# Optimal way to stack deck against adversarial opponent?

A two-player card game is played with a deck of cards numbered 1-52, which is shuffled and placed face down. Each player draws a card from the top of the deck, then both players reveal their cards and the player whose card has higher rank scores 1 point. Both cards are then discarded. The process is repeated until both decks have been depleted. The winner of the game is the one with the largest number of points.

Suppose you and your opponent can "cheat" at this game. Subjectively, when you reveal a card from your deck, that card is drawn uniformly at random from the set of all cards that haven't been played yet. Instead, before drawing, you and your opponent may each secretly choose to have their card drawn uniformly at random from a restricted subset of cards. You may choose any subset of two or more specific cards that haven't been played yet, and your opponent may do the same. (Neither of you has any information about whether the other person has cheated or which subset they've chosen, and the choice of subset is made before any cards are drawn that round.) The cards you and your opponent draw are guaranteed by the laws of physics to be distinct.

Is there an effective strategy for cheating that improves your chances of winning over playing fairly, or is the best strategy to play fairly? I have tried to tabulate the payoff matrix for simple cases (n=2, n=4 cards) as well as trying to formulate an argument based on the symmetry of the game, but I haven't been able to prove a result either way yet. Any help is appreciated!

See also: I asked an earlier question about a similar game, where a single deck is split into two halves whose contents are known, and the opponent draws cards randomly instead of adversarially. Optimal way to stack deck against uniformly random opponent? Unlike in that question, in this question both players are drawing from the same pool of unplayed cards (rather than both players knowing the contents of their respective halves and drawing from only those halves.)

• I believe, but do not think the proof is solid, that you can't do better than choosing randomly. Imagine playing against an opponent who draws randomly. How can you do better than drawing randomly? – Ross Millikan Feb 27 at 6:09
• @RossMillikan That's my intuition as well. But what if against an opponent who draws randomly from the full set of remaining cards, you chose to draw one of the two highest-ranked cards remaining? Wouldn't that generally improve your chances of winning? – user326210 Feb 27 at 6:14
• That would improve your chances of winning this round, but not the overall contest. – Ross Millikan Feb 27 at 6:17
• @RossMillikan I don't have a clear understanding of why that's true. It seems like if restricting to high-rank cards helps in the first round, it will also tend to help (to a lesser extent) in subsequent rounds as well. – user326210 Feb 27 at 6:20
• No, because it leaves you with lower ranking cards for the later rounds – Ross Millikan Feb 27 at 6:24

Theorem: The optimal strategy is for both players to cheat each turn by choosing the two cards of highest rank. In this case, because you and your opponent are symmetric, the probability of winning is 50%.

Proof.

1. If you draw the card of highest rank, you will win against any card your opponent draws with certainty. If you draw the card of next-highest rank, you will win against any card your opponent draws, except if your opponent draws the card of highest rank. All lower-ranked cards are less likely to win than these two against any given subset of cards your opponent chooses. Therefore to optimize your expected winnings, you should cheat by choosing the two cards of highest rank. (So, by symmetry, should your opponent. but let's explore in more detail.)

2. Suppose your opponent chooses a subset of $$k$$ cards. If you draw the card of highest rank, you win with certainty. If you draw the card of next-highest rank, you win unless they draw the card of highest rank. That probability is $$1/k$$ if their subset doesn't contain the card of next highest rank, or $$1/(k-1)$$ if it does (because your opponent cannot draw the same card as you).

3. Therefore against your strategy, your opponent should: include the card of highest rank, so as not to lose with certainty; include the card of next-highest rank so that the probability of winning otherwise is $$1/(k-1)$$ instead of $$1/k$$; and include no other cards so that $$k=2$$ is minimal.

4. In this case, each player will win the round with probability 50%, by the symmetry of their positions, and also because the enumerated outcomes are [highest, next-highest] or [next-highest, highest].

5. Every round has at least two cards remaining in the deck. Because our considerations don't otherwise depend on the number of cards in the deck, this same per-round strategy applies in all subsequent rounds. Your probability of winning is 50%.

Your linked question has an answer that shows you cannot do better against a random opponent than to be random yourself. That shows your opponent cannot be sure to do better against you than by playing randomly, so both of you should play randomly. Now symmetry says you win with probability $$\frac 12$$ if draws are split.