Team first to solve well-known game theory scenario

February 11, 2016

A team of computer scientists from the University of Maryland, Stanford University and Microsoft Research is the first to solve a game theory scenario that has vexed researchers for nearly a century. The game, known as "Colonel Blotto," has been used to analyze the potential outcomes of elections and other similar two-party conflicts since its invention in 1921. Until now, however, the game has been of limited use because it lacked a definitive solution.

A new algorithm developed by the UMD-led team is capable of solving the Colonel Blotto scenario. A notable achievement in its own right, the algorithm could also provide political strategists, business leaders and other decision-makers with a powerful new tool for making informed choices. The team will report its findings at the Association for the Advancement of Artificial Intelligence (AAAI) Conference in Phoenix on February 15, 2016.

"Our algorithm can potentially be used to compute the best resource investment strategy for any competitor up against a single opponent," said Mohammad Hajiaghayi, the Jack and Rita G. Minker Associate Professor of Computer Science at UMD and lead on the project. "As long as we have sufficient data on a given scenario, we can use our algorithm to find the best strategy for a wide variety of leaders, such as political candidates, sports teams, companies and military leaders."

Colonel Blotto pits two competitors against one another and requires each to make difficult decisions on how to deploy limited resources. In its simplest form, each player assigns a limited number of resources, or troops, to a number of battlefields. Players must do this without any knowledge of their opponent's strategy. Players win a given battlefield if they allocate more troops than their opponent; the player who wins the most battlefields also wins the game.

The game can be extended to real-world scenarios, such as a U.S. presidential general election. In this example, each candidate is a player; resources such as campaign staff, stump time and funding are the troops; and each state is a battlefield. The game can also apply to high-profile consumer product competition, such as the ongoing battle between Apple's iPhone and Google's Android mobile phone products.

"From presidential elections to marketing decisions, competition for attention and loyalty is a part of daily life. However, the behavior of individuals in response to such competitions is not yet well understood," said Hajiaghayi, who also holds a joint appointment at the University of Maryland Institute for Advanced Computer Studies (UMIACS). "We show that such strategic behavior is computationally tractable. Given a description of the competition, we can determine which strategies will maximize the outcomes for a given player."

Although the rules of Colonel Blotto are relatively simple, the potential strategies a player can employ are nearly limitless, depending on the number of battlefields and the total resources available to each player. The solution achieved by Hajiaghayi and his colleagues does not necessarily favor one player over another, but rather represents an equilibrium in which both players have deployed the best strategy they possibly can in relation to their opponent's strategy.

The large variety of possible strategies has been the key obstacle to finding a computational solution to the game. Hajiaghayi and his team overcame this issue by limiting the total number of possible strategies to a relative handful of representative choices.

"We found that the strategies of the players can be accurately represented by a reasonably small number of possibilities," Hajiaghayi said. "This is a more general approach, but it works well as a proof-of-concept. Many others have tried to solve Colonel Blotto for specific scenarios, but we are the first to take a more general approach and solve the theory."

This solution enabled the team to develop a generalized algorithm, which can now be applied to specific scenarios, such as the 2016 presidential election.

"Our algorithm only works for two competitors, so we will need to wait for the general election to try this," said Saeed Seddighin, a graduate student in computer science at UMD who will present the group's findings at the AAAI meeting. "If we know how a given state voted in previous elections relative to the resources each candidate invested in that state, then we can use the same investment data from this year's election cycle to predict whether each candidate has deployed his or her best possible strategy nationwide."

Explore further: Evolving our way to artificial intelligence

More information: The study, "From Duels to Battlefields: Computing Equilibria of Blotto and Other Games," AmirMahdi Ahmadinejad, Sina Dehghani, MohammadTaghi Hajiaghayi, Brendan Lucier, Hamid Mahini and Saeed Seddighin, will be presented on February 15, 2016, at the Association for the Advancement of Artificial Intelligence (AAAI) Conference in Phoenix, Arizona.

Related Stories

Evolving our way to artificial intelligence

February 5, 2016

Researcher David Silver and colleagues designed a computer program capable of beating a top-level Go player – a marvelous technological feat and important threshold in the development of artificial intelligence, or AI. ...

How to apply game theory to buying your Christmas presents

December 21, 2015

According to Sheldon from The Big Bang Theory, if someone is buying you a Christmas gift then the "essence of the custom is that I now have to go out and purchase for you a gift of commensurate value and representing the ...

How to clean up space debris – using game theory

November 13, 2015

A piece of debris just 10cm in diameter could cause an entire spacecraft to disintegrate and it is estimated that there are more than 29,000 objects larger than 10cm in Earth's orbit. This poses a major risk to the spacecraft ...

Too many candidates spoil the stew

September 11, 2015

This election year has produced 17 Republican presidential candidates, which on its surface may appear to give the party a competitive advantage. Evolution, however, disagrees.

Recommended for you

Swiss unveil stratospheric solar plane

December 7, 2016

Just months after two Swiss pilots completed a historic round-the-world trip in a Sun-powered plane, another Swiss adventurer on Wednesday unveiled a solar plane aimed at reaching the stratosphere.

Solar panels repay their energy 'debt': study

December 6, 2016

The climate-friendly electricity generated by solar panels in the past 40 years has all but cancelled out the polluting energy used to produce them, a study said Tuesday.

Wall-jumping robot is most vertically agile ever built

December 6, 2016

Roboticists at UC Berkeley have designed a small robot that can leap into the air and then spring off a wall, or perform multiple vertical jumps in a row, resulting in the highest robotic vertical jumping agility ever recorded. ...

1 comment

Adjust slider to filter visible comments by rank

Display comments: newest first

BartV
5 / 5 (1) Feb 11, 2016
Too bad some people view political elections as a game to be played. Maybe that is why so many people choose to be cynical and go with the extremes of Bernie or Trump.

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.