Voting in Two-Crossing Elections
Authors: Andrei Constantinescu, Roger Wattenhofer
IJCAI 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We introduce two-crossing elections as a generalization of single-crossing elections, showing a number of new results. First, we show that two-crossing elections can be recognized in polynomial time, by reduction to the well-studied consecutive ones problem. Single-crossing elections exhibit a transitive majority relation, from which many important results follow. On the other hand, we show that the classical Debord-Mc Garvey theorem can still be proven two-crossing, implying that any weighted majority tournament is inducible by a two-crossing election. This shows that many voting rules are NP-hard under two-crossing elections, including Kemeny and Slater. This is in contrast to the single-crossing case and outlines an important complexity boundary between single- and two-crossing. Subsequently, we show that for two-crossing elections the Young scores of all candidates can be computed in polynomial time, by formulating a totally unimodular linear program. Finally, we consider the Chamberlin Courant rule with arbitrary disutilities and show that a winning committee can be computed in polynomial time, using an approach based on dynamic programming. |
| Researcher Affiliation | Academia | Andrei Constantinescu and Roger Wattenhofer ETH Zürich {aconstantine, wattenhofer}@ethz.ch |
| Pseudocode | Yes | Introduce dp[ℓ, r, t] for 1 ℓ r n, 1 t k to mean the least total dissatisfaction attainable for voters in [ℓ: r] using a legal t-assignment restricted to those voters... Then, the recurrence relation is: dp[ℓ, r, t] = min i=1 ρ(wi, crt) + i=0 dp[wi + 1, wi+1 1, ti] : crt C, 1 x r ℓ+ 1, ℓ w1 < . . . < wx r, t0, . . . , tx 0 and t0 + . . . + tx = t 1 (4) |
| Open Source Code | No | The paper does not provide an explicit statement or link for open-source code for the described methodology. |
| Open Datasets | No | This paper is theoretical and does not conduct experiments involving datasets. |
| Dataset Splits | No | This paper is theoretical and does not report on experimental validation, so no dataset splits for validation are mentioned. |
| Hardware Specification | No | The paper does not describe any specific hardware used, as it focuses on theoretical results and complexity analysis rather than empirical experiments. |
| Software Dependencies | No | The paper does not mention any specific software dependencies with version numbers, as it is a theoretical work. |
| Experiment Setup | No | The paper is theoretical and does not include details about an experimental setup, such as hyperparameters or training settings. |