The University of Southampton

Sparkling victory for ECS researchers in Lemonade Game

Published: 28 January 2010
Illustration

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.

Articles that may also interest you

Share this article FacebookTwitterWeibo