There is a stack of N cards numbered 1 to N in order, with 1 on the top and N on the bottom. Two players are going to play a game where they will each wind up keeping some of these cards. The utility a player gets from playing the game is equal to the sum of the numbers on all the cards the player kept.
The game works by the players taking turns. On a turn, the active player may either keep the top card or give it to the other player. If the active player kept the card, then the other player gets the next turn. If the active player gave the card away, then the active player gets to take another turn. The play continues until the deck is empty.
Assuming optimal play, what is the result?
If you don't like utility, instead assume that the cards are worth $1 to $N, in order, with the $1 card on top and the $N card on the bottom. A player gets to cash out all of the cards that that player kept at the end of the game. People like money, right?
2 comments:
This is what I think I figured out, but I haven't done a proof or anything fancy like that.
If N is even then it seems easier, and both players agree with the amount of utility the game has.
I thought N being odd would be different, but I still find the optimal play is a tie.
One difference is that the even players are always greedy. They will always give away a card for the the n+1 card below it. This isn't always the case for the odd players though it almost always is...
I expect that I'm missing something clever here, I should probably think about it more.
Well, I already answered you in person, but I might as well answer you on here also.
It is slightly non-trivial that the players will try to divide up the utility if they can, but it is what happens in the actual case.
Giving away a card for the card below it is a funny concept, since why not just give away two cards for the card below that? Because the other person gets more than you? Then why give away any cards, why not just take? In the actual solution, the players do perform many give-take actions, but I guess it comes down to actual proofs to see when to do what.
Post a Comment