# The Median Game - For Money

Inspired by this interesting puzzle which was quickly solved.

Five friends play a simple game with the following rules:

1. Players play consecutively one after the other.
2. Each player must call out a whole number between 1 and 10 (inclusive), such that it hasn't been called out already.
3. The winner is the player whose number is the median of all called out numbers.
4. The winner receives \$100. At any point, players are allowed to "bribe" others to guess in a particular way (e.g. Player 5 says to Player 4 "I'll give you \$20 if you choose a 3.")

What should be the optimal strategy for each player to maximize their expected profit? What is the expected profit for each player?

Assume that the players' only interest is maximizing their own profit, and they will choose randomly if their available options all have the same expected profit.

• Interesting. Can they bribe others to not to bribe others? :-P
– Eric
Apr 1 at 13:34
• I think for this to work you need some kind of irrevocability: if a players has said something, they cannot renege on whatever they have said. This means you can't allow them to bribe (or talk) "at any point". Instead it's most natural if everyone can only make their offer before they choose their number. I asked a similar puzzle in this fashion puzzling.stackexchange.com/questions/109112/…
– Eric
Apr 1 at 14:00
• I think the "bribes" need a lot of further clarification for the question to be answerable. Apr 1 at 15:09
• Can people update their offers repeatedly in a bribing escalade? Must all amouts be in whole dollars, or dollars and cents? Apr 3 at 13:39
• I believe that the optimum strategy may depend on weather the bribes are public or private. So is everyone aware of the 'deals' each player is trying to make, or can groups of two or more players have conversations private from the others? Apr 3 at 23:45

I claim that

introducing bribes doesn't change how the game is played!

This is because

there will always be two or more players who would benefit from a bribe, yet the player being bribed could accept any and all of them. The bribers, recognizing this, choose not to bribe at all, because if one offered $$\\\x$$, then another would offer $$\\\x+\epsilon$$, and so on, until all bribers offered $$\\\100$$. At this point, the player being bribed has no more incentive to behave a certain way than if no money was offered.

To see this, let's understand how a game with players A, B, C, D, and E plays out:

For A to have any chance of winning, they must choose a number with two more numbers on either side. This allows 3, 4, 5, 6, 7, or 8, but it will become apparent that they prefer one of the numbers in the middle, 5 or 6. Assume WLOG they choose 5.

B picks the other number to set their chance of winning equal to A's; in our example, they pick 6.

To have any chance of winning, C must pick adjacent to A or B. Suppose they pick 4.

Now comes the interesting part: D and E are guaranteed to lose, so their only source of income is bribes. Everyone's actions will now play out based on the following information:

A wins if and only if D and E pick from opposite sides of A.
B wins if and only if D and E pick from B's side of A.
C wins if and only if D and E pick from C's side of A.

Therefore, A does not bribe D at all, because that would risk D being counter-bribed; instead, they can always wait to bribe E to pick opposite to D. However, B and C each need D on their side to win, but this runs into the runaway bribing situation, so neither bribe D at all. Thus, D picks randomly and their expected profit is $$\\\0$$.

Suppose WLOG D chooses from B's side. This means A and B each need E on their side to win. So again, neither of them bribe E; E picks randomly, and their expected profit is $$\\\0$$.

Thus, by the symmetry of their choices, A and B each have the same chance of winning. C's chance of winning is $$\frac37\cdot\frac26=\frac17$$, so A's and B's chances each become $$\frac37$$.

This gives the following approximate expected profits:

A: $$\\\42.86$$.
B: $$\\\42.86$$.
C: $$\\\14.29$$.
D: $$\\\00.00$$.
E: $$\\\00.00$$.

• Can you explain further why bribing is suboptimal? And does the logic apply between players who have different winning chances? Apr 3 at 7:59
• Under this answer, C, D, and E have poor expected profits. What's to stop them realising this and devising a scheme where E gives C and D 100/3 dollars each in exchange for setting things up so that E wins the pot (which can be done regardless of how A and B choose)? Is it an assumption that the players don't trust each other enough not to renege? Apr 3 at 10:50