Author |
Topic: Game of Greed : more choices (Read 1233 times) |
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Game of Greed : more choices
« on: Dec 4th, 2004, 1:48pm » |
Quote Modify
|
You are one of the twenty participants in the TV show known under the name "Greed!". The show is to reach its climax: a total of 1 million dollar is to be distributed amongst you and the 19 other participants. This works as follows: All 20 candidates can bid for their share of the 1 million. They all have to make their bid simultaneously and without having any communication. Once a bid is made the participant has committed to pay the bid amount. In return, the 1 million will be distributed amongst the twenty participants proportional to the amount bid by each individual. The minimum bid is $ 0.01, and one can make any higher bids using steps of $ 0.01. There is no maximum to the amount one can bid. If all 20 candidates happen to bid the same amount, the 1 million gets split equally amongst them, so that each gets $ 50,000. They also each have to pay their bid, so that they all leave the show with a net amount of $ 50,000 minus the bid amount. In particular, if all twenty candidates bid $ 0.01, all twenty will leave the show with a big smile and $ 49,999.99 in their pocket. However, if one or more candidate bids higher than the others, they will receive a proportionaly larger fraction of the 1 million. For instance, if 19 candidates bid $ 0.01 and one candidate bids $ 0.06, the total amount bid is $ 0.25, and for each $ 0.01 bid the participants will receive 1/25th part of the 1 million or $ 40,000. So the 19 low-bidders will each receive $ 40,000 (taking into account the $ 0.01 bid, leaving each of them with a net gain of $ 39,999.99) and the single high bidder will receive $ 240,000 (taking into account the $ 0.06 bid, leaving him/her with a net gain of $ 239,999,94). Got it? OK, take a deep breath and think hard - there is a lot of money at stake.... What is your bid?
|
« Last Edit: Dec 4th, 2004, 2:46pm by JocK » |
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: Game of Greed : more choices
« Reply #1 on: Dec 5th, 2004, 11:14am » |
Quote Modify
|
Douglas R Hofstadter's Scientific American Column, "Metamagical Themas", ran this game, without limiting it to 20 participants, but rather allowing anyone who cared to enter before the deadline to do so. The prize was also determined slightly differently - something like $1,000,000 divided by the winning bid. His book of the collected columns has details of the outcome as well as the original offer, but I think ThreeHands has his copy with him... Anyway, it's probably better to hold off on revealing the answers until after everyone has had plenty of chance to vote - besides, JocK presumably has something in mind.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Game of Greed : more choices
« Reply #2 on: Dec 5th, 2004, 12:07pm » |
Quote Modify
|
Hofstadter's "Luring Lottery" was similar to this, and perhaps the same strategies apply, but there were a number of differences. I may be a bit rusty on the details (I read it when he offered it, rather than finding it in a collection), but it went like this: Douglas got the editors of Sci Am (he was the first successor to Martin Gardener, but only signed up for a limited run) to agree to run a sweepstakes ("Luring Lottery", although there was no cost to enter other than postage) according to the following rules: (1) Anyone could enter as many times as they wanted. In fact, they could simply write how many entries they wanted to make on a postcard. (2) The prize would be $1,000,000 divided by the total number of entries. (3) There would be only one winner, chosen so that each participant's chance of winning was propotional to the number of entries they made. I too will hold off stating the outcome, but frankly, it isn't hard to guess...
|
|
IP Logged |
"Pi goes on and on and on ... And e is just as cursed. I wonder: Which is larger When their digits are reversed? " - Anonymous
|
|
|
towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Game of Greed : more choices
« Reply #3 on: Dec 5th, 2004, 12:17pm » |
Quote Modify
|
Everyone's gain is bid * (prize total / total bids - 1) Which will likely be positive if nobody overbids. And relatively speaking, the higher people bid the less they get To be frank, I seem to be rather risk-averse (though less so then at least one other person) Not that there is actually anything at stake, I could have bid a million for all anyone cares
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: Game of Greed : more choices
« Reply #4 on: Dec 5th, 2004, 12:29pm » |
Quote Modify
|
on Dec 5th, 2004, 12:07pm, Icarus wrote:Hofstadter's "Luring Lottery" was similar to this, and perhaps the same strategies apply, but there were a number of differences. I may be a bit rusty on the details (I read it when he offered it, rather than finding it in a collection), but it went like this: Douglas got the editors of Sci Am (he was the first successor to Martin Gardener, but only signed up for a limited run) to agree to run a sweepstakes ("Luring Lottery", although there was no cost to enter other than postage) according to the following rules: (1) Anyone could enter as many times as they wanted. In fact, they could simply write how many entries they wanted to make on a postcard. (2) The prize would be $1,000,000 divided by the total number of entries. (3) There would be only one winner, chosen so that each participant's chance of winning was propotional to the number of entries they made. I too will hold off stating the outcome, but frankly, it isn't hard to guess... |
| That's the one.
|
|
IP Logged |
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: Game of Greed : more choices
« Reply #5 on: Dec 5th, 2004, 12:39pm » |
Quote Modify
|
on Dec 5th, 2004, 12:17pm, towr wrote:Everyone's gain is bid * (prize total / total bids - 1) ... Not that there is actually anything at stake, I could have bid a million for all anyone cares |
| Well, if you bid a million, you cause total bids > prize total and hence a net loss for all, with the person with the biggest loss being the highest bidder.... and that is...?
|
|
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Game of Greed : more choices
« Reply #6 on: Dec 5th, 2004, 12:53pm » |
Quote Modify
|
on Dec 5th, 2004, 12:39pm, JocK wrote:and hence a net loss for all |
| Yes, but I won't actually have to pay, since it is just a silly internet game That's why experiments involving this kind of research usually offer real prizes; that way there really is something at stake.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: Game of Greed : more choices
« Reply #7 on: Dec 5th, 2004, 12:54pm » |
Quote Modify
|
on Dec 5th, 2004, 12:07pm, Icarus wrote:Hofstadter's "Luring Lottery" was similar to this, and perhaps the same strategies apply, but there were a number of differences. I may be a bit rusty on the details (I read it when he offered it, rather than finding it in a collection), but it went like this: Douglas got the editors of Sci Am (he was the first successor to Martin Gardener, but only signed up for a limited run) to agree to run a sweepstakes ("Luring Lottery", although there was no cost to enter other than postage) according to the following rules: (1) Anyone could enter as many times as they wanted. In fact, they could simply write how many entries they wanted to make on a postcard. (2) The prize would be $1,000,000 divided by the total number of entries. (3) There would be only one winner, chosen so that each participant's chance of winning was propotional to the number of entries they made. I too will hold off stating the outcome, but frankly, it isn't hard to guess... |
| Let me guess... a postcard came in from a teaser... a card that mentioned Graham's number as the number of entries? The current game is a bit more subtle... rational (selfish) play leaves a win for all participants. Although this gain is considerably less than the optimal cooperative gain, it is still significant.
|
|
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Game of Greed : more choices
« Reply #8 on: Dec 5th, 2004, 6:40pm » |
Quote Modify
|
Actually, many postcards came in with that sort of response. If I recall, he said that Avagodro's number was most common. But a significant number came in, in which the person attempted to express the largest finite number they could on a postcard, such as 9!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! !!!!!!!!!! !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! !!!!!!!!!!!... and so on until the card was filled. This resulted in his follow-up article being about strategies to write the largest possible number with a set number of symbols. I recall that he indicated the most effective approach was to use a variety of symbolisms, rather than a single one like the factorials above, but I no longer remember why this was so. As for the Luring Lottery, he declared that since the winning prize would be smaller than the smallest subatomic particle within a penny, that he would forgo attempting to pick a winner.
|
|
IP Logged |
"Pi goes on and on and on ... And e is just as cursed. I wonder: Which is larger When their digits are reversed? " - Anonymous
|
|
|
Grimbal
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Game of Greed : more choices
« Reply #9 on: Dec 6th, 2004, 4:53am » |
Quote Modify
|
I believe with Hofstadter's Lottery, there was no participation fee. I computed that the best strategy is to bet as much as the total of all other entries, which explains the race to large numbers. The real gain then became to be picked as a winner, even without a payout, and have his name printed in a reputed international magazine. Anyway, I though I should send a card with 0 entries. This way I would have an almost zero (but not exactly zero) chance of being the only participant to send a card, and win an amount of ($1M/0). "Almost zero" chances times $1M/0 is infinite, so it is still a nice payout. Of course, there is almost no chance the editors would interpret it like that, but as long as it is almost, it is worth the try.
|
|
IP Logged |
|
|
|
Three Hands
Uberpuzzler
Gender:
Posts: 715
|
|
Re: Game of Greed : more choices
« Reply #10 on: Dec 6th, 2004, 11:05am » |
Quote Modify
|
Hofstadter's recommended method for anyone deciding whether to enter the Luring Lottery would be: First, work out how many people will be aware, and thus be able to enter, the Luring Lottery. Then work out a suitable amount for how much you would consider worthwhile winning, and how much that would divide the total prize-fund by. This then gives you the number of people you want to enter, work out what fraction of the set of people who could enter is, and then randomly determine (through dice-rolling or coin-flipping, or other such random methods) whether you should enter by setting the probability of you entering at the 1:x value you can derive from the fraction you'd previously worked out. If you come up with the result of "ENTER", then you submit one entry, otherwise you do not enter. Granted, there was no official participation fee, but there was the cost of getting a postcard to the appropriate location, which (given the result) left everyone who entered with a net loss. Suffice to say, Hofstadter suspected that the majority of his readers did not do this...
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Game of Greed : more choices
« Reply #11 on: Dec 7th, 2004, 2:03am » |
Quote Modify
|
This method assumes that every single person participating in the lottery collaborates to maximize the collective payout, regardless of who earns it. Assuming at least one person is greedy enough to send at least one entry, the best method to maximize the collective payout is to refrain from sending any more entry.
|
|
IP Logged |
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: Game of Greed : more choices
« Reply #12 on: Dec 7th, 2004, 2:36pm » |
Quote Modify
|
OK... the poll has now closed. Let's discuss the strategy: is there an optimal strategy? (The responses to the poll do not suggest so, but there really is a unique optimal bid available...!)
|
|
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Game of Greed : more choices
« Reply #13 on: Dec 7th, 2004, 2:45pm » |
Quote Modify
|
The optimal strategy is to meditate and find enlightenment
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: Game of Greed : more choices
« Reply #14 on: Dec 7th, 2004, 6:02pm » |
Quote Modify
|
on Dec 7th, 2004, 2:36pm, JocK wrote:(The responses to the poll do not suggest so, but there really is a unique optimal bid available...!) |
| What assumptions do you have to arrive to arrive at that unique bid? I claim that the unique optimal bid is 1 cent (assuming that everyone knows that everyoneknows that everyone knows that [...] everyone is rational - so will make the same "best" decision)
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Game of Greed : more choices
« Reply #15 on: Dec 8th, 2004, 1:43am » |
Quote Modify
|
on Dec 7th, 2004, 2:36pm, JocK wrote:(The responses to the poll do not suggest so, but there really is a unique optimal bid available...!) |
| ::47500:: ?
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: Game of Greed : more choices
« Reply #16 on: Dec 8th, 2004, 1:23pm » |
Quote Modify
|
Correct Towr! (why did you avoid that bid in the poll..? )
|
|
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Game of Greed : more choices
« Reply #17 on: Dec 8th, 2004, 1:48pm » |
Quote Modify
|
Well, as you can see in the poll, some people bid over 50.000. And if the total of the bids goes over the total prize money we all end up paying the hosts. So I was being risk averse. It's only the 'optimum' if everybody else chooses it. A gain of P/N2 isn't very good compared to the 'irrational' gain of P/N if everyone cooperates (or just blissfully naively assumes people are fair)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: Game of Greed : more choices
« Reply #18 on: Dec 8th, 2004, 3:31pm » |
Quote Modify
|
on Dec 8th, 2004, 1:48pm, towr wrote: It's only the 'optimum' if everybody else chooses it. |
| Well, it is the optimum even if no others choose it, as long as it is chosen on average. For the game under discussion, the 'Nash bid' actually outperforms any lower bid as long as the average bid of the 19 others exceeds $2500. So you need only one 'Nash-bidder' amongst the 19 others to prevent you from regretting in hindsight that you didn't make a lower bid. The poll clearly shows that the average bid in practice tends to be way above $2500. But yes, I should be more careful with the word 'optimum' in this context! The Nash bid is the optimum bid assuming rational play of all participants. (Some might want to replace the word 'rational' in above sentence with the word 'sharkish'... )
|
« Last Edit: Dec 8th, 2004, 3:37pm by JocK » |
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Game of Greed : more choices
« Reply #19 on: Dec 9th, 2004, 12:39am » |
Quote Modify
|
on Dec 8th, 2004, 3:31pm, JocK wrote:For the game under discussion, the 'Nash bid' actually outperforms any lower bid as long as the average bid of the 19 others exceeds $2500. |
| It may outperform lower bids, but not higher ones. For any total of bids from the other participants there is an optimum bid.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: Game of Greed : more choices
« Reply #20 on: Dec 9th, 2004, 12:42pm » |
Quote Modify
|
on Dec 9th, 2004, 12:39am, towr wrote:It may outperform lower bids, but not higher ones. For any total of bids from the other participants there is an optimum bid. |
| Indeed, for any given total of bids from the other N-1 participants there is an optimum bid for you. But if a bid is optimum for you, it should also be optimum for all other players. So, finding an optimum bid for you given the sum of the bids of the others is not enough to get to the best strategy: the optimum bid also needs to satisfy the equilibrium condition - the bid needs to be optimal not only for you but for all players, in such a way that none of the players can improve his/her net gain by changing his/her bid). There is only one bid that satisfies these conditions, and that is the bid given by yourself towr... [ For the N players game with a total prize money of P this equilibrium bid is a fraction 1/N below the 'break even bid': (1 - 1/N)P/N. ]
|
« Last Edit: Dec 9th, 2004, 12:44pm by JocK » |
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
|