The University of Southampton

Sparkling victory for ECS researchers in Lemonade Game

28 January 2010

A team of three researchers from the School of Electronics and Computer Science defeated agents designed by researchers from Princeton University, Brown University, Rutgers University, Carnegie Mellon University and the University of Michigan to win the inaugural Lemonade Game Tournament, contested on the Web earlier this month and run by Yahoo! researcher Martin Zinkevich.

The ECS researchers, Enrique Munoz de Cote, Archie Chapman and Adam Sykulski, are based in the Intelligence, Agents, Multimedia research group. The game is set on Lemonade Island, and the aim is to set up your lemonade stall as far from the other players as possible. But the island is circular ... The task is to design an agent that could recognise a collaborator in a repeated three-player zero-sum game (the Lemonade Game). In the rules of the game, the agent must cooperate with the collaborator in order to defeat the unlucky third player. However, the agents are not able to communicate directly with one another, so they must indicate their willingness to collaborate by signalling, using the actions that they play in the game.

The approach taken by the ECS researchers was to classify the style of behaviour that other agents in the game are playing, and to use this to rank their potential as collaborators. Then, using game—theoretic reasoning, the agent would play a combination of actions that would hopefully indicate to the highest ranked agent that it would like to cooperate with it. The technique proved successful, and the researchers are improving their agent for the next running of the tournament.

Enrique, Archie and Adam all investigate problems arising at the intersection between multiagent systems, game theory, optimization and machine learning. Enrique has developed algorithms for solving stochasitc and extensive form games, Archie has investigated game-theoretic models of optimization problems and algorithms for solving them, while Adam has examined policies for learning in finite multi-armed bandits and noisy games.

Share this article FacebookGoogle+TwitterWeibo

We use cookies to ensure that we give you the best experience on our website. If you continue without changing your settings, we will assume that you are happy to receive cookies on the University of Southampton website.