A team of researchers, including three from the University of Maryland have developed the first all-encompassing algorithm to conquer a classic game-theory scenario.
The game, called the Colonel Blotto game, involves battlefields that can be literal, as in a war scenario, or figurative, with any situation involving two or more competing forces, said Mohammad Hajiaghayi, a computer science professor and lead researcher on the project. In this case, the algorithm accounts for just two competing forces.
The team reported their findings at the Association for the Advancement of Artificial Intelligence Conference in Phoenix in February.
“These battlefields can be real or virtual … and for different battlefields, you can invest different amounts of money or spend resources differently,” Hajiaghayi said.
For example, in a Microsoft-versus-Google scenario, both companies would be competing against each other in different product areas, such as email, search engines and computer programs, said Saeed Seddighin, a computer science graduate student and member of the research team.
“Both will be willing to spend some amount of their budget on these products,” Seddighin said. “The question is how best they can manage their products to reach customers.”
One of the most famous battlefield scenarios is the presidential election, Hajiaghayi said. Each state would be a battlefield, and the candidates need to play differently in each, spending different amounts of money and utilizing resources to try to gain more voters.
“And just like on a regular battlefield, somebody wins,” he said. “With Microsoft and Google, someone wins by getting the attention of the most customers, or in the election, someone wins by getting the most votes.”
In the Colonel Blotto game, players spend their resources, having no idea what the strategy of the other player might be. Even a player with fewer resources can win if they can assign their resources in a more important battlefield. That’s what the researchers were trying to analyze, Hajiaghayi said.
“In practice, our algorithm provides optimal strategies for resource management in competitions or conflict situations,” said Sina Dehghani, a computer science doctoral student and team member.
The point is to provide helpful tools for predicting competition outcomes, he said.
“We take the total resources you have and then for each of these battlefields, you need to allocate some amount of each resource,” Hajiaghayi said. “We [provide] what would be your best strategy.”
Seddighin said they created the algorithm so anyone could use it on virtually any problem.
Other researchers have worked with this game scenario in the past, Hajiaghayi said, but mostly focusing on very specific scenarios that would yield a very singular solution. Before now, no one had considered the general case, he said.
“But that’s the beauty of computer science: We don’t care about the case. We give an algorithm that can consider any case and give the best solution,” Hajiaghayi said. “Previously, each scenario had to be specifically evaluated. … We just say, ‘This is the algorithm. Take it and solve it yourself.'”
Looking ahead, Hajiaghayi said, they plan to continue to try and expand the algorithm to work in scenarios involving multiple battlefields and more than two rivals.
In the meantime, the upcoming election might be a good test of the algorithm’s usefulness. Hajiaghayi said he actually started thinking about the problem during the previous election.
“If somebody asks us, it can be applied to this election,” Hajiaghayi said, “but so far nobody has asked us.”
