Abstract
We investigate a version of the classic Colonel Blotto game in which individual battlefields may have different values. Two players allocate a fixed discrete budget across battlefields. Each battlefield is won by the player who allocates the most to that battlefield. The player who wins the battlefields with highest total value receives a constant winner payoff, while the other player receives a constant loser payoff. We focus on apex games, in which there is one large and several small battlefields. A player wins if he wins the large and any one small battlefield, or all the small battlefields. For each of the games we study, we compute an equilibrium and we show that certain properties of equilibrium play are the same in any equilibrium. In particular, the expected share of the budget allocated to the large battlefield exceeds its value relative to the total value of all battlefields, and with a high probability (exceeding 90 % in our treatments) resources are spread over more battlefields than are needed to win the game. In a laboratory experiment, we find that strategies that spread resources widely are played frequently, consistent with equilibrium predictions. In the treatment where the asymmetry between battlefields is strongest, we also find that the large battlefield receives on average more than a proportional share of resources. In a control treatment, all battlefields have the same value and our findings are consistent with previous experimental findings on Colonel Blotto games.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
Young describes the lobbying game in which lobbyists have infinitely divisible budgets. He then states that “Instead of attempting to compute [the expected allocation of the lobbyists’ budget to each voter] explicitly by integration, a useful approach is to approximate the continuous strategy spaces by a finite grid. A natural way to do this is by allocating a large but finite number u of indivisible units to each lobbyist that may be distributed among the voters. This leads to a two-person, zero-sum matrix game whose equilibrium solutions were used to approximate the equilibrium solution to the infinite lobbying game.” He then states, without giving further details of the derivations, the resulting values.
Dechenaux et al. (2014) survey the experimental literature on contests more generally.
Arad and Rubinstein (2012) also study a game with an auction CSF and budget-constrained use-it-or-lose-it costs using a round-robin tournament in which each subject’s allocation is pitted against everybody else’s. They observe significant deviations from equilibrium and interpret subjects’ choices as reflecting iterated reasoning in several dimensions. Note, however, that their subjects play a one-shot game, with no opportunity for learning.
Another related paper is Hortala-Vallve and Llorente-Saguer (2010). They consider a modification of the Colonel Blotto game with an additive objective in which the two players have cardinal valuations of the battlefields, and these valuations are private information. Their main focus is on the efficiency of the outcome, an issue that does not arise in our setting.
Constant-sum games have a well-defined value, so all equilibria of a constant-sum game yield the same payoffs to the players. Symmetric games always have at least one equilibrium that is symmetric, and a symmetric equilibrium in this game necessarily results in each player winning with probability one-half.
One thing we know is that results for the additive objective game with a continuously divisible budget do not carry over to majoritarian objective games. Take \({{\mathbf {v}}} = (2, 1, 1, 1)\) and suppose the budget E = 5 is continuously divisible. Consider any strategy such that the amount allocated to the first battlefield is uniformly distributed between 0 and 4, and the amount allocated to each of the other battlefields is uniformly distributed between 0 and 2. Such a strategy constitutes an equilibrium in the additive objective case (Thomas 2013). (For an example of such a strategy draw \(\varepsilon \) from a uniform distribution on the interval [0, 1] and place \(4 - 4 \varepsilon \) units on the large battlefield and assign \(2 \varepsilon , \varepsilon \), and \(1 + \varepsilon \) to the small battlefields where each of the 6 permutations of assignments to small battlefields is equally likely. Note that the total placed on all battlefields is \(4 - 4 \varepsilon + 2 \varepsilon +\varepsilon + 1 + \varepsilon = 5\) and the marginal distribution on each battlefield is uniform.) For the majoritarian objective case, any such strategy can be bettered by a strategy that puts 3 on the first battlefield and 2 on the second. This alternative strategy wins the second battlefield with probability 1, and the first battlefield with probability 3/4, hence it wins with probability 3/4 overall. Analogously, for \({{\mathbf {v}}} = (3, 1, 1, 1, 1)\) and \(E = 7\), any strategy such that the allocation is uniform on [0, 6] for the first battlefield and on [0, 2] for each of the others can be beaten with a probability of at least 5/6, since placing 5 on the first battlefield and 2 on the second would beat it with probability 5/6.
Note that \({\hat{X}}\) does not correspond to the set of all object-symmetric strategies in \(\Gamma \); this set would correspond to \(\Delta ({\hat{X}})\).
For example, in the game APEX3 (a degenerate apex game where \({{\mathbf {v}}} = (1, 1, 1)\)) with an endowment \(E = 5\) analyzed in the “Appendix” of the working paper Montero et al. (2013), consider both players randomizing equally between the three pure strategies (3,2,0), (0,3,2), and (2,0,3). This strategy combination is an equilibrium of the game but is not object-symmetric, since there are three other permutations, namely (3,0,2), (0,2,3) and (2,3,0), that are not being used. This equilibrium is in fact part of a continuum of equilibria which place probability 1 on the permutations of (3,2,0), and the equilibrium set does include the object-symmetric case where all six permutations are given equal probability.
Instructions for one of the treatments can be found in “Appendix 2”.
In the instructions and on-screen we did not use the “battlefield” terminology, but rather referred to “objects.”
If a subject timed out, the computer made a default decision allocating zero tokens to each battlefield. Across all sessions only 28 out of 6660 allocation decisions resulted in a timeout.
At an early stage of our research, we also ran some sessions with a budget of 5 indivisible units. This permitted identification of equilibrium benchmarks without resorting to numerical methods. See Montero et al. (2013) for details.
This is equivalent to a test against equilibrium for APEX3. For tests against equilibrium in APEX4 and APEX5, all p values are less than 0.0005.
Again, this echoes previous experimental findings. Chowdhury et al. (2013) also observe mild positional order effects (see their table 3 and figure 3).
Hart (2008, p.454, Case 2.1) provides an equilibrium strategy for this game with the additive objective; due to the equivalence of the additive and majoritarian objectives in this case, the strategy is also an equilibrium in our setting. The strategy involves uniform marginals on even numbers only; in our case on \(\{0,2,4,...,80\}\). The probability of a minimal winning strategy is then \(3/41 \approx 7\,\%\), since each of the battlefields receives 0 with probability 1/41 and the strategy never puts 0 on more than one battlefield. Other approximately uniform marginal distributions would have a smaller probability of allocating 0 to a battlefield.
A similar result is obtained by Mago and Sheremeta (2012) in a majoritarian contest with linear costs. In their experiment, 35 % of the time subjects bid only on two out of three objects, whereas in equilibrium they should make positive bids on all three.
We also examined the effect of replacing the regressor 1 / t with t. The results are essentially the same: a regression using all the data indicates a significant decrease in the amount allocated to the large battlefield over time, but the trend variable is insignificant when we restrict the regression to the last 15 rounds.
The implied maximum of the concave relation between AllocA and the probability of winning is when 20 % of the budget is allocated to the large battlefield, and two-thirds of the observations allocate more than this to the large battlefield.
Footnote 7 provides, for the continuous case, strategies that achieve winning probability 3/4 for APEX4 and 5/6 for APEX5 against any strategy with uniform marginals on the appropriate intervals. For each strategy with uniform marginals, there may exist strategies that achieve even higher winning probability; 3/4 for APEX4 and 5/6 for APEX5 are thus lower bounds on the exploitability of strategies with uniform marginals in the continuous case. Due to the discreteness of the budget, exploitability values for our games can be below these bounds.
References
Arad, A., Rubinstein, A.: Multi-dimensional iterative reasoning in action: the case of the Colonel Blotto game. J. Econ. Behav. Organ. 84, 475–712 (2012)
Avrahami, J., Kareev, Y.: Do the weak stand a chance? Distribution of resources in a competitive environment. Cogn. Sci. 33, 940–950 (2009)
Avrahami, J., Kareev, Y., Todd, P., Silverman, B.: Allocation of resources in asymmetric competitions: how do the weak maintain a chance of winning? J. Econ. Psychol. 42, 161–174 (2014)
Borel, E.: La théorie du jeu et les équations intégrales à noyau symétrique. Comptes Rendus de l’Académie des Sciences 173, 1304–1308 (1921); English translation: Savage, L.: The theory of play and integral equations with skew symmetric kernels. Econometrica 21, 97–100 (1953)
Borel, E., Ville, J.: Application de la théorie des probabilités aux jeux de hasard. Gauthier-Villars, Paris (1938); reprinted in Borel, E., Cheron, A.: Théorie mathématique du bridge à la portée de tous. Editions Jacques Gabay, Paris (1991)
Chowdhury, S.M., Kovenock, D., Sheremeta, R.M.: An experimental investigation of Colonel Blotto games. Econ. Theory 52, 833–861 (2013)
Dantzig, G.: A proof of the equivalence of the programming problem and the game problem. In: Koopmans, T.C. (ed.) Activity Analysis of Production and Allocation, pp. 330–335. Wiley, New York (1951)
Dechenaux, E., Kovenock, D., Sheremeta, R.M.: A survey of experimental research on contests, all-pay auctions and tournaments. Forthcoming in Exp. Econ. (2014). doi:10.1007/s10683-014-9421-0
Duffy, J., Matros, A.: Stochastic Asymmetric Blotto games: Theory and Evidence. Typescript, University of California, Irvine (2015)
Fischbacher, U.: z-Tree: Zurich toolbox for ready-made economic experiments. Exp. Econ. 10, 171–178 (2007)
Greiner, B.: An online recruitment system for economic experiments. In: Kremer, K., Macho, V. (eds.) Forschung und Wissenschaftliches Rechnen 2003, pp. 79–93. Ges. für Wiss. Datenverarbeitung, GWDG Bericht 63, Göttingen (2004)
Gross, O., Wagner, R.: A Continuous Colonel Blotto Game. RAND Corporation, RM-408, Santa Monica (1950)
Hart, S.: Discrete Colonel Blotto and General Lotto games. Int. J. Game Theory 36, 441–460 (2008)
Hortala-Vallve, R., Llorente-Saguer, A.: A simple mechanism for resolving conflict. Game. Econ. Behav. 70, 375–391 (2010)
Isbell, J.R.: On the enumeration of majority games. Math Tables Other Aids Comput 13, 21–28 (1959)
Kovenock, D., Roberson, B.: Conflicts with multiple battlefields. In: Garfinkel, M.R., Skaperdas, S. (eds.) Oxford Handbook of the Economics of Peace and Conflict, pp. 503–531. Oxford University Press, Oxford (2012)
McKelvey, R., McLennan, A., Turocy, T.: Gambit: Software Tools for Game Theory, Version 13.1.0. http://www.gambit-project.org (2013)
Mago, S.D., Sheremeta, R.M.: Multi-Battle Contests: An Experimental Study. http://ssrn.com/abstract=2027172 (2012)
Montero, M., Possajennikov, A., Sefton, M., Turocy, T.: Majoritarian contests with asymmetric battlefields: an experiment. (2013). doi:10.2139/ssrn.2369056
Roberson, B.: The Colonel Blotto game. Econ. Theory 29, 1–24 (2006)
Stahl, D.O., Wilson, P.W.: On players’ models of other players: theory and experimental evidence. Game. Econ. Behav. 10, 218–254 (1995)
Thomas, C.: N-dimensional Blotto Game with Asymmetric Battlefield Values. Typescript, The University of Texas, Austin (2013)
Walker, M., Wooders, J.: Minimax play at Wimbledon. Am. Econ. Rev. 91, 1521–1538 (2001)
Wooders, J., Shachat, J.: On the irrelevance of risk attitudes in repeated two-outcome games. Game. Econ. Behav. 34, 342–363 (2001)
Young, H.P.: A tactical lobbying game. RR-78-10. International Institute for Applied Systems Analysis, Laxenburg (1978)
Author information
Authors and Affiliations
Corresponding author
Additional information
We thank the co-editor (Dan Kovenock), four anonymous referees, Subhasish Chowdhury, Judith Avrahami, seminar participants at New York University, Keele University, University of East Anglia, University of the Basque Country, and conference participants at the Voting Power in Practice Symposium at LSE 2011, M-BEES 2011, SING7 2011, Contests, Mechanisms and Experiments Conference at Exeter 2012, SAET 2012, GAMES 2012 and ESEM-EEA 2013. The equilibrium computations were carried out on the High Performance Computing Cluster supported by the Research and Specialist Computing Support service at the University of East Anglia.
Appendices
Appendix 1: Computational techniques
The games APEX4 and APEX5, and the corresponding auxiliary games restricting to object-symmetric strategies, are two-player constant-sum symmetric games. As two-player constant-sum games, a minimax strategy, and therefore a Nash equilibrium, can be written as the solution to a linear program (Dantzig 1951). In practice, it is possible to solve linear programs of substantial size. Moreover, because the set of mixed strategy Nash equilibria for two-player constant-sum games is convex, once an equilibrium has been found it is straightforward to explore the whole set of equilibria, and to place tight bounds on the size of this set. In particular, it is in principle possible to verify uniqueness, if one uses exact rational arithmetic. However, doing so is infeasible in our games with large endowments. We instead use floating-point arithmetic for our calculations. For many values of the endowment, we bound all strategy probabilities to within \(10^{-6}\), which suggests the object-symmetric equilibrium is in fact unique.
1.1 Improving computational efficiency
Turning specifically to the games studied in this paper, with a budget of \(E=120\) tokens, the strategy spaces of these games are quite large. Even restricting attention to object-symmetric strategies, APEX4 has 52,311, and APEX5 has 430,256 strategies. However, preliminary explorations with smaller budgets led us to conjecture that equilibria in these games would have small supports. We therefore used an iterative method to identify the set of equilibrium strategies.
Consider the game with a budget of E tokens. Let X be the set of pure-strategy token allocations. We construct an increasing sequence of supports, \(X_0 \subseteq X_1 \subseteq \cdots \subseteq X_\mathrm{T}\), such that \(X_\mathrm{T}\) is the support of an equilibrium of the game. Pick some initial guess at the support of the equilibrium, and call it \(X_0 \subseteq X\). (The correctness of the construction does not depend on the value of the initial guess \(X_0\); for this approach to work efficiently, it should be small in size.)
At each step \(\tau \) of the algorithm, we consider the restriction of the game in which players can choose only strategies in \(X_\tau \). This induces a well-defined two-player constant-sum game, which can be solved for some equilibrium \(\pi _\tau \); insofar as \(\left| {X_\tau } \right| <<\left| X \right| \), solving the restricted game should be much faster than solving the full game. Then, given \(\pi _\tau \), we consider all the strategies which were deleted from the restricted game, \(X \backslash X_\tau \), and order them in decreasing order by their payoff relative to the candidate equilibrium \(\pi _\tau \). If there are no strategies which attain a payoff greater than the equilibrium payoff of one-half, then the algorithm terminates, and \(\pi _\tau \) is an equilibrium of the game with strategy set X. If not, then we construct \(X_{\tau +1}\) by adding the top h strategies from \(X\backslash X_\tau \) to those in \(X_\tau \), and iterating.
The number of strategies h added at every step is arbitrary; we obtained sufficiently good performance with \(h=25\). The trade-off is that if h is too small, then the algorithm will require many iterations, and therefore many calls to the linear program solver, to find the equilibrium, while if h is too large the algorithm will consider many strategies which are not in the equilibrium support, slowing down individual runs of the linear programming solver.
In any event, the correctness of the approach does not depend on the scheme used for adding strategies. Because \(X_{\tau +1}\) is always a strict superset of \(X_\tau \), and because all the supports are bounded above (in the sense of set inclusion) by the strategy set X, this iterative process is guaranteed to terminate in a finite number of steps.
Appendix 2: Instructions
1.1 General rules
Welcome! This session is part of an experiment in the economics of decision making. If you follow the instructions carefully and make good decisions, you can earn a considerable amount of money.
In this session you will be competing with one other person, randomly selected from the people in this room, over the course of forty-five rounds. Throughout the session your competitor will be the same but you will not learn whom of the people in this room you are competing with. The amount of money you earn will depend on your decisions and your competitor’s decisions.
It is important that you do not talk to any of the other people in the room until the session is over. If you have any questions raise your hand and a monitor will come to your desk to answer it.
1.2 Description of a round
Each of the forty-five rounds is identical. At the beginning of each round your computer screen will look like the one below.
You have 120 tokens. You must use these to bid on 4 objects labeled A, B, C, and D. You get points for winning objects—object A is worth 2 points and the other objects are worth 1 point each. For each object you can bid any whole number of tokens (including zero), but the total bid for all objects must add up to 120 tokens. You bid by entering numbers in the boxes, and then clicking on the “Submit” button. If the bids you submit do not add up to 120 the computer will indicate by how many tokens the bid needs to be corrected. If you do not submit a valid bid within 90 s, the computer will bid for you and will place zero tokens on each object.
When everyone in the room has submitted their bids, the computer will compare your bids with those of your opponent. Your computer screen will look like the one below (the bids in the figure have been chosen for illustrative purposes only):
You win an object if you bid more for it than your opponent. (If you and your opponent bid the same amount the computer will randomly decide whether you or your opponent wins the object, with you and your opponent having an equal chance of winning the object. In this case the computer screen will indicate with an asterisk that the object was awarded randomly).
The winner of the round is the person who gets the most points.
The winner of the round earns 50 pence, the other person earns zero.
1.3 Ending the session
At the end of the session, you will be paid the amount you have earned from all forty-five rounds. You will be paid in private and in cash.
Now, please complete the quiz. If you have any questions, please raise your hand. The session will continue when everybody in the room has completed the quiz correctly.
1.4 Quiz
1. Suppose your bids and your competitor’s bids were as follows:
Object | Points | Your bid | Opponent’s bid |
|---|---|---|---|
A | 2 | 30 | 60 |
B | 1 | 30 | 60 |
C | 1 | 30 | 0 |
D | 1 | 30 | 0 |
How many points would you receive? ________ .
How many points would your opponent receive? ________.
What would your earnings from this round be (in pence)? ________.
What would your opponent’s earnings from this round be (in pence)? ________.
2. Suppose your bids and your competitor’s bids were as follows:
Object | Points | Your bid | Opponent’s bid |
|---|---|---|---|
A | 2 | 30 | 10 |
B | 1 | 30 | 30 |
C | 1 | 30 | 40 |
D | 1 | 30 | 40 |
Who wins object A? Me / My Opponent / Randomly Determined (Circle One)
Who wins object B? Me / My Opponent / Randomly Determined (Circle One)
For the remaining questions suppose the computer awards object B to your opponent:
How many points would you receive? ________.
How many points would your opponent receive? ________.
What would your earnings from this round be (in pence)? ________.
What would your opponent’s earnings from this round be (in pence)? ________.
Rights and permissions
About this article
Cite this article
Montero, M., Possajennikov, A., Sefton, M. et al. Majoritarian Blotto contests with asymmetric battlefields: an experiment on apex games. Econ Theory 61, 55–89 (2016). https://doi.org/10.1007/s00199-015-0902-y
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00199-015-0902-y