Blotto game

Last updated

A Blotto game, Colonel Blotto game, or divide-a-dollar game is a type of two-person zero-sum game 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.

In game theory and economic theory, a zero-sum game is a mathematical representation of a situation in which each participant's gain or loss of utility is exactly balanced by the losses or gains of the utility of the other participants. If the total gains of the participants are added up and the total losses are subtracted, they will sum to zero. Thus, cutting a cake, where taking a larger piece reduces the amount of cake available for others, is a zero-sum game if all participants value each unit of cake equally.

Contents

The Colonel Blotto game was first proposed and solved by Émile Borel [1] in 1921, as an example of a game in which "the psychology of the players matters". It was studied after the Second World War by scholars in Operation Research, and became a classic in game theory. [2] It has been shown that finding a Min-Max equilibrium, or in other words, the optimal strategies of this game is computationally tractable. [3] [4]

Émile Borel French mathematician and politician

Félix Édouard Justin Émile Borel was a French mathematician and politician. As a mathematician, he was known for his founding work in the areas of measure theory and probability.

Game theory is the study of mathematical models of strategic interaction among rational decision-makers. It has applications in all fields of social science, as well as in logic, systems science, and computer science. Originally, it addressed zero-sum games, in which each participant's gains or losses are exactly balanced by those of the other participants. Today, game theory applies to a wide range of behavioral relations, and is now an umbrella term for the science of logical decision making in humans, animals, and computers.

Minimax is a decision rule used in artificial intelligence, decision theory, game theory, statistics and philosophy for minimizing the possible loss for a worst case scenario. When dealing with gains, it is referred to as "maximin"—to maximize the minimum gain. Originally formulated for two-player zero-sum game theory, covering both the cases where players take alternate moves and those where they make simultaneous moves, it has also been extended to more complex games and to general decision-making in the presence of uncertainty.

The game is named after the fictional Colonel Blotto from Gross and Wagner's 1950 [5] paper. The Colonel was tasked with finding the optimum distribution of his soldiers over N battlefields knowing that:

  1. on each battlefield the party that has allocated the most soldiers will win, but
  2. neither party knows how many soldiers the opposing party will allocate to each battlefield, and:
  3. 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:

Any triplet against itself is a draw
(1, 1, 4) against (1, 2, 3) is a draw
(1, 2, 3) against (2, 2, 2) is a draw
(2, 2, 2) 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.

In game theory, the Nash equilibrium, named after the mathematician John Forbes Nash Jr., is a proposed solution of a non-cooperative 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 their own strategy.

For larger S the game becomes progressively more difficult to analyze. 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.

Borel's game is similar to the above example for very large S, but the players are not limited to round integers. They thus have an infinite number of available pure strategies, indeed a continuum.

This concept is also implemented in a story of Sun Bin when watching a chariot race with three different races running concurrently. In the races each party had the option to have one chariot team in each race, and each chose to use a strategy of 1, 2, 3 (with 3 being the fastest chariot and 1 being the slowest) to deploy their chariots between the three races creating close wins in each race and few sure outcomes on the winners. When asked how to win Sun Bin advised the chariot owner to change his deployment to that of 2, 3, 1. Though he would be sure to lose the race against the fastest chariots (the 3 chariots); he would win each of the other races, with his 3 chariot easily beating 2 chariots and his 2 chariot beating the 1 chariots.

Sun Bin was a Chinese general, military strategist, and writer who lived during the Warring States period of Chinese history. A supposed descendant of Sun Tzu, Sun Bin was tutored in military strategy by the hermit Guiguzi. He was accused of treason while serving in the Wei state and was sentenced to face-tattooing and had his kneecaps removed, permanently crippling him. Sun escaped from Wei later and rose to prominence in the Qi state, by serving as a military strategist and commander. He led Qi to victory against the Wei state at the Battle of Guiling and Battle of Maling. Sun authored the military treatise Sun Bin's Art of War, which was rediscovered in a 1972 archaeological excavation after being lost for almost 2000 years.

