One of my cousins asked me this question: Suppose 3 people make secret guesses of a number, uniformly randomly chosen from 1--100. Whoever is closest wins. What is their "best" strategy? I'd like to modify this to let the unknown number to be uniformly chosen real number in [0,1]. In the event of ties, let's say the winner is chosen uniformly from all best guesses (or the "prize" is distributed equally, I don't care). By "best", I want a Nash optimal probability distribution for the guesses of the the three participants --- that is, if each one knows the probabilities with which the others choose their guess, they can do no better than using the same distribution. Note that with two guessers, a guess of .5 wins over everything except another guess of .5, when it ties. For 3 guessers, it's not optimal for all three to pick .5, because .49 then wins against the other two. It's also not optimal to pick a number uniformly at random from the unit interval: if two of the players do that a guess of .5 has an expectation of 5/12. Bill Thurston
Bill -- How do you deal with collusion? If Dylan and I agree to pool our winnings, surely we want to bracket your guess and box you out entirely, if we can. --Michael On Tue, Jul 12, 2011 at 9:56 PM, Bill Thurston <wpthurston@mac.com> wrote:
One of my cousins asked me this question: Suppose 3 people make secret guesses of a number, uniformly randomly chosen from 1--100. Whoever is closest wins. What is their "best" strategy?
I'd like to modify this to let the unknown number to be uniformly chosen real number in [0,1]. In the event of ties, let's say the winner is chosen uniformly from all best guesses (or the "prize" is distributed equally, I don't care). By "best", I want a Nash optimal probability distribution for the guesses of the the three participants --- that is, if each one knows the probabilities with which the others choose their guess, they can do no better than using the same distribution.
Note that with two guessers, a guess of .5 wins over everything except another guess of .5, when it ties.
For 3 guessers, it's not optimal for all three to pick .5, because .49 then wins against the other two. It's also not optimal to pick a number uniformly at random from the unit interval: if two of the players do that a guess of .5 has an expectation of 5/12.
Bill Thurston
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush.
I'm interested in the simpified situation: let's say that the guessers make sealed choices without communicating ahead of time. Nonetheless, as a secondary question, it would be interesting if you can describe a good collusion strategy whereby the colluders have probability each greater than 1/3. If there's a unique Nash equilibrium, all three players need to have the same distribution, but it's possible that there are asymmetric equilibrium distributions or even optimal distributions where the three players have three different distributions. But, I'd be happy to see the "best" solution where all three pick the same distribution. Bill On Jul 12, 2011, at 10:04 PM, Michael Kleber wrote:
Bill -- How do you deal with collusion? If Dylan and I agree to pool our winnings, surely we want to bracket your guess and box you out entirely, if we can.
--Michael
On Tue, Jul 12, 2011 at 9:56 PM, Bill Thurston <wpthurston@mac.com> wrote:
One of my cousins asked me this question: Suppose 3 people make secret guesses of a number, uniformly randomly chosen from 1--100. Whoever is closest wins. What is their "best" strategy?
I'd like to modify this to let the unknown number to be uniformly chosen real number in [0,1]. In the event of ties, let's say the winner is chosen uniformly from all best guesses (or the "prize" is distributed equally, I don't care). By "best", I want a Nash optimal probability distribution for the guesses of the the three participants --- that is, if each one knows the probabilities with which the others choose their guess, they can do no better than using the same distribution.
Note that with two guessers, a guess of .5 wins over everything except another guess of .5, when it ties.
For 3 guessers, it's not optimal for all three to pick .5, because .49 then wins against the other two. It's also not optimal to pick a number uniformly at random from the unit interval: if two of the players do that a guess of .5 has an expectation of 5/12.
Bill Thurston
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
It turns out that the uniform distribution on the interval [1/4,3/4] does the trick. Martin Osborne and Carolyn Pitchik proved this back in 1982. Link to paper: http://cowles.econ.yale.edu/P/cd/d06a/d0628.pdf See Proposition 3 for the relevant statement. (I haven't checked their proof, but I did check that the given distribution has the desired properties.) Jakob Jonsson ________________________________________ Från: math-fun-bounces@mailman.xmission.com [math-fun-bounces@mailman.xmission.com] för Bill Thurston [wpthurston@mac.com] Skickat: den 13 juli 2011 04:18 Till: math-fun Kopia: Chung-chieh Shan; Dylan Thurston Ämne: Re: [math-fun] Guessing game I'm interested in the simpified situation: let's say that the guessers make sealed choices without communicating ahead of time. Nonetheless, as a secondary question, it would be interesting if you can describe a good collusion strategy whereby the colluders have probability each greater than 1/3. If there's a unique Nash equilibrium, all three players need to have the same distribution, but it's possible that there are asymmetric equilibrium distributions or even optimal distributions where the three players have three different distributions. But, I'd be happy to see the "best" solution where all three pick the same distribution. Bill On Jul 12, 2011, at 10:04 PM, Michael Kleber wrote:
Bill -- How do you deal with collusion? If Dylan and I agree to pool our winnings, surely we want to bracket your guess and box you out entirely, if we can.
--Michael
On Tue, Jul 12, 2011 at 9:56 PM, Bill Thurston <wpthurston@mac.com> wrote:
One of my cousins asked me this question: Suppose 3 people make secret guesses of a number, uniformly randomly chosen from 1--100. Whoever is closest wins. What is their "best" strategy?
I'd like to modify this to let the unknown number to be uniformly chosen real number in [0,1]. In the event of ties, let's say the winner is chosen uniformly from all best guesses (or the "prize" is distributed equally, I don't care). By "best", I want a Nash optimal probability distribution for the guesses of the the three participants --- that is, if each one knows the probabilities with which the others choose their guess, they can do no better than using the same distribution.
Note that with two guessers, a guess of .5 wins over everything except another guess of .5, when it ties.
For 3 guessers, it's not optimal for all three to pick .5, because .49 then wins against the other two. It's also not optimal to pick a number uniformly at random from the unit interval: if two of the players do that a guess of .5 has an expectation of 5/12.
Bill Thurston
Thanks for finding the reference, Jakob! I couldn't figure out how to find relevant literature. We did figure this one out after posting it, but I held back to give others a chance to think about it. For four guessers, if there were a solution that is a uniform distribution on an interval, it would turn out that the interval would need to be [1/6, 5/6]. Once the first three have guessed according to a uniform distribution on some interval, the expectation of winning for the fourth guesser, for any choice in that itnerval, needs to be .25, otherwise they could improve their odds by guessing a particular value, since the average expectation for guesses in that interval is .25, by symmetry. An easy computation shows that the only possible interval is [1/6, 5/6]. But a calculation of the expectation of winning for fourth guesses in that interval is not uniform: Here's a link to a plot of the expectation function for a fourth guess in the interval [1/6, 5/6], done with mathematica. It's a fourth-degree polynomial, with maxima at the points 1/30(15 +- 2 sqrt(15)) having slightly increased odds of winning of 25.8045%. We haven't calculated the corresponding Nash equilibrium. It seems likely to be a transcendental function, which one should be able to find numerically by an iterative procedure by changing your strategy in the direction of the deviation of the expectation of fourth guesses from the uniform distribution. Probably one should start with a distribution that is uniform in the interval [1/6,5/6], but is never 0, because the support of the final answer is may be an interval different from this. I'd like to mention also, following up on Michael Kleber's remark, that there are collusion strategies that work. If the Michael and Dylan can secretly agree to always pick 1/4 and 3/4, respectively, the then I, even knowing their strategy, can do no better than picking 1/4 or 3/4 at random. Resolution of the tie by a coin flip gives me an interval of length .25, while Dylan and Michael have the remaining total length of .75, so by splitting winnings, or just letting multiple times playing the game, gives each .375 of the winnings. This configuration is not a Nash Equilibrium, however, because if the strategies remain fixed except that Michael decides to break from the collusion, he can increase his odds by moving his guess toward Dylan's. The reference you cite claims that there are no other equilibria subject to some regularity assumption, but I haven't checked the reasoning. Bill Thurston On Jul 14, 2011, at 11:10 PM, Jakob Jonsson wrote:
It turns out that the uniform distribution on the interval [1/4,3/4] does the trick. Martin Osborne and Carolyn Pitchik proved this back in 1982. Link to paper:
http://cowles.econ.yale.edu/P/cd/d06a/d0628.pdf
See Proposition 3 for the relevant statement. (I haven't checked their proof, but I did check that the given distribution has the desired properties.)
Jakob Jonsson
________________________________________ Från: math-fun-bounces@mailman.xmission.com [math-fun-bounces@mailman.xmission.com] för Bill Thurston [wpthurston@mac.com] Skickat: den 13 juli 2011 04:18 Till: math-fun Kopia: Chung-chieh Shan; Dylan Thurston Ämne: Re: [math-fun] Guessing game
I'm interested in the simpified situation: let's say that the guessers make sealed choices without communicating ahead of time. Nonetheless, as a secondary question, it would be interesting if you can describe a good collusion strategy whereby the colluders have probability each greater than 1/3. If there's a unique Nash equilibrium, all three players need to have the same distribution, but it's possible that there are asymmetric equilibrium distributions or even optimal distributions where the three players have three different distributions. But, I'd be happy to see the "best" solution where all three pick the same distribution. Bill On Jul 12, 2011, at 10:04 PM, Michael Kleber wrote:
Bill -- How do you deal with collusion? If Dylan and I agree to pool our winnings, surely we want to bracket your guess and box you out entirely, if we can.
--Michael
On Tue, Jul 12, 2011 at 9:56 PM, Bill Thurston <wpthurston@mac.com> wrote:
One of my cousins asked me this question: Suppose 3 people make secret guesses of a number, uniformly randomly chosen from 1--100. Whoever is closest wins. What is their "best" strategy?
I'd like to modify this to let the unknown number to be uniformly chosen real number in [0,1]. In the event of ties, let's say the winner is chosen uniformly from all best guesses (or the "prize" is distributed equally, I don't care). By "best", I want a Nash optimal probability distribution for the guesses of the the three participants --- that is, if each one knows the probabilities with which the others choose their guess, they can do no better than using the same distribution.
Note that with two guessers, a guess of .5 wins over everything except another guess of .5, when it ties.
For 3 guessers, it's not optimal for all three to pick .5, because .49 then wins against the other two. It's also not optimal to pick a number uniformly at random from the unit interval: if two of the players do that a guess of .5 has an expectation of 5/12.
Bill Thurston
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
A similar question, which I remember knowing the answer to at some point, but now have forgotten, concerns the following game: N players independently select positive integers; the game is won by the player who picks the smallest integer that nobody else picked. What is the Nash equilibrium strategy? (If every choice is selected by more than one player, nobody wins.) On Fri, Jul 15, 2011 at 6:47 AM, Bill Thurston <wpthurston@mac.com> wrote:
Thanks for finding the reference, Jakob! I couldn't figure out how to find relevant literature.
We did figure this one out after posting it, but I held back to give others a chance to think about it. For four guessers, if there were a solution that is a uniform distribution on an interval, it would turn out that the interval would need to be [1/6, 5/6]. Once the first three have guessed according to a uniform distribution on some interval, the expectation of winning for the fourth guesser, for any choice in that itnerval, needs to be .25, otherwise they could improve their odds by guessing a particular value, since the average expectation for guesses in that interval is .25, by symmetry. An easy computation shows that the only possible interval is [1/6, 5/6]. But a calculation of the expectation of winning for fourth guesses in that interval is not uniform: Here's a link to a plot of the expectation function for a fourth guess in the interval [1/6, 5/6], done with mathematica. It's a fourth-degree polynomial, with maxima at the points 1/30(15 +- 2 sqrt(15)) having slightly increased odds of winning of 25.8045%. We haven't calculated the corresponding Nash equilibrium. It seems likely to be a transcendental function, which one should be able to find numerically by an iterative procedure by changing your strategy in the direction of the deviation of the expectation of fourth guesses from the uniform distribution. Probably one should start with a distribution that is uniform in the interval [1/6,5/6], but is never 0, because the support of the final answer is may be an interval different from this. I'd like to mention also, following up on Michael Kleber's remark, that there are collusion strategies that work. If the Michael and Dylan can secretly agree to always pick 1/4 and 3/4, respectively, the then I, even knowing their strategy, can do no better than picking 1/4 or 3/4 at random. Resolution of the tie by a coin flip gives me an interval of length .25, while Dylan and Michael have the remaining total length of .75, so by splitting winnings, or just letting multiple times playing the game, gives each .375 of the winnings. This configuration is not a Nash Equilibrium, however, because if the strategies remain fixed except that Michael decides to break from the collusion, he can increase his odds by moving his guess toward Dylan's. The reference you cite claims that there are no other equilibria subject to some regularity assumption, but I haven't checked the reasoning.
Bill Thurston
On Jul 14, 2011, at 11:10 PM, Jakob Jonsson wrote:
It turns out that the uniform distribution on the interval [1/4,3/4] does the trick. Martin Osborne and Carolyn Pitchik proved this back in 1982. Link to paper:
http://cowles.econ.yale.edu/P/cd/d06a/d0628.pdf
See Proposition 3 for the relevant statement. (I haven't checked their proof, but I did check that the given distribution has the desired properties.)
Jakob Jonsson
________________________________________ Från: math-fun-bounces@mailman.xmission.com [ math-fun-bounces@mailman.xmission.com] för Bill Thurston [ wpthurston@mac.com] Skickat: den 13 juli 2011 04:18 Till: math-fun Kopia: Chung-chieh Shan; Dylan Thurston Ämne: Re: [math-fun] Guessing game
I'm interested in the simpified situation: let's say that the guessers make sealed choices without communicating ahead of time. Nonetheless, as a secondary question, it would be interesting if you can describe a good collusion strategy whereby the colluders have probability each greater than 1/3. If there's a unique Nash equilibrium, all three players need to have the same distribution, but it's possible that there are asymmetric equilibrium distributions or even optimal distributions where the three players have three different distributions. But, I'd be happy to see the "best" solution where all three pick the same distribution. Bill On Jul 12, 2011, at 10:04 PM, Michael Kleber wrote:
Bill -- How do you deal with collusion? If Dylan and I agree to pool our winnings, surely we want to bracket your guess and box you out entirely, if we can.
--Michael
On Tue, Jul 12, 2011 at 9:56 PM, Bill Thurston <wpthurston@mac.com> wrote:
One of my cousins asked me this question: Suppose 3 people make secret guesses of a number, uniformly randomly chosen from 1--100. Whoever is closest wins. What is their "best" strategy?
I'd like to modify this to let the unknown number to be uniformly chosen real number in [0,1]. In the event of ties, let's say the winner is chosen uniformly from all best guesses (or the "prize" is distributed equally, I don't care). By "best", I want a Nash optimal probability distribution for the guesses of the the three participants --- that is, if each one knows the probabilities with which the others choose their guess, they can do no better than using the same distribution.
Note that with two guessers, a guess of .5 wins over everything except another guess of .5, when it ties.
For 3 guessers, it's not optimal for all three to pick .5, because .49 then wins against the other two. It's also not optimal to pick a number uniformly at random from the unit interval: if two of the players do that a guess of .5 has an expectation of 5/12.
Bill Thurston
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I like this one: Two players pick positive integers. Whoever picks the lesser one wins $1 from the other, unless he happens to pick an integer exactly one less than his opponent's number, in which case he pays $2 to his opponent, instead. If they happen to pick the same number, no money changes hands. Like Allan, I'd welcome information about the origin of this problem. I think the Nash equilibrium involves playing no number larger than 6 (maybe 5?). On Sat, Jul 16, 2011 at 3:58 PM, Allan Wechsler <acwacw@gmail.com> wrote:
A similar question, which I remember knowing the answer to at some point, but now have forgotten, concerns the following game:
N players independently select positive integers; the game is won by the player who picks the smallest integer that nobody else picked. What is the Nash equilibrium strategy? (If every choice is selected by more than one player, nobody wins.)
On Fri, Jul 15, 2011 at 6:47 AM, Bill Thurston <wpthurston@mac.com> wrote:
Thanks for finding the reference, Jakob! I couldn't figure out how to find relevant literature.
We did figure this one out after posting it, but I held back to give others a chance to think about it. For four guessers, if there were a solution that is a uniform distribution on an interval, it would turn out that the interval would need to be [1/6, 5/6]. Once the first three have guessed according to a uniform distribution on some interval, the expectation of winning for the fourth guesser, for any choice in that itnerval, needs to be .25, otherwise they could improve their odds by guessing a particular value, since the average expectation for guesses in that interval is .25, by symmetry. An easy computation shows that the only possible interval is [1/6, 5/6]. But a calculation of the expectation of winning for fourth guesses in that interval is not uniform: Here's a link to a plot of the expectation function for a fourth guess in the interval [1/6, 5/6], done with mathematica. It's a fourth-degree polynomial, with maxima at the points 1/30(15 +- 2 sqrt(15)) having slightly increased odds of winning of 25.8045%. We haven't calculated the corresponding Nash equilibrium. It seems likely to be a transcendental function, which one should be able to find numerically by an iterative procedure by changing your strategy in the direction of the deviation of the expectation of fourth guesses from the uniform distribution. Probably one should start with a distribution that is uniform in the interval [1/6,5/6], but is never 0, because the support of the final answer is may be an interval different from this. I'd like to mention also, following up on Michael Kleber's remark, that there are collusion strategies that work. If the Michael and Dylan can secretly agree to always pick 1/4 and 3/4, respectively, the then I, even knowing their strategy, can do no better than picking 1/4 or 3/4 at random. Resolution of the tie by a coin flip gives me an interval of length .25, while Dylan and Michael have the remaining total length of .75, so by splitting winnings, or just letting multiple times playing the game, gives each .375 of the winnings. This configuration is not a Nash Equilibrium, however, because if the strategies remain fixed except that Michael decides to break from the collusion, he can increase his odds by moving his guess toward Dylan's. The reference you cite claims that there are no other equilibria subject to some regularity assumption, but I haven't checked the reasoning.
Bill Thurston
On Jul 14, 2011, at 11:10 PM, Jakob Jonsson wrote:
It turns out that the uniform distribution on the interval [1/4,3/4] does the trick. Martin Osborne and Carolyn Pitchik proved this back in 1982. Link to paper:
http://cowles.econ.yale.edu/P/cd/d06a/d0628.pdf
See Proposition 3 for the relevant statement. (I haven't checked their proof, but I did check that the given distribution has the desired properties.)
Jakob Jonsson
________________________________________ Från: math-fun-bounces@mailman.xmission.com [ math-fun-bounces@mailman.xmission.com] för Bill Thurston [ wpthurston@mac.com] Skickat: den 13 juli 2011 04:18 Till: math-fun Kopia: Chung-chieh Shan; Dylan Thurston Ämne: Re: [math-fun] Guessing game
I'm interested in the simpified situation: let's say that the guessers make sealed choices without communicating ahead of time. Nonetheless, as a secondary question, it would be interesting if you can describe a good collusion strategy whereby the colluders have probability each greater than 1/3. If there's a unique Nash equilibrium, all three players need to have the same distribution, but it's possible that there are asymmetric equilibrium distributions or even optimal distributions where the three players have three different distributions. But, I'd be happy to see the "best" solution where all three pick the same distribution. Bill On Jul 12, 2011, at 10:04 PM, Michael Kleber wrote:
Bill -- How do you deal with collusion? If Dylan and I agree to pool our winnings, surely we want to bracket your guess and box you out entirely, if we can.
--Michael
On Tue, Jul 12, 2011 at 9:56 PM, Bill Thurston <wpthurston@mac.com> wrote:
One of my cousins asked me this question: Suppose 3 people make secret guesses of a number, uniformly randomly chosen from 1--100. Whoever is closest wins. What is their "best" strategy?
I'd like to modify this to let the unknown number to be uniformly chosen real number in [0,1]. In the event of ties, let's say the winner is chosen uniformly from all best guesses (or the "prize" is distributed equally, I don't care). By "best", I want a Nash optimal probability distribution for the guesses of the the three participants --- that is, if each one knows the probabilities with which the others choose their guess, they can do no better than using the same distribution.
Note that with two guessers, a guess of .5 wins over everything except another guess of .5, when it ties.
For 3 guessers, it's not optimal for all three to pick .5, because .49 then wins against the other two. It's also not optimal to pick a number uniformly at random from the unit interval: if two of the players do that a guess of .5 has an expectation of 5/12.
Bill Thurston
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Thane Plambeck tplambeck@gmail.com http://counterwave.com/
participants (5)
-
Allan Wechsler -
Bill Thurston -
Jakob Jonsson -
Michael Kleber -
Thane Plambeck