6
$\begingroup$

$b^2$ swimmers are to be put into one of the teams $1,2,\dots,b$. A team $i$ has a value function $f_i$, so that if they get swimmer $k$, they get value $f_i(k)$. The value $f_i(k)$ is randomized uniformly from $[0,1]$, independently of this value for other $i,k$. (So, there are $b^3$ different values in total.) The value that a team has for a set of swimmers is simply the sum of the individual values.

Suppose that we divide the swimmers to maximize the product of the team values. For large enough $b$, is it true that each team will get a number of swimmers in the range $[b/2, 2b]$ with high probability? In other words, is it highly likely that the swimmers will be divided roughly equally between the teams?

$\endgroup$
4
  • $\begingroup$ Since you are maximizing the product of the sums, it seems something with nearly equal sums is intended, and that seems different to me than roughly equal numbers of members per team. I would guess that it is not high probability (consider swapping one member of value 3/4 for three members of value 1/4). It really depends on the specific f_i. Gerhard "Is Sure He Is Uncertain" Paseman, 2016.05.31. $\endgroup$ Commented May 31, 2016 at 22:22
  • $\begingroup$ I have trouble handling small scores. Are you equally happy with scores uniform in [1,2] ? And for that matter, with team sizes in [b/100, 100b] or worse ? $\endgroup$
    – user83457
    Commented Jun 2, 2016 at 13:58
  • $\begingroup$ @michael [b/100, 100b] is fine. [1,2] I'm not sure - haven't thought carefully yet, but would still be interesting I guess $\endgroup$
    – Karo
    Commented Jun 2, 2016 at 14:11
  • $\begingroup$ That case is actually very straightforward. Let T be optimal, L be largest team sum, and S be smallest. Starting with the optimal , move a player from the the largest to the smallest. You lose XT/L and gain YT/S, where X is the players value to the large team and Y that to the small team, also the T/S isn't strictly accurate but is very good on a percent basis. If X and Y are comparable you will improve if S/L too small. $\endgroup$
    – user83457
    Commented Jun 2, 2016 at 16:06

1 Answer 1

2
$\begingroup$

This is not exactly a solution, but what seems a good way to approach the problem.

1) Consider for each player $k$ the team $I(k)$ to which he brings a maximal value $$ v(k)=\max_i f_i(k) = f_{I(k)}(k). $$ BTW: note, that most probably for most of the players $v(k)$ is quite close to 1, as it is a maximum of $b\gg 1$ independent $R[0,1]$'s; to be more precise, the expectation of $v(k)$ is $1-\frac{1}{b+1}$.

2) Take a "greedy" way of forming the teams: put each player $k$ into the team $I(k)$ where he plays the best. Then, each player equiprobably goes to any of the teams, hence the number of players in any team is equal to the sum of $b^2$ expectation-$1/b$ Bernoulli variables, and thus is roughly normal with expectation and dispersion $\sim b$. In particular, the teams formed in this way are roughly equal, differing from $b$ by something like $\sqrt{b}$.

If I'm not mistaken, this means that the product for this case differs (in average, most probably) from the theoretical maximum of $b^b$ by a factor of constant. (This could be surprising, as in the theoretical upper bound 1 is used instead of all the values, but in fact the greedy method almost gets 1 everywhere, and $(1-1/b)^b$ is $1/e$ -- a constant)

3) The idea now is that if you divide the players in a strongly non-equal way, you will get a value that will be lower than the ``greedy'' one.

4) Namely: imagine, that one of the teams is much smaller than the average, that it has less than $\epsilon b$ players (where, say, $\epsilon=\frac{1}{10}$). Then, you get an upper bound for the product by $\epsilon b$ times $(b+(1-\epsilon)b\cdot \frac{1}{b-1})^{b-1}$ (it is a bit rough: we're again setting all the players to values 1). But this is a theoretical maximum of $b^b$, multiplied by a constant, which is approximately equal to $\epsilon \cdot \exp(1-\epsilon)$, and the smaller is $\epsilon$, the smaller it becomes. In particular, for sufficiently small $\epsilon$ it becomes smaller, than the constant that we are getting in the greedy algorithm.

The same applies if one of the teams is too large, larger than $Ab$. The upper bound is again $b^b$ times $A\cdot \exp(1-A)$, and the factor $A\cdot \exp(1-A)$ tends to zero as $A$ tends to infinity.

5) Finally, it looks quite plausible that one can make the above arguments work for $\epsilon$ and $A$ arbitrarily close to $1$, but for that one should improve the above arguments in two points:

*) First, take $S=\sum_k v(k)$ to be maximal possible sum of values, and use $(S/b^2)^b$ as a reference point instead of $b^b$.

*) Second, re-equilibrate the teams: for every player, consider the team which is second-best for him, and try moving $\sim \sqrt{b}$ players from large teams to smaller ones, which are second-best for them.

It looks plausible that with this improvement of the greedy algorithm you get a product that is equivalent to our new maximum-reference point $(S/b^2)^b$, while any $\epsilon<1$ or $A>1$ reduce maximum possible value by a constant factor.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .