3
$\begingroup$

Consider the following competitive game:

There is a pie, whose size is a random uniform variable (from 0 to 1 kg, say). No player knows the size of the pie.

Each player writes down their request - how much pie they would like, anywhere from 0 to 1 kg. Let player 1 request a1, player 2 request a2, and so on.

The size of the pie is revealed, and the players are served their requests, starting from the player with the smallest request, continuing in ascending order through to the player with the largest request (or whenever the pie runs out). In the case of exactly equal requests where there is not enough pie to serve both players, each gets an equal portion of what remains.

What is the optimal strategy?

Optimal strategy is defined as the strategy which maximises, over multiple rounds, the expected pie won. A strategy can take into account the past actions of opposing players. No communication between players is allowed.

Even considering the case of only 2 players, the situation is complex, because it is best to bid 1 (if their bid is lower than (1-1/sqrt(2))), or slightly undercut their bid (if their bid is anything higher than (1-1/sqrt(2))). This will probably lead to a somewhat chaotic set of bids.

Any thoughts?

$\endgroup$
  • $\begingroup$ What is the number of players: two, finite $n$, countable $n$? $\endgroup$ – mlc Mar 13 '17 at 8:21
  • $\begingroup$ Finite $n$, at least 2, and I beleive OP is particularly interested in the $n=2$ case. $\endgroup$ – MJD Mar 13 '17 at 12:26
  • $\begingroup$ This problem is still interesting even if you assume that the pie always has size 1 and that the two players already know this. $\endgroup$ – MJD Mar 13 '17 at 15:35
0
$\begingroup$

Ok, so what's the Nash equilibrium? Consider the $n=2$ player case. Let's look at a fixed size of the pie $p>0$ for now.

A Nash equilibrium (NE) is a strategy profile $(a_1,a_2)$ such that $(a_1,a_2)$ are best responses to each other. A symmetric Nash equilibrium is $(a_1=p/2,a_2=p/2)$.

"Proof": Could any of the two players do better by switching? Then we would not have a NE, otherwise we do. Suppose player 1 switched to $a_1>p/2$ ($a_2$ stays fixed). He would still get $p/2$ (given that half goes to player 2 who now has the smaller "demand" and is served first), so no improvement. Suppose player 1 switched to $a_1<p/2$, then he would get less than $p/2$, exactly what he asked for, but this is less than in the Nash equilibrium candidate (where he gets $p/2$). So $(a_1=p/2,a_2=p/2)$ is a Nash equilibrium, i.e., $a_1$ is the optimal action given $a_2$ and $a_2$ is the optimal action given $a_1$, i.e., both play best responses to each other.

Is there also an asymmetric Nash equilibrium? No. Suppose without loss of generality $a_1>a_2$ would be a Nash equilibrium. If $a_2<p/2$, then player 2 could get more by playing $\hat{a}_2=(a_1+a_2)/2$, so there is a profitable deviation and it cannot be a NE. If $a_2>p/2$, then player 1 could get more by playing $\hat{a}_1=p/2$ (which guarantees $p/2$, which is more than $\min\{0,p-a_2\}$ [since $p-a_2<p/2$] that he would otherwise get), so a profitable deviation exists and it is no NE.

With the same arguments we can show more generally that, for finitely many $n\ge 2$ players, the symmetric NE strategy has to be $a_i=p/n$ for $i=1,...,n$. (No asymmetric NE exists.)

I leave the case of stochastic $p$ to someone else.

Note: In case you don't know, a Nash equilibrium is vaguely what you call optimal strategies for both players when both players know what the other is playing (so that there is no surprise). In a Nash equilibrium, both players play the optimal strategy given the strategy of the other player.

$\endgroup$
  • $\begingroup$ Thanks, Nameless and MJD, for your thoughts. I realised that when the pie is of fixed size, there is a simple, symmetric Nash equilibrium at a1=a2=p/2. That's why the problem is much more interesting when the size of the pie is a random variable. And I'm not only interested in the n=2 case - just I figured that, unless we solve that, there is little chance of solving n>2. $\endgroup$ – Thomas Delaney Apr 12 '17 at 5:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.