Blotto games
Encyclopedia
Blotto games constitute a class of two-person zero-sum games in which the players are tasked to simultaneously distribute limited resources over several objects (or battlefields). In the classic version of the game, the player devoting the most resources to a battlefield wins that battlefield, and the gain (or payoff) is then equal to the total number of battlefields won.
Though the Colonel Blotto game was first proposed by Borel in 1921, most variations of the classic game remained unsolved for 85 years. In 2006, Roberson described the equilibrium payoffs to the classic game for any number of battlefields, and any level of relative resources, as well as characterizing the set of equilibrium to most versions of the classic game.
The game is named after the fictional Colonel Blotto from Gross and Wagner's 1950 paper. The Colonel was tasked with finding the optimum distribution of his soldiers over N battlefields knowing that:
For S = 6 only three choices of numbers are possible: (2, 2, 2), (1, 2, 3) and (1, 1, 4). It is easy to see that:
against (1, 2, 3) is a draw against (2, 2, 2) is a draw against (2, 2, 2) is a draw beats (1, 1, 4)
It follows that the optimum strategy is (2, 2, 2) as it does not do worse than breaking even against any other strategy while beating one other strategy. There are however several Nash equilibria. If both players choose the strategy (2, 2, 2) or (1, 2, 3), then none of them can beat the other one by changing strategies, so every such strategy pair is a Nash equilibrium
.
For larger S the game becomes progressively more difficult to analyse. For S = 12, it can be shown that (2, 4, 6) represents the optimal strategy, while for S > 12, deterministic strategies fail to be optimal. For S = 13, choosing (3, 5, 5), (3, 3, 7) and (1, 5, 7) with probability 1/3 each can be shown to be the optimal probabilistic strategy.
, one of the closest races in recent history, has been modeled as a Colonel Blotto game. It is argued that Gore could have utilized a strategy that would have won the election, but that such a strategy was not identifiable ex ante.
Though the Colonel Blotto game was first proposed by Borel in 1921, most variations of the classic game remained unsolved for 85 years. In 2006, Roberson described the equilibrium payoffs to the classic game for any number of battlefields, and any level of relative resources, as well as characterizing the set of equilibrium to most versions of the classic game.
The game is named after the fictional Colonel Blotto from Gross and Wagner's 1950 paper. The Colonel was tasked with finding the optimum distribution of his soldiers over N battlefields knowing that:
- on each battlefield the party that has allocated the most soldiers will win, but
- both parties do not know how many soldiers the opposing party will allocate to each battlefield, and:
- both parties seek to maximize the number of battlefields they expect to win.
Example
As an example Blotto game, consider the game in which two players each write down three positive integers in non-decreasing order and such that they add up to a pre-specified number S. Subsequently, the two players show each other their writings, and compare corresponding numbers. The player who has two numbers higher than the corresponding ones of the opponent wins the game.For S = 6 only three choices of numbers are possible: (2, 2, 2), (1, 2, 3) and (1, 1, 4). It is easy to see that:
against (1, 2, 3) is a draw against (2, 2, 2) is a draw against (2, 2, 2) is a draw beats (1, 1, 4)
It follows that the optimum strategy is (2, 2, 2) as it does not do worse than breaking even against any other strategy while beating one other strategy. There are however several Nash equilibria. If both players choose the strategy (2, 2, 2) or (1, 2, 3), then none of them can beat the other one by changing strategies, so every such strategy pair is a Nash equilibrium
Nash equilibrium
In game theory, Nash equilibrium is a solution concept of a game involving two or more players, in which each player is assumed to know the equilibrium strategies of the other players, and no player has anything to gain by changing only his own strategy unilaterally...
.
For larger S the game becomes progressively more difficult to analyse. For S = 12, it can be shown that (2, 4, 6) represents the optimal strategy, while for S > 12, deterministic strategies fail to be optimal. For S = 13, choosing (3, 5, 5), (3, 3, 7) and (1, 5, 7) with probability 1/3 each can be shown to be the optimal probabilistic strategy.
Application
The 2000 US presidential electionUnited States presidential election, 2000
The United States presidential election of 2000 was a contest between Republican candidate George W. Bush, then-governor of Texas and son of former president George H. W. Bush , and Democratic candidate Al Gore, then-Vice President....
, one of the closest races in recent history, has been modeled as a Colonel Blotto game. It is argued that Gore could have utilized a strategy that would have won the election, but that such a strategy was not identifiable ex ante.
External links
- Ayala Arad and Ariel Rubinstein's article Colonel Blotto's Top secret Files: Multi-Dimensional Iterative Reasoning in Action
- Jonathan PartingtonJonathan PartingtonJonathan R. Partington is an English mathematician.-Education:Professor Partington was educated at Gresham's School, Holt, and Trinity College, University of Cambridge, where he completed his PhD thesis entitled "Numerical ranges and the Geometry of Banach Spaces" under the supervision of Béla...
's Colonel Blotto page