Author |
Topic: Winning Strategy (Read 653 times) |
|
Ronno
Junior Member
Gender: 
Posts: 140
|
 |
Winning Strategy
« on: Mar 2nd, 2009, 12:09am » |
 Quote  Modify
|
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?
|
| « Last Edit: Mar 2nd, 2009, 12:10am by Ronno » |
 IP Logged |
Sarchasm: The gulf between the author of sarcastic wit and the person who doesn't get it..
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Winning Strategy
« Reply #1 on: Mar 2nd, 2009, 12:55am » |
Quote Modify
|
Obviously, there is not winning stragegy for 2 players. Both will play 1 every round.
|
| « Last Edit: Mar 2nd, 2009, 12:55am by Grimbal » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Winning Strategy
« Reply #2 on: Mar 2nd, 2009, 1:11am » |
Quote Modify
|
on Mar 2nd, 2009, 12:09am, 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
|
| « Last Edit: Mar 2nd, 2009, 1:12am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Winning Strategy
« Reply #3 on: Mar 2nd, 2009, 3:18am » |
Quote Modify
|
on Mar 2nd, 2009, 1:11am, 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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Winning Strategy
« Reply #4 on: Mar 2nd, 2009, 3:46am » |
Quote Modify
|
on Mar 2nd, 2009, 3:18am, 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Ronno
Junior Member
Gender:
Posts: 140
|
|
Re: Winning Strategy
« Reply #5 on: Mar 2nd, 2009, 7:57am » |
Quote Modify
|
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).
|
|
IP Logged |
Sarchasm: The gulf between the author of sarcastic wit and the person who doesn't get it..
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Winning Strategy
« Reply #6 on: Mar 2nd, 2009, 8:59am » |
Quote Modify
|
on Mar 2nd, 2009, 3:18am, 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.
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Winning Strategy
« Reply #7 on: Mar 2nd, 2009, 11:52am » |
Quote Modify
|
It's 0 won divided by 0 nondiscarded.
|
|
IP Logged |
|
|
|
River Phoenix
Junior Member
Gender:
Posts: 125
|
|
Re: Winning Strategy
« Reply #8 on: Mar 2nd, 2009, 5:25pm » |
Quote Modify
|
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
|
| « Last Edit: Mar 2nd, 2009, 5:26pm by River Phoenix » |
IP Logged |
|
|
|
Ronno
Junior Member
Gender:
Posts: 140
|
|
Re: Winning Strategy
« Reply #9 on: Mar 2nd, 2009, 6:56pm » |
Quote Modify
|
Could you explain your answer, River Phoenix?
And what are Nash Equilibria?
|
|
IP Logged |
Sarchasm: The gulf between the author of sarcastic wit and the person who doesn't get it..
|
|
|
Ronno
Junior Member
Gender:
Posts: 140
|
|
Re: Winning Strategy
« Reply #11 on: Mar 2nd, 2009, 7:25pm » |
Quote Modify
|
Why would it be interesting if there are Nash equilibria over non-symmetric strategies?
|
|
IP Logged |
Sarchasm: The gulf between the author of sarcastic wit and the person who doesn't get it..
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print