Application

This game is commonly used as a metaphor for electoral competition, with two political parties devoting money or resources to attract the support of a fixed number of voters. [6] [7] Each voter is a "battlefield" that can be won by one or the other party. The same game also finds application in auction theory where bidders must make simultaneous bids. [8]

Several variations on the original game have been solved by Jean-François Laslier, [9] Brian Roberson, [10] Dmitriy Kvasov. [11] .

See also

Related Research Articles

The game of chicken, also known as the hawk–dove game or snowdrift game, is a model of conflict for two players in game theory. The principle of the game is that while it is to both players’ benefit if one player yields, the other player's optimal choice depends on what their opponent is doing: if the player opponent yields, they should not, but if the opponent fails to yield, the player should.

In game theory, the best response is the strategy which produces the most favorable outcome for a player, taking other players' strategies as given. The concept of a best response is central to John Nash's best-known contribution, the Nash equilibrium, the point at which each player in a game has selected the best response to the other players' strategies.

In game theory, coordination games are a class of games with multiple pure strategy Nash equilibria in which players choose the same or corresponding strategies.

In game theory, a player's strategy is any of the options which he or she chooses in a setting where the outcome depends not only on their own actions but on the actions of others. A player's strategy will determine the action which the player will take at any stage of the game.

In game theory, battle of the sexes (BoS) is a two-player coordination game. Some authors refer to the game as Bach or Stravinsky and designate the players simply as Player 1 and Player 2, rather than assigning sex.

In game theory, a Perfect Bayesian Equilibrium (PBE) is an equilibrium concept relevant for dynamic games with incomplete information. A PBE is a refinement of both Bayesian Nash equilibrium (BNE) and subgame perfect equilibrium (SPE). A PBE has two components - strategies and beliefs:

Backward induction is the process of reasoning backwards in time, from the end of a problem or situation, to determine a sequence of optimal actions. It proceeds by first considering the last time a decision might be made and choosing what to do in any situation at that time. Using this information, one can then determine what to do at the second-to-last time of decision. This process continues backwards until one has determined the best action for every possible situation at every point in time. It was first used by Zermelo in 1913, to prove that chess has pure optimal strategies.

In game theory, a repeated game is an extensive form game that consists of a number of repetitions of some base game. The stage game is usually one of the well-studied 2-person games. Repeated games capture the idea that a player will have to take into account the impact of his or her current action on the future actions of other players; this impact is sometimes called his or her reputation. Single stage game or single shot game are names for non-repeated games.

In game theory, a correlated equilibrium is a solution concept that is more general than the well known Nash equilibrium. It was first discussed by mathematician Robert Aumann in 1974. The idea is that each player chooses their action according to their observation of the value of the same public signal. A strategy assigns an action to every possible observation a player can make. If no player would want to deviate from the recommended strategy, the distribution is called a correlated equilibrium.

In game theory, an outcome is a situation which results from a combination of player's strategies. Every combination of strategies is an outcome of the game. A primary purpose of game theory is to determine which outcomes are stable according to a solution concept.

In game theory, the purification theorem was contributed by Nobel laureate John Harsanyi in 1973. The theorem aims to justify a puzzling aspect of mixed strategy Nash equilibria: that each player is wholly indifferent amongst each of the actions he puts non-zero weight on, yet he mixes them so as to make every other player also indifferent.

In game theory, a subgame perfect equilibrium is a refinement of a Nash equilibrium used in dynamic games. A strategy profile is a subgame perfect equilibrium if it represents a Nash equilibrium of every subgame of the original game. Informally, this means that if the players played any smaller game that consisted of only one part of the larger game, their behavior would represent a Nash equilibrium of that smaller game. Every finite extensive game with perfect recall has a subgame perfect equilibrium.

