Fast and Simple Solutions of Blotto Games
Operations Research · 2023-03 · 71 (2) · 506-516
DOI: 10.1287/opre.2022.2261 ↗Kurz gefasst
Fachartikel in der Zeitschrift Operations Research, 2023-03. Verfasst von Soheil Behnezhad und 4 weiteren Autor:innen. Die Arbeit wurde bisher 12-mal zitiert (Crossref) und nennt 24 Literaturangaben.
Abstract (Originalsprache)
The Colonel Blotto game (initially introduced by Borel in 1921) is commonly used for analyzing a wide range of applications from the U.S.Ppresidential election to innovative technology competitions to advertising, sports, and politics. After around a century Ahmadinejad et al. provided the first polynomial-time algorithm for computing the Nash equilibria in Colonel Blotto games. However, their algorithm consists of an exponential-size LP solved by the ellipsoid method, which is highly impractical. In “Fast and Simple Solutions of Blotto Games,” Behnezhad, Dehghani, Derakhshan, Hajighayi, and Seddighin provide the first polynomial-size LP formulation of the optimal strategies for the Colonel Blotto game using linear extension techniques. They use this polynomial-size LP to provide a simpler and significantly faster algorithm for finding optimal strategies of the Colonel Blotto game. They further show this representation is asymptotically tight, which means there exists no other linear representation of the strategy space with fewer constraints.
Zitieren
APA
Behnezhad, S., Dehghani, S., Derakhshan, M., Hajiaghayi, M., & Seddighin, S. (2023). Fast and Simple Solutions of Blotto Games. Operations Research, 71(2), 506-516. https://doi.org/10.1287/opre.2022.2261
Vancouver
Behnezhad S, Dehghani S, Derakhshan M, Hajiaghayi M, Seddighin S. Fast and Simple Solutions of Blotto Games. Operations Research. 2023;71(2):506-516. doi:10.1287/opre.2022.2261
BibTeX
@article{Behnezhad2023,
author = {Behnezhad, Soheil and Dehghani, Sina and Derakhshan, Mahsa and Hajiaghayi, Mohammedtaghi and Seddighin, Saeed},
title = {Fast and Simple Solutions of Blotto Games},
journal = {Operations Research},
year = {2023},
volume = {71},
number = {2},
pages = {506--516},
doi = {10.1287/opre.2022.2261}
}
EUVIMED