There is an ICPC 2016 contest question about cheating in a raffle. It gives n names in the raffle box and p prizes, and you give back the optimal probability of winning a prize in the raffle by possibly cheating. The rules of cheating are that you lose your prize if your name comes up more than once.
But what if, instead, you are given n participants and p prizes, and you're not given how many cheat and by how much, but you're allowed to assume that everyone plays optimally. What is an approach to finding a solution to this problem?
Edit: As Saul points out, the probability is the same. So how many tickets do I (and everyone else) add?
Edit: As Saul also pointed out, the answer depends on whether lost prizes are redrawn or discarded. To be reasonable (not having stated this distinction first), an answer to either assumption is interesting.
(This isn't a homework or a competition question.)
Several partial solutions.
Assumption $1$: the OP question asks for an "optimal" strategy. If you know your opponents' strategies before hand, then finding your optimal (assuming it exists) is a matter of tedious computation. But if you must take into account your opponents being just as perfectly smart as you are, then the usual approach is to look at Nash Equilibrium (N.E.), which is what I will do here.
Assumption $2$: the original specification is unclear on what to do after a cheat is found. In this answer I assume an IMHO natural extension: the drawing continues until either (1) $p$ non-disqualified winners have been drawn, or (2) $n-p$ players have been disqualified in which case drawing stops and the prizes automatically go to the other players. This way, $p$ prizes are always awarded, and the game remains zero-sum.
Proof: obvious, since more tickets is always better and there isn't a maximum integer. Note that it is perfectly fine for a game not to have a N.E. due to the nature of the strategy set (here, pairs of integers).
For the rest, I only consider fixed "all $k$" symmetric strategy set, where each player puts in the same number of tickets, $k \ge 1$, and I ask whether it is a N.E.
When each player puts in $k$ tickets, by symmetry they have the same payoff. Meanwhile by assumption $2, p$ prizes are always awarded, so the payoffs must sum to $p$, so each player's payoff (prob of winning) $= p/n$.
The definition of a N.E. is that, from player A's perspective, if every other player puts in $k$ tickets, then player A cannot do better by putting in a different number of tickets.
Proof: For $n=3, p=2$, two tickets drawn suffice to determine the winner - if they are different then those players are winners, whereas if they are the same then that player is disqualified and the others are the winners. E.g. A wins if the two drawn tickets are: AB, BA, AC, CA, BB or CC; and A loses if the two drawn tickets are: AA, BC or CB.
The question therefore becomes, whether $\exists a \neq k$ s.t.
$$p_A := Prob(\text{A loses}) = {{a \choose 2} + k^2 \over {2k+a \choose 2}} < \frac13$$
If such an $a$ exists, then A can do better by putting in $a$ tickets instead of $k$ tickets, so the "all $k$" symmetric strategy set is not a N.E.
In the following, we rewrite $a = k+b$ for some integer $b$ (positive or negative):
$$ \begin{array}{} p_A < \frac13 &\iff 3 (k^2 + {a (a-1) \over 2}) < {(2k+a) (2k+a-1) \over 2}\\ &\iff 6 k^2 + 3 (k+b)^2 - 3 (k+b) < (3k + b) ( 3k + b - 1)\\ &\iff 9 k^2 + (6b-3) k + 3 b(b-1) < 9 k^2 + 3 (2b -1) k + b(b-1)\\ &\iff 2 b(b-1) < 0 \end{array} $$
But the last inequality is impossible for any integer $b$ (positive, zero or negative). So, for any $k$, A cannot do better by putting in a different number of tickets, so the "all $k$" symmetry strategy set is a N.E. for any $k$. $\square$
Comments:
Curiously, it turns out $b=1$, i.e. $a=k+1$, also yields $p_A = \frac13$. However since this is not $< \frac13$, this does not affect the N.E. status.
It is a surprise to me that "all $k$" is a N.E. for any value of $k$. In the context of the OP's question, IMHO this means there is no "optimal". E.g. when both opps are playing $k=17$, your optimal is $a=17$ or $18$, but when they are both playing $k=293$, your optimal is $a = 293$ or $294$, etc. Anyway, this surprising result is probably just a quirk of $n=3, p=2$, because it is no longer true when...
I have a partial proof plus some strong numerical evidence.
Again, three tickets drawn suffice to determine the three winners. A loses if the tickets are: BCD (in any order), A+A+(not A) (in any order), or AAA. So again the question become whether $\exists a \neq k$ s.t.
$$p_A = Prob(\text{A loses}) = {k^3 + 3k{a \choose 2} + {a \choose 3} \over {3k+a \choose 3}} < \frac14$$
Here are the numerical values of $p_A$ for $k \in \{1, 2, \dots, 10\}, a \in \{0, 1, 2, \dots, 15\}$
Note that:
In all cases $k=a \implies p_A = \frac14$ as expected.
For $k=1$ there does not seem to be any $a$ s.t. $p_A < \frac14$. This is strong evidence that "all $k=1$" is a N.E. (This case must be easy to prove, but I didn't bother.)
For $k \in \{2, 3, \dots, 10\}$, there exists $a (< k)$ s.t. $p_A < \frac14$. This proves "all $k$" is not a N.E. for these $k$.
The fact $a<k$ is (often) better for A means A is winning by virtue of others being caught cheating.
The best $a$ seems to be $\approx k/2$ or slightly less.
When $k=9$ or $10$, even $a=0$ (no tickets for A!) beats $\frac14$.
I did not try $k > 10$, but again IMHO the numerical evidence is very strong that none of these "all $k$" would be a N.E. E.g. it might be possible to prove that $a=1$ (e.g.) beats $\frac14$ whenever $k> 10$.