Giving Cards

Time for the solution to the card game from last time. I suppose the standard thing to do is consider simpler cases.

In the case when N=1, the start player must simply take the card (if they are playing optimally, anyway). Next, if N=2 it is optimal to give the 1 card and take the 2 card.

For N=3 we have a real choice. We can simply take the 1 card, in which case the opponent will give us the 2 so they can keep the 3 (ending with 3 vs. 3 total utility). If instead we give the 1 card we will be left in the 2,3 case and it is clearly optimal to give the 2 and take the 3 (again, a 3-3 ending).

Next we must study N=4. This gets a bit trickier, as in order to choose what to do with the top card we must first find the optimal play in the 2,3,4 case. This is not particularly difficult, but it does show that in general we must solve a subgame with cards K,K+1,K+2,...N left in the pile.

Consider a situation where the top card is K and there are L cards left. Specifically the remaining cards are numbered K through K+L-1 (To convince yourself of that -1 consider L=2). Now let us inductively solve this on L. When L=1 we take (this is obvious). When L=2, we give then take, getting K+1 utility instead of just K. When L=3 we have a choice. If we choose to take, we will get card K and the opponent will give us K+1 to take K+2. If we give when L=3, we must also give when L=2 and take the last card, getting K+2 instead of K and K+1. So when L=3, choosing take gets 2K+1 vs choosing give getting K+2, comparing these we can see that 2K+1>K+2 iff K>1, and 2K+1=K+2 iff K=1. In a typical case K>1, so we should keep, and in the exceptional case K=1 we can do whatever (and might as well keep). In particular, being the active player when L=3 and card K is on top is worth K-1 utility.

Next, consider L=4. If we keep, then we get to keep card K, the opponent will keep card K+1 allowing us to give card K+2 and keep card K+3. If we give K we will keep K+1 (L=3 then, so we keep at that point) and the opponent will give K+2 to keep K+3. In the end, keeping gets us K+K+3 vs giving getting us K+1+K+2. These are the same, this result is somewhat clearer when you note that it is worth K utility to be the active player when L=3 and K+1 is on top, but keeping the top card of L=4 is worth exactly K, so keeping the top card of L=4 and being the next active player are worth exactly the same amount, so we do not care. Note that a result of this is that being the active player when L=4 is worth zero utility.

Next, L=5 (hopefully this goes somewhere soon). When L=5, we do not care who is the active player on the coming turn, being active when L=4 is worthless anyway. Thus, when L=5, we might as well keep. For L=6, whoever gets to go on the following L=5 turn will just take the top card worth K+1, so we should give K to the opponent and take K+1 when L=6.

When L=7, we get a similar analysis to L=3. We can take K and receive K+1, watching the opponent take K+2 (because the following initiative on L=4 is worthless). Or we can give K and K+1 to take K+2 (sounds sad unless K=1). This means we should take when L=7. L=8 comes out the same as L=4, being a worthless turn to have the initiative, we can keep or give, it does not matter.

We can see a pattern here. We need only look at how many cards are left mod 4. If the number of cards is 0 mod 4, this turn does not matter. If it is 1 mod 4, keep because the next turn does not matter. If it is 2 mod 4, give so you can keep the next card. If it is 3 mod 4, keep because the opponent is going to give then keep (unless the top card is K=1, then you can give it if you want).

So, if the total number of cards left is odd, you should always keep. If the total is even then give if it is not a multiple of 4, and play random if it is, alternately, you can just always give when the number of cards left is even and you will not be making any mistakes.

This means that the optimal play will have the players constantly performing give-keep actions. There is another way to see this, consider a pair of players that constantly keep the top card. They will divide the deck between them until one of them takes the last card. It is not hard to see that the person who gets the last card has a much higher utility than the other person, as their cards are all 1+ the other persons card. That is to say, the person who got to keep on the turns with odd numbers of cards left is much happier. Two optimal players are just taking turns trying to be the person who gets to take the cards when there are odd numbers of cards left.

The result of the game is that the players divide up the utility quite evenly. Let n be N mod 4. If n=0, the players will split the utility evenly. If n=1, then the first player gets a 1 utility advantage, but the rest is even. If n=2 the active player again gets a 1 utility advantage, by giving the 1 and taking the 2. If n=3, then the players split it evenly again.

How much utility is in the deck? With N cards, there is N(N+1)/2 in total (the N^th triangle number). Exactly one of N or N+1 is even, so the total utility in the deck will only be even if that number is also a multiple of 4. So, the only way that the utility can be split evenly is if N or N+1 is a multiple of 4, that is n=0 or n=3. In the other two cases, there is an odd utility out and the first player to take a turn will always get it.