wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Winning Strategy
        
(Message started by: ronnodas on Mar 2nd, 2009, 12:09am)
Title: Winning Strategy
Post by ronnodas on Mar 2nd, 2009, 12:09am
N persons each secretly pick a positive integer. The choices are then compared and the person who picks the lowest number not chosen by anyone else wins. If no one picks a unique number, that round is discarded. Consider each player using the same strategy.

1. Is there a winning strategy for this game?
2. Is there a strategy that wins with probability at least 1/N when discarded rounds are counted?
3. Is there a strategy that wins with probability at least 1/N when discarded rounds are NOT counted?
Title: Re: Winning Strategy
Post by Grimbal on Mar 2nd, 2009, 12:55am
Obviously, there is not winning stragegy for 2 players.  Both will play 1 every round.
Title: Re: Winning Strategy
Post by towr on Mar 2nd, 2009, 1:11am

on 03/02/09 at 00:09:35, ronnodas wrote:
1. Is there a winning strategy for this game?
Obviously not, since all the other players can play the same strategy.
Except when you play alone.


Quote:
2. Is there a strategy that wins with probability at least 1/N when discarded rounds are counted?
Same as above. They each have the same probability of winning, and there is a positive probability of discarded rounds.


Quote:
3. Is there a strategy that wins with probability at least 1/N when discarded rounds are NOT counted?
If they all play the same strategy, they have the same chance of winning, so ignoring discarded rounds, that's 1/N
Title: Re: Winning Strategy
Post by Hippo on Mar 2nd, 2009, 3:18am

on 03/02/09 at 01:11:05, towr wrote:
If they all play the same strategy, they have the same chance of winning, so ignoring discarded rounds, that's 1/N


But as mentioned by Grimbal, for N=2 case all rounds are discarded so there is division by zero.
Title: Re: Winning Strategy
Post by towr on Mar 2nd, 2009, 3:46am

on 03/02/09 at 03:18:44, Hippo wrote:
But as mentioned by Grimbal, for N=2 case all rounds are discarded so there is division by zero.
If anyone wins, they have an equal chance of winning. Which is trivially true because nobody wins, and also because the game is symmetric.
Title: Re: Winning Strategy
Post by ronnodas on Mar 2nd, 2009, 7:57am
If a strategy exists that can ensure win or discarded round, and if everyone just uses that, then by that knowledge, one player can easily win (assuming n>2).
Title: Re: Winning Strategy
Post by Grimbal on Mar 2nd, 2009, 8:59am

on 03/02/09 at 03:18:44, Hippo wrote:
But as mentioned by Grimbal, for N=2 case all rounds are discarded so there is division by zero.

In fact it is still correct.  It's not a division by 0 because N is the number of players, which is 2 in this case.  Everybody still wins 1/N on the rounds that were not discarded.  It is just there aren't any.
Title: Re: Winning Strategy
Post by Hippo on Mar 2nd, 2009, 11:52am
It's 0 won divided by 0 nondiscarded.
Title: Re: Winning Strategy
Post by River Phoenix on Mar 2nd, 2009, 5:25pm
the equilibrium is just going to be a distribution of the form:

play the number 1, 2, ... , i, ..., N/2 with probability p_i

surely p_i > p_i+1 for all i

EDIT: the interesting thought is there may be nash equilbria over nonsymmetric strategies
Title: Re: Winning Strategy
Post by ronnodas on Mar 2nd, 2009, 6:56pm
Could you explain your answer, River Phoenix?

And what are Nash Equilibria?
Title: Re: Winning Strategy
Post by ThudanBlunder on Mar 2nd, 2009, 7:03pm

on 03/02/09 at 18:56:52, ronnodas wrote:
And what are Nash Equilibria?

http://www.gametheory.net/dictionary/NashEquilibrium.html
Title: Re: Winning Strategy
Post by ronnodas on Mar 2nd, 2009, 7:25pm
Why would it be interesting if there are Nash equilibria over non-symmetric strategies?


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board