Blotto on the Ballot: A Ballot Stuffing Blotto Game
Harsh Shah, Jayakrishnan Nair, D Manjunath, Narayan Mandayam · 2024
Read Blotto on the Ballot: A Ballot Stuffing Blotto Game by Harsh Shah, Jayakrishnan Nair, D Manjunath, Narayan Mandayam (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-06222.txt.
Introduction
Harsh Shah and co-authors model a contest over votes as a game in 2024. One party places workers across many voting areas. A rival can clear a set number of those areas, wiping out the workers there. The first party wants as many workers as possible to survive. The rival wants the count low.
The authors link the game to ballot stuffing and to steps by election staff to stop it. They find all the stable outcomes of the game by solving a math problem. The outcomes have a clear shape, and fast methods can find them. The model also fits a parliament style vote. It may apply to security and audit work as well.
Catalog record
| CREATOR | Harsh Shah, Jayakrishnan Nair, D Manjunath, Narayan Mandayam |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 48 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-06222
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Blotto on the Ballot: A Ballot Stuffing Blotto Game Harsh Shah, Jayakrishnan Nair, D Manjunath, Narayan Mandayam Abstract We consider the following Colonel Blotto game between parties P 1 P_{1} and P A . P_{A}. P 1 P_{1} deploys a non negative number of troops across J J battlefields, while P A P_{A} chooses K , K, K < J , K<J, battlefields to remove all of P 1 P_{1} ’s troops from the chosen battlefields. P 1 P_{1} has the objective of maximizing the number of surviving troops while P A P_{A} wants to minimize it. Drawing an analogy with ballot stuffing by a party contesting an election and the countermeasures by the Election Commission to negate that, we call this the Ballot Stuffing Game. For this zero-sum resource allocation game, we obtain the set of Nash equilibria as a solution to a convex combinatorial optimization problem. We analyze this optimization problem and obtain insights into the several non trivial features of the equilibrium behavior. These features in turn allows to describe the structure of the solutions and efficient algorithms to obtain then. The model is described as ballot stuffing game in a plebiscite but has applications in security and auditing games. The results are extended to a parliamentary election model. Numerical examples illustrate applications of the game. 1 Department of Electrical Engineering, IIT Bombay, Mumbai, India 2 WINLAB, Rutgers University, North Brunswick, New Jersey 08902, USA {210100063, jayakrishnan.nair, dmanju}@iitb.ac.in, [email protected] Keywords—Colonel Blotto game, Nash equilibrium computation 1 Introduction Resource allocation games over multiple asymmetric battlefields between asymmetric competing players has wide applications in electoral politics, e.g., ( Washburn 2013 ) , security deployments, e.g., ( Boehmer et al. 2024 ) , market strategies, e.g., ( Maljkovic, Nilsson, and Geroliminis 2024 ) ), etc. The asymmetry could be in the deployment cost in and/or the payoffs from the different battlefields and also in the strategy space for the two players. A popular model is the Colonel Blotto Game. The classical version is a two-player, zero-sum, multi-dimensional resource allocation game over J battlefields. The objective of the players is to maximize the number of battlefields that they win. Players have finite resources that are distributed among the J battlefields without knowing the opponents deployment. Each battlefield is won by the player that deploys the higher number of resources for that location. We describe and analyze a new variation that we call the Ballot Stuffing Game. Our illustrative scenario is a game between an election contestant (attacker) and the Election Commission (the defender) that is responsible for a fair election. Party P_{1} is contesting the election and attempts to gain an unfair advantage over its rivals by indulging in ‘ballot stuffing,’ i.e., by having votes cast in its favour by non eligible voters, voters voting multiple times, or through other means. The Election Commission, denoted by P_{A}, is aware of this intention and aims to mitigate the negative effect by placing observers in a subset of the booths to prevent stuffing. The resources of the attacker P_{1} above is a positive real number and it incurs a deployment dependent cost. The resources of the defender called P_{A} above, is an integer and the possible deployment in each battlefield is a binary integer. The effect of P_{A} deploying a resource in a battlefield is to nullify all the resources of P_{1} in that battlefield. In the next section, we formally describe the model and develop the notation. We will also introduce two variations of the Ballot Stuffing Game. Ballot stuffing, while not widespread, is a known threat in all forms of elections in all countries. There have been accusations of election fraud in mayoral elections in the US ( NYT 2024 ) , the Russian elections ( Harvey 2016 ; RFE 2024 ) , and electronic voting over the Internet in organisational elections ( Cortier et al. 2011 ) . It is also not uncommon in reputation systems ( Bhattacharjee and Goel 2005 ) . However, it has been observed that the presence of observers or inspectors reduces the levels of fraud ( Asunka et al. 2019 ) . Colonel Blotto games have been studied since, at least 1912 when it was first posed by Emile Borel. A key insight was developed in ( Roberson 2006 ) where the unique equilibrium payoffs and the distributions of the deployments were characterized in some detail. Since then several contributions to the algorithms to compute the equilibrium have been developed in ( Ahmadinejad et al. 2016 ) , ( Behnezhad et al. 2017 ) , ( Behnezhad et al. 2018a ) , ( Behnezhad et al. 2018b ) , ( Behnezhad et al. 2019 ) , and ( Behnezhad et al. 2023 ) among others. There are also some similarities of the Ballot Stuffing Game to the Auditing Games games ( Behnezhad et al. 2019 ) and Blotto Game with Testing ( Sonin 2024 ) . However, the resources available to the attacker and the defender and also the rules of engagement in the battlefields in these games are significantly different. 2 Model and Notation There are J polling stations and two players ( P_{1},P_{2} ) contesting for the votes that will be cast at these stations. The actual number of votes that will be cast for Player P_{i} in station j is a random variable X_{i,j}, with i\in\{1,2\} and 1\leq j\leq J. Define X_{j}:=X_{1,j}-X_{2,j} as the excess votes for P_{1} that will be cast in station j. Let V be the event that P_{1} is the victor in the election. There are two election models that we will consider. In the Plebiscite model V=\mathds{1}_{\left\{{\sum_{j=1}^{J}X_{j}>0}\right\}} (1) i.e., P_{1} wins the election if the total of the votes cast for it from all the stations exceeds that of P_{2}. We could also define a generalized Parliamentary model with w_{j} being the weight associated with polling station j and V=\mathds{1}_{\left\{{\left(\sum_{j=1}^{J}w_{j}\mathds{1}_{\left\{{X_{j}>0}\right\}}\right)>W/2}\right\}}. (2) Here, P_{1} is the winner if the weighted sum of the polling stations won by P_{1} is more than half of the sum of the weights. In the UK and many countries w_{j}=1 while the US has different weights for the different stations. P_{1} can try to increase its vote count in station j (without any corresponding response from P_{2} ) by, say, z_{j} at a cost of g_{j}(z_{j}). We assume the cost function g_{j}(z_{j}) is strictly convex, differentiable, and increasing in its argument, beginning from zero when its argument is zero, for 1\leq j\leq J. Define z:=[z_{1},\ldots,z_{J}] to be the vector of votes stuffed by P_{1} in each of the stations, g(z):=[g_{1}(z_{1}),\ldots,g_{J}(z_{J})] to be the vector of cost functions and V(z):=\mathds{1}_{\left\{{\sum_{j=1}^{J}(X_{j}+z_{j})>0}\right\}}. Let \phi(z) be the probability that P_{1} wins the election when it stuffs according to z. For the plebiscite model \phi(z) will be given by \displaystyle\phi(z):=\mathsf{E}\!\left[V(z)\right] \displaystyle=\mathsf{Pr}\!\left(\sum_{j=1}^{J}(X_{j}+z_{j})>0\right), (3) and for the parliamentary model, we will have \displaystyle\phi(z):=\mathsf{E}\!\left[V(z)\right] \displaystyle=\mathsf{Pr}\!\left(\ \left(\sum_{j=1}^{J}\mathds{1}_{\left\{{(X_{j}+z_{j})>0}\right\}}\right)>J/2\right). (4) \phi(0) is the prior probability of P_{1} winning. P_{1} has a total budget of G and, assuming the costs are additive, has the following objective. \displaystyle\max_{z}\ \displaystyle\ \phi(z) subject to \displaystyle\sum_{j=1}^{J}g_{j}(z_{j})\ \leq\ G, \displaystyle 0\leq z_{j}\hskip 21.68121pt\mbox{for $1\leq j\leq J$}, (5) The Ballot Stuffing Game Recall that we had assumed that P_{2} does not