# 1..n game, how to analyze?

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.

-
I'm afraid I don't understand your notation for the example. Could you expand a little? – j.c. Oct 12 '10 at 0:11
I have played such a game as a young child with a deck of cards: the permutation consisted of one shuffled suit, and each player had a suit from which to bid, but bidding was secret. Unfortunately, I don't remember its name :( – JBL Oct 12 '10 at 12:46
The open information isn't clear. Do both players know the permutation before the game begins? If not, do players learn of the number if they don't win the bid? What happens if the bids are tied? If both players are out of money? – Kevin O'Bryant Oct 12 '10 at 14:48
Both players know the permutation before the game begins. You can't make a bid that would tie. If you are out of money then you have to either bid 0 or lose the bid. – ohai Oct 12 '10 at 16:33

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

-
I was thinking that if the sum of the numbers is odd, perhaps the case with m = ceil(n(n+1)/4) would be simpler. However, with the evidence on bids I have seen so far, I don't have that much support for that. E.g. n=5, m=8, and n=10, m=23. But it is of course possible that the game just needs an exhaustive search to beat. – Carl Johan Oct 12 '10 at 7:07
Do you have some code for how you implemented this minimax function? For the case n=10, m=28, branching seems rather high and the number of options very large unless you impose some restrictions. – Carl Johan Oct 13 '10 at 13:21

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

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