Well-known game theory scenario solved
Source: University of Maryland
A team of computer scientists 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 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.
"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."
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.
This work was supported by the National Science Foundation (Award Nos. 1053605 and CCF-1161626), the Office of Naval Research (Award No. N000141110662), the Defense Advanced Research Projects Agency (Award No. FA9550-12-1-0423) and Google. The content of this article does not necessarily reflect the views of these organizations.
| }
|