The Lemonade Stand Game

2009 2010 2011 2012 Forum Code The Future

2012 Competition

Deadline is 11:59 PM Samoa Time, July 15th

The Future of Small-Scale Multi-agent Competitions

July 27, 2012

DIMACS, Rutgers University

Where is this competition going? Join us to find out!

INTRODUCTION

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.

UTILITIES

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.