From Duels to Battlefields: Computing Equilibria of Blotto and Other Games

References

• [1] Ashlagi I, Krysta P, Tennenholtz M (2008) Social context games. Saberi A, ed. Internet and Network Economics: 6th Internat. Workshop, WINE 2010, Stanford CA, Decmeber 13--17 (Springer, New York), 675–683.Crossref, Google Scholar
• [2] Azar Y, Cohen E, Fiat A, Kaplan H, Racke H (2003) Optimal oblivious routing in polynomial time. Proc. 35th Annual ACM Symp. Theory Comput. (ACM, New York), 383–388.Crossref, Google Scholar
• [3] Bell RM, Cover TM (1980) Competitive optimality of logarithmic investment. Math. Oper. Res. 5(2):161–166.Link, Google Scholar
• [4] Bellman R (1969) On Colonel Blotto and analogous games. SIAM Rev. 11(1):66–68.Crossref, Google Scholar
• [5] Blackett DW (1954) Some Blotto games. Naval Res. Logist. Quart. 1(1):55–60.Crossref, Google Scholar
• [6] Blackett DW (1958) Pure strategy solutions to blotto games. Naval Res. Logist. Quart. 5(2):107–109.Crossref, Google Scholar
• [7] Borel É (1921) La théorie du jeu et les équations intégrales à noyau symétrique. Comptes Rendus de l’Académie 173(13041308):97–100.Google Scholar
• [8] Borel É (1953) The theory of play and integral equations with skew symmetric kernels. Econometrica 21(1):97–100.Crossref, Google Scholar
• [9] Brandt F, Fischer F, Harrenstein P, Shoham Y (2009) Ranking games. Artificial Intelligence 173(2):221–239.Crossref, Google Scholar
• [10] Charnes A (1953) Constrained games and linear programming. Proc. Natl. Acad. Sci. USA 39(7):639–641.Crossref, Google Scholar
• [11] Chen X, Deng X (2006) Settling the complexity of two-player Nash equilibrium. 47th Annual IEEE Symp. Foundations Comput. Sci. FOCS’06 (IEEE, New York), 261–272.Crossref, Google Scholar
• [12] Chen X, Deng X, Teng SH (2006) Computing nash equilibria: Approximation and smoothed complexity. 47th Annual IEEE Symp. Foundations Comput. Sci. FOCS’06 (IEEE, New York), 603–612.Crossref, Google Scholar
• [13] Chowdhury SM, Kovenock D, Sheremeta RM (2013) An experimental investigation of Colonel Blotto games. Econom. Theory 52(3):1–29.Google Scholar
• [14] Dantzig GB (1963) Linear Programming and Extensions (Princeton University Press, Princeton, NJ).Crossref, Google Scholar
• [15] Daskalakis C, Goldberg PW, Papadimitriou CH (2009) The complexity of computing a Nash equilibrium. SIAM J. Comput. 39(1):195–259.Crossref, Google Scholar
• [16] Dziubiński M (2011) Non-symmetric discrete general lotto games. Internat. J. Game Theory 42(4):801–833.Crossref, Google Scholar
• [17] Fréchet M (1953) Commentary on the three notes of Emile Borel. Econometrica 21(1):118–124.Crossref, Google Scholar
• [18] Fréchet M (1953) Emile Borel, initiator of the theory of psychological games and its application. Econometrica 21(1):95–96.Crossref, Google Scholar
• [19] Garg J, Jiang AX, Mehta R (2011) Bilinear games: Polynomial time algorithms for rank based subclasses. Saberi A, ed. Internet and Network Economics: 6th Internat. Workshop, WINE 2010, Stanford CA, Decmeber 13--17 (Springer, New York), 399–407.Crossref, Google Scholar
• [20] Goldberg PW, Papadimitriou CH (2006) Reducibility among equilibrium problems. Proc. 38th Annual ACM Sympos. Theory Comput. (ACM, New York), 61–70.Crossref, Google Scholar
• [21] Golman R, Page SE (2009) General Blotto: Games of allocative strategic mismatch. Public Choice 138(3-4):279–299.Crossref, Google Scholar
• [22] Grötschel M, Lovász L, Schrijver A (1981) The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1(2):169–197.Crossref, Google Scholar
• [23] Grötschel M, Lovász L, Schrijver A (2012) Geometric Algorithms and Combinatorial Optimization, vol. 2 (Springer Science & Business Media, New York).Google Scholar
• [24] Hart S (2008) Discrete Colonel Blotto and General Lotto games. Internat. J. Game Theory 36(3–4):441–460.Crossref, Google Scholar
• [25] Immorlica N, Kalai AT, Lucier B, Moitra A, Postlewaite A, Tennenholtz M (2011) Dueling algorithms. Proc. 43rd Annual ACM Symp. Theory Comput. (ACM, New York), 215–224.Crossref, Google Scholar
• [26] Jiang AX, Leyton-Brown K (2015) Polynomial-time computation of exact correlated equilibrium in compact games. Games Econom. Behav. 91(May):347–359.Crossref, Google Scholar
• [27] Khachiyan LG (1980) Polynomial algorithms in linear programming. USSR Comput. Math. Math. Phys. 20(1):53–72.Crossref, Google Scholar
• [28] Koller D, Megiddo N, Von Stengel B (1994) Fast algorithms for finding randomized strategies in game trees. Proc. 26th Annual ACM Symp. Theory Comput. (ACM, New York), 750–759.Crossref, Google Scholar
• [29] Kontogiannis S, Spirakis P (2010) Exploiting concavity in bimatrix games: New polynomially tractable subclasses. Serna M, Shaltiel R, Jansen K, Rolim J, eds. Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques (Springer, New York), 312–325.Crossref, Google Scholar
• [30] Kovenock D, Roberson B (2010) Conflicts with multiple battlefields. CESifo Working Paper Series 3165, CESifo Group Munich, Munich, Germany. Google Scholar
• [31] Kovenock D, Roberson B (2012) Coalitional Colonel Blotto games with application to the economics of alliances. J. Public Econom. Theory 14(4):653–676.Crossref, Google Scholar
• [32] Kvasov D (2007) Contests with limited resources. J. Econom. Theory 136(1):738–748.Crossref, Google Scholar
• [33] Laslier JF, Picard N (2002) Distributive politics and electoral competition. J. Econom. Theory 103(1):106–130.Crossref, Google Scholar
• [34] Letchford J, Conitzer V (2013) Solving security games on graphs via marginal probabilities. Proc. 27th AAAI Conf. Artificial Intelligence (AAAI Press, Palo Alto, CA), 591–597.Google Scholar
• [35] Lipton RJ, Markakis E, Mehta A (2003) Playing large games using simple strategies. Proc. 4th ACM Conf. Electronic Commerce (ACM, New York), 36–41.Crossref, Google Scholar
• [36] Merolla J, Munger M, Tofias M (2005) In play: A commentary on strategies in the 2004 us presidential election. Public Choice 123(1–2):19–37.Crossref, Google Scholar
• [37] Myerson RB (1993) Incentives to cultivate favored minorities under alternative electoral systems. Amer. Political Sci. Rev. 87(4):856–869.Crossref, Google Scholar
• [38] Nash J (1951) Non-cooperative games. Ann. Math. 54(2):286–295.Crossref, Google Scholar
• [39] Osborne MJ, Rubinstein A (1994) A Course in Game Theory (MIT Press, Cambridge, MA).Google Scholar
• [40] Papadimitriou CH, Steiglitz K (1998) Combinatorial Optimization: Algorithms and Complexity (Courier Dover Publications, Mineola, NY).Google Scholar
• [41] Roberson B (2006) The Colonel Blotto game. Econ. Theory 29(1):1–24.Crossref, Google Scholar
• [42] Rothvoss T (2014) The matching polytope has exponential extension complexity. Proc. 46th Annual ACM Symp. Theory Comput. (ACM, New York), 263–272.Crossref, Google Scholar
• [43] Sahuguet N, Persico N (2006) Campaign spending regulation in a model of redistributive politics. J. Econom. Theory 28(1):95–124.Crossref, Google Scholar
• [44] Shubik M, Weber RJ (1981) Systems defense games: Colonel Blotto, command and control. Naval Res. Logist. Quart. 28(2):281–287.Crossref, Google Scholar
• [45] Sion M (1958) On general minimax theorems. Pacific J. Math. 8(1):171–176.Crossref, Google Scholar
• [46] Tukey JW (1949) A problem of strategy. Econometrica 17:73.Crossref, Google Scholar
• [47] Von Neumann J, Fréchet M (1953) Communication on the Borel notes. Econometrica 21(1):124–127.Crossref, Google Scholar
• [48] Weinstein J (2012) Two notes on the Blotto game. BE J. Theoret. Econom. 12(1):1–13.Google Scholar
• [49] Xu H, Fang F, Jiang AX, Conitzer V, Dughmi S, Tambe M (2014) Solving zero-sum security games in discretized spatio-temporal domains. Proc. 28th Conf. Artificial Intelligence (AAAI, Palo Alto, CA), 1500–1506.Google Scholar