A card game is played by splitting a face-down shuffled deck evenly between two players. The deck consists of cards numbered 1-52. Each player reveals the top card of their deck, 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 can cheat at this game: first, you know the contents, but not the order, of both decks. Second, each round before your opponent reveals a card, you can choose which card in your deck you will reveal. (That is, you can choose which card you will reveal next based on all of the information you have up to the point where the opponent will reveal a new card.)
My friend suggested that even if you can cheat in this way, there is no strategy you can play which will give you a higher score on average than playing at random. This doesn't seem true to me, but I've had trouble proving that cheating helps in simple cases, or proving (e.g. inductively) that it doesn't matter. Any help is appreciated.
Edit: If it helps, I've previously considered a simpler version of this game, in which you know the fixed order of your opponents' cards, which are played in order. If you are allowed to cheat in this deterministic version, you can optimize your score according to the following strategy. First, it suffices to establish a mapping between their cards and your cards — the card you will play when they play their card. To create this mapping, list your cards in ascending order of rank and list their cards in the same way. If their highest ranked card beats your highest ranked card, pair it with your lowest-ranked card. Otherwise, pair it with the lowest-ranked card you have that still beats it. Remove both cards, and repeat this process.
Edit 2: Conjecture. Even if you cheat, there is no strategy which performs better than chance. In particular, regardless of which strategy you employ, your expected score is simply the probability that a random card from your deck beats a random card from their deck, times the total number of cards in each deck. If you create an $n\times n$ matrix whose $(i,j)$ entry is 1 if your $i$th card beats their $j$th card, your expected score on any strategy is 1/$n$ times the sum of the entries of the matrix. I think I have an inductive proof of this, but am still figuring out how to write it out formally.
Best Answer
Theorem: Even if you cheat, you cannot do better than chance. In particular, your expected number of points is equal to your probability of winning a single round between a random card of yours and a random card of your opponent's, times your total number of cards.
Proof: The proof is by induction. Suppose you and your opponent each have a deck of $n=2$ cards in a fixed but arbitrary order. Consider the payout matrix $\mathbf{P} = \begin{bmatrix}a&b\\c&d\end{bmatrix}$ which has a $1$ in entry $(i,j)$ if your $i$th card beats their $j$th card, and a 0 otherwise. If you choose row 1, your opponent will randomly choose a column $j$. Your payout will either be $a+d$ (if they choose column 1), or $b+c$ (if they choose column 2). Your expected payout on choosing row 1 is $(a+b+c+d)/2$. A similar argument shows the same expected payout on choosing row 2. This establishes the result that your choices do not influence the expected score when $n=2$.
In the inductive case, suppose you have an $(n+1)\times (n+1)$ payout matrix $\mathbf{P}$. Removing cards corresponds to removing a row/column from the matrix — let $\mathbf{P}^{i,\times}$ denote $\mathbf{P}$ with row $i$ deleted; $\mathbf{P}^{\times,j}$ with column $j$ deleted, and $\mathbf{P}^{i,j}$ with both deleted. Finally, let $|\mathbf{P}|$ denote the sum of all the entries of $\mathbf{P}$.
Now consider your strategy of choosing row $i$. Your opponent chooses a column $j$. For a given column $j$, your payout will be $P_{i,j}$, plus the expected payout resulting from continuing the game; by hypothesis, it is $\frac{1}{n}|\mathbf{P}^{i,j}|$. Hence when choosing row $i$, your expected payout over all opponent responses $j$ is:
$$\frac{1}{n+1} \sum_{j=1}^{n+1}\left[ P_{i,j} + \frac{1}{n}|\mathbf{P}^{i,j}|\right]$$
Note that the term $|\mathbf{P}^{i,j}|$ occurs once for each $j$ from 1 to $n+1$. Hence we can assemble the deleted columns into a single negative term $-|\mathbf{P}^{i,\times}|$.
$$\frac{1}{n+1} \sum_{j=1}^{n+1}\left[ P_{i,j} + \frac{1}{n}|\mathbf{P}^{i,j}|\right] = \frac{1}{n+1} \left[ \sum_{j=1}^{n+1} P_{i,j} + \frac{1}{n}\sum_{j=1}^{n+1}|\mathbf{P}^{i,j}|\right] = \frac{1}{n+1} \left[ \sum_{j=1}^{n+1} P_{i,j} + \frac{1}{n}\left(-|\mathbf{P}^{i,\times}| +\sum_{j=1}^{n+1}|\mathbf{P}^{i,\times}|\right)\right] = \frac{1}{n+1}\left[|\mathbf{P}^{i,\times}|+\sum_{j=1}^{n+1} P_{i,j}\right] = \frac{1}{n+1}|\mathbf{P}|$$
This establishes the result for the inductive case.