1..n game, how to analyze?

Question

I came up with a simple game.

A permutation of 1..n is available for purchase in that order. 2 players each have m in money each to bid for one number at a time in the permutation in order and will get that score for purchasing it. The player who won the previous auction starts bidding for the next number A player may bid zero and then wins if the other player does not bid. In the end, only the score counts, not remaining money.

Naturally, by a simple strategy-stealing argument, there has to be a winning move for the first player, and there can only be one such winning move.

E.g. the case n=5, m=8

Each example shows only one line of play:

54321: 5 wins // (bid for) 5: P1=5, P2 pass 4: P1=3, P2=4 3: P2=3 2: P2=1, P1=2 1: P1=1 wins

54321: 6 loses // 5: P1=6, P2 pass 4: P1=2, P2 = 3 3: P2=2 2: P2=2 wins

52431: 4 wins // 5: P1=4, P2 pass 2: P1=1, P2=2 4: P2=4 3: P2=2, P1=3 wins

Becase a player needs to win 8 points to win, and there are a total of 8 money per player, it seems natural that the number n is worth about n. My conjecture is that a winning bid in the special case if the first number in the permutation is p, is always p or p-1

Has this game been considered before?

What is the natural way to proceed with this problem? (except exhaustive search)

Edit: It seems like a fairly interesting game, but after a bit more thought, I guess that the fact that the players are bidding for a permutation of 1..n does not make the game any simpler to analyze than an arbitrary set. Because, the central point of the analysis will be: Which possible subsets of 1..n do I have to win to win the game? For example, to win the game 1..5 you will need to win {5 4}, {5 3}, {5 2 1}, {4 3 2} or {4 3 1} or some super-set of one of those sets.

This means that the simplest case to analyze will instead be a game consisting of n 1's to bid for (where n is odd and you need to win ceil(n/2) auctions to win). That game is fairly simple to analyze, but I haven't been able to generalize further than that.

What I find interesting is how the order in which the auctions proceed will affect the best bid. This is a little surprising in such a simple setting.

I have seen a blind bidding variant similar to the one suggested in comments played also (and I believe it is quite possible to get really good at it), but that is a completely different game.

Answer 1

"My conjecture is that a winning bid in the special case if the first number in the permutation is p, is always p or p-1"

Did you mean n instead of p here? For the 5 and 6 case I think this is true, if my minimax codes are right, but I don't think this is the case for n=10 m=28 when the initial permutation is (10,1,2,3,4,5,6,7,8,9) for example. In this case the winning initial bid is n-2=8 whereas n-1=9 and n=10 both lose.

Answer 2

I will be assuming that money starts at 1 for each player and players can bid any real number. I'll also assume that prizes are real numbers.

First, it should be noted that in each position with prizes $p_1 , \dots , p_n$ and accumulated scores $s_A, s_B$, if one player wins with money $m$ then he can win with any amount $m'>m$ and if that player loses with money $m$ he also loses with $m' < m $.

Let's assume that there is no partition of the prizes into two classes which yield the same sum; the above argument shows that there is a "singular value" which is the separator of the classes of winning and losing position for a player (such existence is guaranteed in $\mathbb{R}$).

There is a practical rule to find out what that value is in general, but let's start with simple positions: if player $A$ has to win $n$ times in a row in order to win, it is easy to see that the winning condition is $ \frac{1}{n} \cdot m_A \geq m_B$.

To analyse a general position, given that the win-the-prize option has a winning condition of the form $\chi_W \cdot m_A \geq m_B$ and the lose-the-prize option has a winning condition of the form $\chi_L \cdot m_A \geq m_B$, the position the player $A$ is in has a winning condition of $ \frac{1+\chi_L}{1+ \frac{1}{\chi_W}} m_A \geq m_B$.

To see why this happens, just consider the associated system of inequalities:

$$\chi_W \cdot (m_A - p) \geq m_B $$

$$\chi_L \cdot m_A \geq m_B - p$$

then deduce

$$ m_A - \frac{ m_B}{\chi_W} \geq p \geq m_B - \chi_L \cdot m_A $$

Taking equalities yields the relation stated above.

This way, starting form the end of the auction tree you can go backward and find out all the $\chi$ for each position, until you get to the first one. Note that exacxtly meeting the inequality does not guarantee a win, it depends on who is going first on that auction (i.e. who won the last auction).

I'll add an example:

Prizes: 10 6 4 8 5

Minimal winning sequences: 10 8, 10 4 5, 10 6 4, 10 6 5, 6 8 5, 6 4 8, 4 8 5.

Results: In the starting position, $\chi=1$. After the first auction, the losing and winning $\chi$ are respectively $\frac{4}{7}$ and $\frac{7}{4}$; after the second auction the $\chi$ are $\frac{3}{1}$ if you won both 10 and 6, $\frac{4}{3}$ if you won 10 and lost 6, $\frac{3}{4}$ if you lost 10 and won 6, $\frac{1}{3}$ if you lost both.

Note that in the general case where there could be ties, the $\chi$s may not be one the inverse of the other, resulting in a $\chi>1$ for the starting position, which means the first player has no way to win (but still has a way to draw). In fact, I think that every time there is a partition in two subsets so that each yields the same sum, it is not possible for the first player to win (he can just draw).