quasi
Posts:
12,067
Registered:
7/15/05
|
|
Re: Beating the Odds?
Posted:
Feb 3, 2013 3:04 PM
|
|
pepstein5@gmail.com wrote: >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. >> >> Two players 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.
Right.
>If player 2 picks n, player 2 should guess that the other is >smaller.
Right.
>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.
OK.
>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.
Right.
The problem is to find the minmax value of the game and to specify optimal strategies for each player.
>Here's a wild guess at the solution. Player 1 should pick all >possible choices with probability 1/(n * (n-1) /2 ).
No.
For example, player 1 should never choose the pair (1,n). >Player 2 should switch if player 2's first choice <= n/2.
No, that's not correct. >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.
Try the case n=3 and you'll see your proposed optimal strategies are not correct -- not even close.
quasi
|
|