The Lemonade Stand Game: 2010 Competition
- January 15th, 2011: Finalize 2011 Rules
- June 2011: Generalized Lemonade Stand Game
March 1st, 2011
In ACM SIGecom Exchanges 10.1, Michael Bowling, Michael Wunder, and I published the results from the first two competitions. The letter is available here.
I would like to add a publication list to this site, so please let me know if I may post a copy of you LSG-related papers here. Thank you!
December 15th, 2010
New bots are available in the code section.
The 2010 Competition was the most popular Lemonade Stand game competition so far with 9 teams playing! With the University of Alberta, the University of Arizona, and Georgia Tech joining teams from previous years, I expect a great deal of interesting results.
That being said, we need to start the discussions on the forum for next year's competition's rules. There have been a variety of games suggested, and I have gotten some great ideas from many of you. Here are some highlights:
What other thoughts do people have? What are the big questions that people feel can be answered in the context of this competition? Let me know!
- It is time to generalize, but we need to be careful.
- A distribution over games is a good step forward
- Communication is something people want to see in the future
- The visual representation of the game is quite helpful, and it may be too early to abandon it.
- There are other ways of ranking the players that provide different motivations, such as allowing self-play or using equilibrium-based ranking.
Imagine the following game. It is summer on Lemonade Island, and you need to make some cash. You decide to set up a lemonade stand on the beach (which goes all around the island), as do two others. There are twelve places to set up around the island like the numbers on a clock. Your price is fixed, and all people go to the nearest lemonade stand.
The game is repeated. Every night, everyone moves under cover of darkness (simultaneously) and in the morning, their locations are fixed. There is no cost to move. After 100 days of summer, the game is over. The utility of the repeated game is the sum of the utilities of single-shot games.
If all the lemonade stands are located at different spots, then your utility is the distance to the person clockwise you plus the distance to the person counterclockwise you, measured in spots.
For example, if Alice sets up at 3 o'clock location, Bob sets up at the 10 o'clock location, and Candy sets up at 6 o'clock, then first we arrange them clockwise from 1 o'clock (Alice, Candy, then Bob): there are 3 spots clockwise between Alice and Candy, 4 spots clockwise between Candy and Bob, and 5 spots clockwise between Bob and Alice. Therefore, Alice gets $8, Bob gets $9, and Candy gets $7.
If all the lemonade stands are located at the same spot, everybody gets $8.
If exactly two lemonade stands are located at the same spot, the two collocated stands get $6 each and the loner gets $12.
So, the total utility is always $24.
SIMPLE, YET HARD
"Listen, here's the thing, if you can't spot the sucker in your first half hour at the table, then you are the sucker." - Rounders
The game has almost no structure. Probability theory and the theory of Nash equilibria do not provide a single solution to this game, but can you?
And yet, it is frighteningly hard: state-of-the art online algorithms fail when up against a simple strategy.