An Algorithmic Solution to the Blotto Game Using Multimarginal Couplings

References

• Agueh M, Carlier G (2011) Barycenters in the Wasserstein space. SIAM J. Math. Anal. 43(2):904–924.Crossref, Google Scholar
• Ahmadinejad A, Dehghani S, Hajiaghayi M, Lucier B, Mahini H, Seddighin S (2019) From duels to battlefields: Computing equilibria of blotto and other games. Math. Oper. Res. 44(4):1304–1325.Link, Google Scholar
• Altschuler JM, Boix-Adsera E (2020) Polynomial-time algorithms for multimarginal optimal transport problems with structure. Preprint, submitted August 7, https://arxiv.org/abs/2008.03006.Google Scholar
• Altschuler J, Boix-Adsera E (2021) Hardness results for multimarginal optimal transport problems. Discrete Optim. 42:100669.Crossref, Google Scholar
• Altschuler J, Weed J, Rigollet P (2017) Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration. Advances Neural Inform. Processing Systems 30 (NIPS 2017) (Curran Associates Inc., Red Hook, NY), 1961–1971.Google Scholar
• Beaglehole D, Hopkins M, Kane D, Liu S, Lovett S (2022) An efficient approximation algorithm for the Colonel Blotto game. https://www.researchgate.net/publication/358142876_An_Efficient_Approximation_Algorithm_for_the_Colonel_Blotto_Game/fulltext/61f2f483c5e3103375c4e85f/An-Efficient-Approximation-Algorithm-for-the-Colonel-Blotto-Game.pdf?_tp=eyJjb250ZXh0Ijp7ImZpcnN0UGFnZSI6InB1YmxpY2F0aW9uIiwicGFnZSI6InB1YmxpY2F0aW9uIn19.Google Scholar
• Behnezhad S, Dehghani S, Derakhshan M, HajiAghayi M, Seddighin S (2017) Faster and simpler algorithm for optimal strategies of Blotto game. Proc. AAAI Conf. Artificial Intelligence, vol. 31 (Association for the Advancement of Artificial Intelligence, Washington, DC), 369–375.Google Scholar
• Bell RM, Cover TM (1980) Competitive optimality of logarithmic investment. Math. Oper. Res. 5(2):161–166.Link, Google Scholar
• Border KC (1991) Implementation of reduced form auctions: A geometric approach. Econometrica 59(4):1175–1187.Crossref, Google Scholar
• Borel E (1921) La théorie du jeu et les équations intégrales à noyau symétrique. Comptes rendus de l’Académie des Sciences 173:1304–1308.Google Scholar
• Borel E, Ville J (1938) Applications de la Théorie des Probabilités aux Jeux de Hasard: Cours Professé à la Faculté des Sciences de Paris (Gauthier-Villars, Paris).Google Scholar
• Bubeck S (2015) Convex optimization: Algorithms and complexity. Foundations Trends Machine Learning 8(3–4):231–357.Crossref, Google Scholar
• Cuturi M (2013) Sinkhorn distances: Lightspeed computation of optimal transport. Burges CJC, Bottou L, Welling M, Ghahramani Z, Weinberger KQ, eds. Advances Neural Inform. Processing Systems 26 (NIPS 2013) (Curran Associates, Inc., Red Hook, NY), 2292–2300.Google Scholar
• Di Marino S, Gerolin A, Nenna L (2017) Optimal transportation theory with repulsive costs. Bergounioux M, Oudet É, Rumpf M, Carlier G, Champion T, Santambrogio F, eds. Topological Optimization and Optimal Transport, vol. 17 (De Gruyter, Berlin, Boston), 204–256.Crossref, Google Scholar
• Ferdowsi A, Saad W, Mandayam NB (2021) Colonel Blotto game for sensor protection in interdependent critical infrastructure. IEEE Internet Things J. 8(4):2857–2874.Crossref, Google Scholar
• Fréchet M (1953) Emile Borel, initiator of the theory of psychological games and its application. Econometrica 21:95–96.Crossref, Google Scholar
• Gross O (1950) The symmetric Blotto game. Technical report, Rand Corporation, Santa Monica, CA.Google Scholar
• Gross O, Wagner R (1950) A continuous Colonel Blotto game. Technical report, Rand Corporation, Santa Monica, CA. Google Scholar
• Hajimirsaadeghi M, Mandayam NB (2017) A dynamic Colonel Blotto game model for spectrum sharing in wireless networks. 2017 55th Annual Allerton Conf. Comm. Control Comput. (Allerton) (IEEE, Piscataway, NJ), 287–294.Google Scholar
• Hart S (2008) Discrete Colonel Blotto and general Lotto games. Internat. J. Game Theory 36(3):441–460.Crossref, Google Scholar
• Hortala-Vallve R, Llorente-Saguer A (2012) Pure strategy Nash equilibria in non-zero sum Colonel Blotto games. Internat. J. Game Theory 41(2):331–343.Crossref, Google Scholar
• Knott M, Smith C (2006) Choosing joint distributions so that the variance of the sum is small. J. Multivariate Anal. 97(8):1757–1765.Crossref, Google Scholar
• Kovenock D, Roberson B (2021) Generalizations of the general Lotto and Colonel Blotto games. Econom. Theory 71(3):997–1032.Crossref, Google Scholar
• Labib M, Ha S, Saad W, Reed JH (2015) A Colonel Blotto game for anti-jamming in the internet of things. 2015 IEEE Global Comm. Conf. (GLOBECOM) (IEEE, Piscataway, NJ), 1–6.Google Scholar
• Laslier JF (2002) How two-party competition treats minorities. Rev. Econom. Design 7(3):297–307.Crossref, Google Scholar
• Laslier JF, Picard N (2002) Distributive politics and electoral competition. J. Econom. Theory 103(1):106–130.Crossref, Google Scholar
• Lin T, Ho N, Cuturi M, Jordan MI (2022) On the complexity of approximating multimarginal optimal transport. J. Machine Learn. Res. 23(65):1–43.Google Scholar
• Macdonell ST, Mastronardi N (2015) Waging simple wars: A complete characterization of two-battlefield Blotto equilibria. Econom. Theory 58(1):183–216.Crossref, Google Scholar
• Masucci AM, Silva A (2015) Defensive resource allocation in social networks. 2015 54th IEEE Conf. Decision Control (CDC) (IEEE, Piscataway, NJ), 2927–2932.Google Scholar
• Merolla J, Munger M, Tofias M (2005) In play: A commentary on strategies in the 2004 U.S. presidential election. Public Choice 123(1/2):19–37.Crossref, Google Scholar
• Myerson RB (1993) Incentives to cultivate favored minorities under alternative electoral systems. Amer. Political Sci. Rev. 87(4):856–869.Crossref, Google Scholar
• Nakayama M (2006) The dawn of modern theory of games. Kusuoka S, Yamazaki A, eds. Advances in Mathematical Economics, vol. 9 (Springer, Tokyo), 73–97.Crossref, Google Scholar
• Polyanskiy Y, Wu Y (2022) Information Theory Information Theory: From Coding to Learning (Cambridge University Press, Cambridge, UK).Google Scholar
• Reny PJ (1999) On the existence of pure and mixed strategy Nash equilibria in discontinuous games. Econometrica 67(5):1029–1056.Crossref, Google Scholar
• Roberson B (2006) The Colonel Blotto game. Econom. Theory 29(1):1–24.Crossref, Google Scholar
• Rüschendorf L, Uckelmann L (2002) Variance minimization and random variables with constant sum. Cuadras CM, Fortiana J, Rodriguez-Lallena JA, eds. Distributions with Given Marginals and Statistical Modelling (Springer, Dordrecht, Netherlands), 211–222.Crossref, Google Scholar
• Santambrogio F (2015) Optimal Transport for Applied Mathematicians. Progress in Nonlinear Differential Equations and Their Applications, vol. 87 (Birkhäuser/Springer, Cham, Switzerland).Crossref, Google Scholar
• Schwartz G, Loiseau P, Sastry SS (2014) The heterogeneous Colonel Blotto game. 2014 7th Internat. Conf. NETwork Games COntrol OPtim. (NetGCoop) (IEEE, Piscataway, NJ), 232–238.Google Scholar
• Sinkhorn R (1964) A relationship between arbitrary positive matrices and doubly stochastic matrices. Ann. Math. Statist. 35(2):876–879.Crossref, Google Scholar
• Sinkhorn R, Knopp P (1967) Concerning nonnegative matrices and doubly stochastic matrices. Pacific J. Math. 21(2):343–348.Crossref, Google Scholar
• Thomas C (2018) N-dimensional Blotto game with heterogeneous battlefield values. Econom. Theory 65(3):509–544.Crossref, Google Scholar
• von Neumann J (1928) Zur Theorie der Gesellschaftsspiele. Math. Ann. 100:295–320.Crossref, Google Scholar
• von Neumann J, Fréchet M (1959) Le rôle d’émile borel dans la théorie des jeux. Rev. Econom. Polit. 69(2):139–167.Google Scholar
• Vu DQ, Loiseau P, Silva A (2018) Efficient computation of approximate equilibria in discrete colonel blotto games. Proc. 27th Internat. Joint Conf. Artificial Intelligence (AAAI Press, Washington, DC), 519–526.Google Scholar
• Wang B, Wang R (2016) Joint mixability. Math. Oper. Res. 41(3):808–826.Link, Google Scholar
• Weinstein J (2012) Two notes on the Blotto game. B. E. J. Theoretical Econom. 12(1):1–13.Google Scholar
• Zimin AP (2020) On existence of measure with given marginals supported on a hyperplane. Preprint, submitted October 14, https://arxiv.org/abs/2010.07263.Google Scholar