From Duels to Battlefields: Computing Equilibria of Blotto and Other Games
Authors: AmirMahdi Ahmadinejad, Sina Dehghani, MohammadTaghi Hajiaghay, Brendan Lucier, Hamid Mahini, Saeed Seddighin
AAAI 2016 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the problem of computing Nash equilibria of zerosum games. Many natural zero-sum games have exponentially many strategies, but highly structured payoffs. For example, in the well-studied Colonel Blotto game (introduced by Borel in 1921), players must divide a pool of troops among a set of battlefields with the goal of winning (i.e., having more troops in) a majority. The Colonel Blotto game is commonly used for analyzing a wide range of applications from the U.S presidential election, to innovative technology competitions, to advertisement, to sports. However, because of the size of the strategy space, standard methods for computing equilibria of zero-sum games fail to be computationally feasible. Indeed, despite its importance, only few solutions for special variants of the problem are known. In this paper we show how to compute equilibria of Colonel Blotto games. Moreover, our approach takes the form of a general reduction: to find a Nash equilibrium of a zero-sum game, it suffices to design a separation oracle for the strategy polytope of any bilinear game that is payoff-equivalent. We then apply this technique to obtain the first polytime algorithms for a variety of games. In addition to Colonel Blotto, we also show how to compute equilibria in an infinite-strategy variant called the General Lotto game; this involves showing how to prune the strategy space to a finite subset before applying our reduction. We also consider the class of dueling games, first introduced by Immorlica et al. (2011). We show that our approach provably extends the class of dueling games for which equilibria can be computed: we introduce a new dueling game, the matching duel, on which prior methods fail to be computationally feasible but upon which our reduction can be applied. |
| Researcher Affiliation | Collaboration | Stanford University Univeristy of Maryland, Microsoft Research |
| Pseudocode | No | The paper describes a dynamic programming approach in the proof of Lemma 0.2, but it is presented as descriptive text and mathematical formulas, not as a structured pseudocode or algorithm block. |
| Open Source Code | No | The paper does not provide any explicit statements about releasing source code or links to a code repository for the methodology described. |
| Open Datasets | No | This is a theoretical paper focused on algorithms for computing equilibria in games, rather than empirical studies involving datasets. Therefore, there is no mention of training datasets or their public availability. |
| Dataset Splits | No | This paper is theoretical and does not involve empirical experiments with data splits. Therefore, it does not provide specific dataset split information (e.g., train/validation/test percentages or counts) for reproduction. |
| Hardware Specification | No | This paper is theoretical and focuses on algorithms for computing game equilibria. It does not describe any specific hardware used for running experiments. |
| Software Dependencies | No | The paper does not provide specific software dependencies or version numbers required to replicate any experiments or implement the proposed algorithms. It's a theoretical work. |
| Experiment Setup | No | This paper is theoretical and does not involve empirical experiments. Therefore, it does not contain specific experimental setup details such as hyperparameter values, training configurations, or system-level settings. |