Strategic Behavior is Bliss: Iterative Voting Improves Social Welfare
Authors: Joshua Kavner, Lirong Xia
NeurIPS 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our first main result (Theorem 1) states that, unfortunately, for any fixed m 3 and utility vector u, the ADPo A is Θ(n) for n agents. Therefore, the positive result achieved by Brˆanzei et al. [2013] is not upheld if u differs from plurality utility under the iterative plurality mechanism. To overcome this negative worst-case result, we introduce the notion of expected additive dynamic price of anarchy (EADPo A), which presumes agents truthful preferences to be generated from a probability distribution. Our second main result (Theorem 2) is positive and surprises us: for any fixed m 3 and utility vector u, the EADPo A is Ω(1) when agents preferences are i.i.d. uniformly at random, known as Impartial Culture (IC) in social choice. |
| Researcher Affiliation | Academia | Joshua Kavner Department of Computer Science Rensselaer Polytechnic Institute Troy, NY 12180 kavnej@rpi.edu Lirong Xia Department of Computer Science Rensselaer Polytechnic Institute Troy, NY 12180 xialirong@gmail.com |
| Pseudocode | No | The paper does not contain any structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide any statement or link regarding the availability of open-source code for the methodology described. |
| Open Datasets | No | The paper is theoretical and focuses on mathematical proofs and analyses under specific distributions (e.g., Impartial Culture), rather than using empirical datasets. No specific dataset access information is provided. |
| Dataset Splits | No | The paper is theoretical and does not describe training, validation, or test splits for any dataset. |
| Hardware Specification | No | The paper is theoretical and does not mention any specific hardware used for experiments. |
| Software Dependencies | No | The paper is theoretical and does not mention any specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not provide details about an experimental setup, hyperparameters, or training configurations. |