In game theory, an epsilon-equilibrium, or near-Nash equilibrium, is a strategy profile that approximately satisfies the condition of Nash equilibrium. In a Nash equilibrium, no player has an incentive to change his behavior. In an approximate Nash equilibrium, this requirement is weakened to allow the possibility that a player may have a small incentive to do something different. This may still be considered an adequate solution concept, assuming for example status quo bias. This solution concept may be preferred to Nash equilibrium due to being easier to compute, or alternatively due to the possibility that in games of more than 2 players, the probabilities involved in an exact Nash equilibrium need not be rational numbers.

In descriptive set theory, the Borel determinacy theorem states that any Gale–Stewart game whose payoff set is a Borel set is determined, meaning that one of the two players will have a winning strategy for the game.

In algorithmic game theory, a succinct game or a succinctly representable game is a game which may be represented in a size much smaller than its normal form representation. Without placing constraints on player utilities, describing a game of players, each facing strategies, requires listing utility values. Even trivial algorithms are capable of finding a Nash equilibrium in a time polynomial in the length of such a large input. A succinct game is of polynomial type if in a game represented by a string of length n the number of players, as well as the number of strategies of each player, is bounded by a polynomial in n.

Mertens stability is a solution concept used to predict the outcome of a non-cooperative game. A tentative definition of stability was proposed by Elon Kohlberg and Jean-François Mertens for games with finite numbers of players and strategies. Later, Mertens proposed a stronger definition that was elaborated further by Srihari Govindan and Mertens. This solution concept is now called Mertens stability, or just stability.

Maximal lotteries refers to a probabilistic voting system first considered by the french mathematician and social scientist Germain Kreweras in 1965. The method uses preferential ballots and returns so-called maximal lotteries, i.e., probability distributions over the alternatives that are weakly preferred to any other probability distribution. Maximal lotteries satisfy the Condorcet criterion, the Smith criterion, reversal symmetry, polynomial runtime, and probabilistic versions of reinforcement, participation, and independence of clones.

References

  1. The Theory of Play and Integral Equations with Skew Symmetric Kernels (1953 translation from the French paper "La théorie du jeu et les équations intégrales à noyau symétrique gauche")
  2. Guillermo Owen, Game Theory, Academic Press (1968)
  3. mewright. "UMD-led Team First to Solve Well-known Game Theory Scenario". College of Computer, Mathematical, and Natural Sciences. Retrieved 2016-03-29.
  4. Ahmadinejad, Mahdi; Dehghani, Sina; Hajiaghayi, MohammadTaghi; Lucier, Brendan; Mahini, Hamid; Seddighin, Saeed (2016). "From Duels to Battefields: Computing Equilibria of Blotto and Other Games". arXiv: 1603.00119 [cs.GT].
  5. A Continuous Colonel Blotto Game
  6. R. Myerson "Incentives to cultivate favored minorities under alternative electoral systems" American Political Science Review 87(4):856—869, 1993
  7. Laslier, J.-F.; Picard, N. (2002). "Distributive politics and electoral competition". Journal of Economic Theory. 103: 106–130. doi:10.1006/jeth.2000.2775.
  8. Szentes, B.; Rosenthal, R. (2003). "Three-object, Two-Bidder Simultaneous Auctions: Chopsticks and Tetrahedra". Games and Economic Behavior. 44: 114–133. doi:10.1016/s0899-8256(02)00530-4.
  9. J.-F. Laslier, "Party objectives in the `divide a dollar’ electoral competition" in: Social Choice and Strategic Decisions, Essays in Honor of Jeff Banks, edited by D. Austen–Smith and J. Duggan, Springer, pp. 113–130 (2005)
  10. B. Roberson, The Colonel Blotto game
  11. Kvasov, D. (2007). "Contests with Limited Resources". Journal of Economic Theory. 136: 738–748. doi:10.1016/j.jet.2006.06.007.