Sunday, February 14, 2016

Game Theory's Colonel Blotto Scenario Solved

From EurekAlert:

UMD-led team first to solve well-known game theory scenario 
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....MORE
HT: Economist's View

But, if interested, see also "Game Theory Is Useful, Except When It Isn't"