The Median Game - For Money

Question

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.

Answer 1

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$.

Answer 2

With several assumption what is possible, I come to the following:

player 1 and 2 have no better play than calling out 5 and 6.

1 and 2 are natural allies and so are 4 and 5. Neither team wants a bidding war, so player 4 will offer X$ for 3 to bid non-adjacent (and thus get control). Here x should be such that player 3 decides randomly; then team 1-2 will not bid.

case 1: If player 3 bids adjacent (i.e. does not take a bribe):
- player 3 will win 1/7 of the time (if 4 and 5 choose its side; 3/7*2/6 chance)
- player 1 or 2 will win otherwise with equal chance 3/7

So player 4 will offer a 100$/7 bribe for 1,2,3,8,9 and 10.
Player 3 takes a random number and thus the bribe 6/8th of the time.

case 2: If player 3 takes the bribe:
If player 4 does not take a bribe he will call 4 if player 3 called high and 7 if player 3 called low, for a 50% win chance when player 5 claaes randomly.
- Thus player 5 will offer player 4 50$ to let him win (i.e for 2 numbers, instead of the one he would normally choose.
Then player 4 decides randomly, and again the rest will not start a bidding war.

case 2a: If player 4 also takes the bribe (2/3rd * 6/8th of the time)
- player 3 gets 100/7(received)
- player 4 gets 50(received)-100/7(paid)
- player 5 gets 100(won)-50(paid)
case 2b: If player 4 does not take the bribe (1/3rd * 6/8th of the time)
- player 4 gets 50(win) - 100/7(paid)
- player 3 gets 100/7(received)
- player 1,2 get 25(win)

Total expected gain:

player 1,2: 1/4*3/7 + 0 + 1/4*1/4 = 17.86$
player 3: 1/4*1/7 + 1/2*1/7 + 1/4*1/7 = 14.28$
player 4: 0 + 1/2*5/14 + 1/4*4/14 = 25.00%
player 5: 0 + 1/2*1/2 + 0 = 25.00$
Addition; the entire calculation probably fails, since player 3 can offer player 2 a bribe (of at least 3.58$) to call out 7 i.s.o. 6 and then call out 6

Note that there is room for 'meta gaming'; If player 4 bribes player 3 for a lesser amount (or not at all), both player 5 and player 4 will want the other to increase the bid to 100$/7, and both have an incentive to do it themself.