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.