Generalized Even Odds

The discussion on Less Wrong about my recent post, Even Odds, raised questions about what to do with more than two alternatives, and what to do with more than two players. Here are some generalizations.

If you have 3 or more different possibilities, then the generalization of the algorithm is simple. Both players report all of their probabilities. Find a proposition P such that the expected payoff for both players if you run the even odds algorithm on P is maximized, and run the even odds algorithm on P. (Break ties randomly) This is clearly fair. To show that this is strategy proof, assume that Alice were to lie about her probabilities. There are two cases. Either Alice’s lie changes the proposition P, or it does not. If the lie does not change P, then Alice is no worse off by the strategy proffness of the original even odds algorithm. If Alice’s lie changes the proposition from P to Q, then notice that Alice prefers telling the truth and betting on P to telling the truth and betting on Q, and Alice prefers telling the truth and betting on Q to lying and betting on Q, so Alice must prefer telling the truth and betting on P to any lie which makes her bet on Q. Therefore, this algorithm is strategy proof.

If there are 3 people, observe that the player who assigns the highest probability to the proposition and the player who assigns the lowest probability to proposition have no incentive to wager with anyone besides each other, since they get more profit for wagering with probabilities that are further apart. Therefore, it would make sense to not force these two players to bet with anyone else. However, this is not strategy proof, since now the third player might be incentivised to lie slightly about his probability in order to participate in a bet. This would not be fair or strategy proof.

Instead, we want to do all pairwise bets, with each player willing to bet half their maximum in each bet. This would clearly be strategy proof, since the component bets are strategy proof. However this is not fair. If one of the bets expects a higher profit than the others, then the player not participating in the high wager bet gets less output. This can be fixed by saying that for each bet, if both players are expected to gain x dollars, then they both also give x/3 dollars to the third player. This makes the wager also fair. It is still strategy proof, since we scaled expected payout by 2/3. However, if a player believes a statement 100%, and the other two think he is wrong 100%, an he is wrong, then he will end up paying d/2 in each bet, and an additional d/6 to each player as a tax for the bets he thought he would win. This totals 4d/3. We should therefore renormalize and have each bet be at 3d/8 instead, so that each player pays at most d total.

To generalize this to n players, run all n(n-1) bets. For each bet, both players pay every other payer 1/n times their expected profit to every other player. Each of these bets is an implementation of the even odds algorithm with maximum bet dn/(2(n-1)^2).

The algorithm for n options seems optimal to me, but I am not sure that the algorithm for n players is optimal.