Verifying Proportionality in Temporal Voting
Authors: Edith Elkind, Svetlana Obraztsova, Jannik Peters, Nicholas Teh
AAAI 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study a model of temporal voting where there is a fixed time horizon, and at each round the voters report their preferences over the available candidates and a single candidate is selected. Prior work has adapted popular notions of justified representation as well as voting rules that provide strong representation guarantees from the multiwinner election setting to this model. In our work, we focus on the complexity of verifying whether a given outcome offers proportional representation. We show that in the temporal setting verification is strictly harder than in multiwinner voting, but identify natural special cases that enable efficient algorithms. ... Our complex-ity result for JR shows that the temporal setting is strictly harder than the multiwinner setting. We complement our hardness results by fixed parameter tractability results as well as a polynomial-time algorithm for a natural special case of our model... We also develop an integer linear programming formulation for the problem of selecting an outcome that provides EJR and satisfies additional linear constraints on voters utilities, thereby establishing that this problem is fixed-parameter tractable with respect to the number of voters n. |
| Researcher Affiliation | Academia | 1Northwestern University, USA 2Carleton University, Canada 3National University of Singapore, Singapore 4University of Oxford, UK |
| Pseudocode | Yes | Algorithm 1: 2-Stage Greedy Cohesive Rule. 1 Input: Set of voters N = {1, . . . , n}, set of candidates P = {p1, . . . , pm}, number of rounds , voters approval sets (s1, . . . , sn); 2 o (p1, . . . , p1); 4 V := {V N : β(V ) > 0}; 6 while V 6= ? do 7 Select a set V 2 arg max V 2V (V ) with ties broken arbitrarily; 8 V+ V+ [ {V }; 9 for V 0 2 V do 10 if V \ V 0 6= ? then 11 V V \ {V 0}; 12 Sort V+ as V1, . . . , Vq so that β(V1) β(Vq); 13 for k = 1, . . . , q do 14 Let T 0 be a subset of {t 2 T : \i2Vksi,t 6= ?} of size (Vk); 15 T T \ T 0; 16 for t 2 T 0 do 17 Pick p 2 \i2Vksi,t and set ot p; 18 return outcome o; |
| Open Source Code | No | The paper does not contain any explicit statement about releasing source code for the methodology described, nor does it provide links to any code repositories or mention code in supplementary materials. |
| Open Datasets | No | The paper focuses on theoretical analysis of temporal voting models and complexity, providing proofs and algorithms. It does not use or evaluate on any empirical datasets. Illustrative examples like Example 2.6 are constructed for theoretical purposes, not as publicly available datasets. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments using datasets, thus there is no mention of training/test/validation splits. |
| Hardware Specification | No | The paper is theoretical and focuses on complexity analysis and algorithms. It does not describe any experimental setup that would require specific hardware specifications. |
| Software Dependencies | No | The paper describes algorithms and an Integer Linear Programming (ILP) formulation, but it does not specify any particular software names with version numbers used for implementation or analysis within the research itself. While ILP implies the use of a solver, no specific solver or its version is mentioned. |
| Experiment Setup | No | The paper is theoretical and focuses on algorithm design and complexity analysis. It does not describe any experimental setup, hyperparameters, or training configurations for models. |