A bin-assignment infinite 2-player zero-sum game

149 Views Asked by At

What is known about the following infinite 2-player zero-sum game? There are $k$ bins. Each player has 1 unit of mass and, simultaneously, divides it arbitrarily among the $k$ bins. The player wins \$1 for each bin where they put more mass than the opponent, and loses \$1 for each bin where they put less mass than the opponent.

Based on solving discrete cases (where mass must be allocated in integer multiples of some small $\epsilon>0$), it looks to me like the optimal strategy probably has infinite support, but may not be continuous nor assign positive probability to any specific move. It seems like it might have no simple description. I'm interested in $k=4$, but $k=3$ doesn't seem much easier. (Obviously, $k=2$ is trivial.)

1

There are 1 best solutions below

2
On BEST ANSWER

I'll start by analysing the 3-bin case. The $k$-bin case is exactly analogous, and I'll say a few words about how to change the proof for this at the end. We know by symmetry that the optimal strategy has value $0$ for each player.

Claim: Suppose that we can come up with a joint distribution on three random variables $X,Y,Z$ such that $X+Y+Z = 1$ and the marginal distributions are uniform on $[0,\frac{2}{3}]$. Then letting $[X,Y,Z]$ be the amounts assigned to the three bins is an optimal strategy.

Proof: Assume the opponent plays $[a,b,c]$, where $0 \leq a,b,c \leq 2/3$. What is the expected value of this move. By linearity of expectation, it's the sum of the expected value for each of the three bins. So let's compute the expected value of the first bin.

The probability that $X > a$ is $(3/2)(X-a)$ and the probably that $X<a$ is just $3/2 a$. Thus, the expected value of the contribution from the first bin is $$\mathrm{E}(3/2)(X-a) = (3/2) (\mathrm{E}X - a) = 1/2 - (3/2) a.$$ And the expected value of the game is $$ 3/2 - (3/2) a - (3/2) b - (3/2) c = 0.$$

It's easy to see that against this strategy, making $a > 2/3$ only hurts the second player. This proves the claim.

Now, we need to show that there's a joint distribution on three random variables $X,Y,Z$ with their sum being $1$ which has the right marginals. There are undoubtedly lots and lots of ways of doing this.

We can do this by first giving a strategy where $X,Y,Z$ always take on odd multiples of $1/3^k$ that has marginal distribution uniform on odd fractions between $1/3^k$ and $2/3 - 1/3^k$. We can then take the limit as $k\rightarrow \infty$. I'm not going to go through all the details, but just write out the first two cases.

For $k=2$, this distribution is uniform on the vectors $$[1/9, \, 3/9, \, 5/9] $$ $$[3/9,\, 5/9, \, 1/9] $$ $$[5/9,\, 1/9, \, 3/9]. $$

For $k=3$, we replace each of the vectors by three new vectors. These are $$ \begin{array}{llllcrrr} [1/9 -2/27, & 3/9, & 5/9 + 2/27 &]&=&[ 1/27, &9/27,& 17/27]\\ [1/9 , & 3/9 + 2/27, & 5/9 - 2/27 &]&=& [3/27, &11/27, &13/27]\\ [1/9 +2/27, & 3/9- 2/27, & 5/9 &]&=& [5/27, &7/27,& 15/27]\\ [3/9 -2/27, & 5/9 , & 1/9+ 2/27 &]&=& [7/27, &15/27,&5/27]\\ [3/9 , & 5/9 + 2/27, & 1/9 - 2/27 &]&=& [9/27, &17/27,& 1/27]\\ [3/9 +2/27, & 5/9 - 2/27, & 1/9 &]&=& [11/27, &13/27,& 3/27]\\ [5/9 -2/27, & 1/9 , & 3/9 + 2/27&]&=& [13/27, &3/27, &11/27]\\ [5/9 , & 1/9 + 2/27, & 3/9 - 2/27& ]&=& [15/27, &5/27,& 7/27]\\ [5/9 +2/27, & 1/9 - 2/27, & 3/9 &] &=& [17/27, &1/27,& 9/27]. \end{array} $$ It's not hard to give an explicit map from $[0,1]$ to $[0,1]^3$ that gives this distribution when you start with a uniform distribution on $[0,1]$ ... express $x \in [0,1]$ in base 3, and use these to decide which of the three possibilities to choose at each step.

For the case with $k$ bins, the only significant difference is that we want each of the $k$ variables to have a marginal distribution that is uniform on $[0,2/k]$.