Strategic Voting with Incomplete Information
Authors: Ulle Endriss, Svetlana Obraztsova, Maria Polukarov, Jeffrey S. Rosenschein
IJCAI 2016 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our contributions are twofold. In the first part of the paper, we establish results on the manipulability of voting rules under incomplete information, complementing previous results by Reijngoud and Endriss [2012]. We focus on the Plurality, Veto, k-approval, Borda, Copeland, and Maximin rules (all defined in Section 2). While the Gibbard-Satterthwaite Theorem shows that all of these rules are susceptible to strategic manipulation when the manipulator has full information, this may in principle cease to be the case when we restrict their access to information. We show that, nevertheless, for several natural restrictions to a manipulator s information, manipulation can still occur for certain rules. At the same time, we are able to identify some combinations of voting rules and information sets where manipulation can be ruled out, thereby providing positive results of practical interest. In the second part of the paper, we connect strategic voting under incomplete information with the growing literature on iterative voting [Meir et al., 2010; Lev and Rosenschein, 2012; Reijngoud and Endriss, 2012; Reyhani and Wilson, 2012; Grandi et al., 2013; Obraztsova et al., 2015]. We consider scenarios where voters are permitted to update their ballot any number of times, in response to the limited information they have regarding the other votes. The question then arises whether such a process will converge to a state where the election winner does not change anymore. As is well known, under complete information, convergence can only be guaranteed in very specific circumstances. Arbitrary improvement moves are not guaranteed to converge under any voting rule, best-response dynamics lead to equilibria only for Plurality and Veto, and other rules require more restrictions on allowed manipulations to guarantee convergence. In contrast to these largely negative results, we are able to show that, when the only information voters have access to is the identity of the candidate currently leading the polls, we obtain convergence results for all the voting rules considered here. |
| Researcher Affiliation | Academia | Ulle Endriss University of Amsterdam The Netherlands Svetlana Obraztsova Hebrew University Jerusalem, Israel Maria Polukarov University of Southampton United Kingdon Jeffrey S. Rosenschein Hebrew University Jerusalem, Israel |
| Pseudocode | No | The paper does not contain structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide concrete access to source code for the methodology described. |
| Open Datasets | No | This is a theoretical paper and does not involve empirical studies with datasets; therefore, no information regarding training datasets or their availability is provided. |
| Dataset Splits | No | This is a theoretical paper and does not involve empirical studies with datasets; therefore, no information regarding validation dataset splits is provided. |
| Hardware Specification | No | This is a theoretical paper and does not involve empirical experiments; therefore, no hardware specifications are mentioned for running experiments. |
| Software Dependencies | No | This is a theoretical paper and does not involve empirical experiments; therefore, no specific software dependencies with version numbers are mentioned. |
| Experiment Setup | No | This is a theoretical paper and does not involve empirical experiments; therefore, no experimental setup details such as hyperparameters or training configurations are provided. |