On Sunday, February 3, 2013 5:36:22 PM UTC, quasi wrote: > Here's a finite version of the problem, cast as a game. > > > > Perhaps the game is well known, I'm not sure, however the > > resolution of the game is nice, and not immediately obvious, > > so I'll pose it here as a challenge. > > > > 2-player play a game, win or lose, for 1 dollar, based on a > > fixed positive integer n > 1, known in advance to both players. > > > > Player 1 chooses two distinct integers from 1 to n inclusive, > > writes them on separate index cards, and places them face down > > on the table. > > > > Player 2 then selects one of the cards and turns it face up, > > exposing the hidden value. Player 2 can then either "stay", > > yielding the value on the chosen card, or "switch", yielding the > > value on the other card instead. Player 2 wins (and player 1 > > loses) if player 2's final value is the higher of the 2 values, > > otherwise player 2 loses (and player 1 wins). > > > > In terms of n, find the value of the game for player 2, and > > specify optimal strategies for both players. > I don't have a solution but I have an outlined approach. Player 1 has n(n-1)/2 choices for pairs. Each of these n(n-1)/2 choices should be picked with a probability p (where p is different for each pair).
If player 2 picks 1, player 2 should guess that the other is larger. If player 2 picks n, player 2 should guess that the other is smaller. Each of the n-2 non-endpoints is assigned a probability q_x where x varies from 2 to n-1. Player 2 switches with probability q_x.
Player 1 chooses the probability for each pair according to the min of the max of the expected gain from all the possible choices for the set of q_x.
It's a Nash equilibrium minmax problem.
Here's a wild guess at the solution. Player 1 should pick all possible choices with probability 1/(n * (n-1) /2 ). Player 2 should switch if player 2's first choice <= n/2. If this is right, then the expected value is trivial to calculate. Furthermore, if I'm right about player 1's strategy (not at all confident about this) then player 2's strategy is trivially correct. However, (again assuming I'm right), player 2's strategy is not unique if n is odd and (n+1)/2 is selected.