From Battlefields to Elections: Winning Strategies of Blotto and Auditing Games
Mixed strategies are often evaluated based on the expected payoff that they guarantee. This is not always desirable. In this paper, we consider games for which maximizing the expected payoff deviates from the actual goal of the players. To address this issue, we introduce the notion of a (u; p)-maxm...
| Main Authors: | , , , , , , , , |
|---|---|
| Other Authors: | |
| Format: | Book |
| Language: | English |
| Published: |
Society for Industrial and Applied Mathematics
2020
|
| Online Access: | https://hdl.handle.net/1721.1/125193 |
| _version_ | 1811070549959376896 |
|---|---|
| author | Behnezhad, Soheil Blum, Avrim Derakhshan, Mahsa HajiAghayi, MohammadTaghi Mahdian, Mohammad Papadimitriou, Christos H. Rivest, Ronald L. Seddighin, Saeed Stark, Philip B. |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Behnezhad, Soheil Blum, Avrim Derakhshan, Mahsa HajiAghayi, MohammadTaghi Mahdian, Mohammad Papadimitriou, Christos H. Rivest, Ronald L. Seddighin, Saeed Stark, Philip B. |
| author_sort | Behnezhad, Soheil |
| collection | MIT |
| description | Mixed strategies are often evaluated based on the expected payoff that they guarantee. This is not always desirable. In this paper, we consider games for which maximizing the expected payoff deviates from the actual goal of the players. To address this issue, we introduce the notion of a (u; p)-maxmin strategy which ensures receiving a minimum utility of u with probability at least p. We then give approximation algorithms for the problem of finding a (u; p)-maxmin strategy for these games. The first game that we consider is Colonel Blotto, a well-studied game that was introduced in 1921. In the Colonel Blotto game, two colonels divide their troops among a set of battle fields. Each battle field is won by the colonel that puts more troops in it. The payoff of each colonel is the weighted number of battle fields that she wins. We show that maximizing the expected payoff of a player does not necessarily maximize her winning probability for certain applications of Colonel Blotto. For example, in presidential elections, the players' goal is to maximize the probability of winning more than half of the votes, rather than maximizing the expected number of votes that they get. We give an exact algorithm for a natural variant of continuous version of this game. More generally, we provide constant and logarithmic approximation algorithms for finding (u; p)-maxmin strategies. We also introduce a security game version of Colonel Blotto which we call auditing game. It is played between two players, a defender and an attacker. The goal of the defender is to prevent the attacker from changing the outcome of an instance of Colonel Blotto. Again, maximizing the expected payoff of the defender is not necessarily optimal. Therefore we give a constant approximation for (u; p)-maxmin strategies. |
| first_indexed | 2024-09-23T08:37:48Z |
| format | Book |
| id | mit-1721.1/125193 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T08:37:48Z |
| publishDate | 2020 |
| publisher | Society for Industrial and Applied Mathematics |
| record_format | dspace |
| spelling | mit-1721.1/1251932022-09-30T10:06:46Z From Battlefields to Elections: Winning Strategies of Blotto and Auditing Games Behnezhad, Soheil Blum, Avrim Derakhshan, Mahsa HajiAghayi, MohammadTaghi Mahdian, Mohammad Papadimitriou, Christos H. Rivest, Ronald L. Seddighin, Saeed Stark, Philip B. Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Mixed strategies are often evaluated based on the expected payoff that they guarantee. This is not always desirable. In this paper, we consider games for which maximizing the expected payoff deviates from the actual goal of the players. To address this issue, we introduce the notion of a (u; p)-maxmin strategy which ensures receiving a minimum utility of u with probability at least p. We then give approximation algorithms for the problem of finding a (u; p)-maxmin strategy for these games. The first game that we consider is Colonel Blotto, a well-studied game that was introduced in 1921. In the Colonel Blotto game, two colonels divide their troops among a set of battle fields. Each battle field is won by the colonel that puts more troops in it. The payoff of each colonel is the weighted number of battle fields that she wins. We show that maximizing the expected payoff of a player does not necessarily maximize her winning probability for certain applications of Colonel Blotto. For example, in presidential elections, the players' goal is to maximize the probability of winning more than half of the votes, rather than maximizing the expected number of votes that they get. We give an exact algorithm for a natural variant of continuous version of this game. More generally, we provide constant and logarithmic approximation algorithms for finding (u; p)-maxmin strategies. We also introduce a security game version of Colonel Blotto which we call auditing game. It is played between two players, a defender and an attacker. The goal of the defender is to prevent the attacker from changing the outcome of an instance of Colonel Blotto. Again, maximizing the expected payoff of the defender is not necessarily optimal. Therefore we give a constant approximation for (u; p)-maxmin strategies. 2020-05-12T20:42:05Z 2020-05-12T20:42:05Z 2018-01 2019-07-03T13:07:04Z Book http://purl.org/eprint/type/ConferencePaper 9781611975031 https://hdl.handle.net/1721.1/125193 Behnezhad, Soheil et al. "From Battlefields to Elections: Winning Strategies of Blotto and Auditing Games." Proceedings of the 2018 Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, Louisiana, USA, Society for Industrial and Applied Mathematics, January 2018 © 2018 SIAM en http://dx.doi.org/10.1137/1.9781611975031.148 Proceedings of the 2018 Annual ACM-SIAM Symposium on Discrete Algorithms Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Society for Industrial and Applied Mathematics SIAM |
| spellingShingle | Behnezhad, Soheil Blum, Avrim Derakhshan, Mahsa HajiAghayi, MohammadTaghi Mahdian, Mohammad Papadimitriou, Christos H. Rivest, Ronald L. Seddighin, Saeed Stark, Philip B. From Battlefields to Elections: Winning Strategies of Blotto and Auditing Games |
| title | From Battlefields to Elections: Winning Strategies of Blotto and Auditing Games |
| title_full | From Battlefields to Elections: Winning Strategies of Blotto and Auditing Games |
| title_fullStr | From Battlefields to Elections: Winning Strategies of Blotto and Auditing Games |
| title_full_unstemmed | From Battlefields to Elections: Winning Strategies of Blotto and Auditing Games |
| title_short | From Battlefields to Elections: Winning Strategies of Blotto and Auditing Games |
| title_sort | from battlefields to elections winning strategies of blotto and auditing games |
| url | https://hdl.handle.net/1721.1/125193 |
| work_keys_str_mv | AT behnezhadsoheil frombattlefieldstoelectionswinningstrategiesofblottoandauditinggames AT blumavrim frombattlefieldstoelectionswinningstrategiesofblottoandauditinggames AT derakhshanmahsa frombattlefieldstoelectionswinningstrategiesofblottoandauditinggames AT hajiaghayimohammadtaghi frombattlefieldstoelectionswinningstrategiesofblottoandauditinggames AT mahdianmohammad frombattlefieldstoelectionswinningstrategiesofblottoandauditinggames AT papadimitriouchristosh frombattlefieldstoelectionswinningstrategiesofblottoandauditinggames AT rivestronaldl frombattlefieldstoelectionswinningstrategiesofblottoandauditinggames AT seddighinsaeed frombattlefieldstoelectionswinningstrategiesofblottoandauditinggames AT starkphilipb frombattlefieldstoelectionswinningstrategiesofblottoandauditinggames |