The Price of Proportional Representation in Temporal Voting

• URL: http://arxiv.org/abs/2605.11157v1
• Date: Mon, 11 May 2026 19:05:30 GMT
• Title: The Price of Proportional Representation in Temporal Voting
• Abstract summary: We study proportional representation in the temporal voting model, where collective decisions are made repeatedly over time over a fixed horizon.<n>We show that imposing proportional representation in the temporal setting can incur a growing, yet sublinear, welfare loss as the number of voters or rounds increases.
• Score: 11.208733293527795
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study proportional representation in the temporal voting model, where collective decisions are made repeatedly over time over a fixed horizon. Prior work has extensively investigated how proportional representation axioms from multiwinner voting (e.g., justified representation (JR) and its variants) can be adapted, satisfied, and verified in this setting. However, much less is understood about their interaction with social welfare. In this work, we quantify the efficiency cost of enforcing proportionality. We formalize the welfare-proportionality tension via the worst-case ratio between the maximum achievable utilitarian welfare and the maximum welfare attainable subject to a proportionality axiom. We show that imposing proportional representation in the temporal setting can incur a growing, yet sublinear, welfare loss as the number of voters or rounds increases. We further identify a clean separation among axioms: for JR, the welfare loss diminishes as the time horizon grows and vanishes asymptotically, whereas for stronger axioms this conflict persists even with many rounds. Moreover, we prove that welfare maximization under each axiom is NP-complete and APX-hard, even under static preferences and bounded-degree approvals, and provide fixed-parameter algorithms under several natural structural parameters.

Related papers

• Geometry of Relaxed Fair Regression: A Unified Framework for Aware and Unaware Settings [0.0]
  principled methods for obtaining accurate predictions under relaxed fairness constraints are largely missing.<n>Our framework unifies both the emphaware and emphunaware settings and characterizes optimal prediction functions via optimal transport maps.<n>Building on these theoretical characterizations, we propose an algorithm that is simple to implement, computationally efficient, and consistently matches or outperforms state-of-the-art baselines on real-world benchmarks.
  arXiv  Detail & Related papers  (2026-05-27T09:45:16Z)
• Fixed Points and Stochastic Meritocracies: A Long-Term Perspective [11.2610829816461]
  We study group fairness in the context of feedback loops induced by meritocratic selection into programs that themselves confer additional advantage.<n>We show that, when the benefit of the program (or the harm of not getting into it) is completely symmetric, disparities between the two populations will eventually dissipate.<n>We also find that significant disparities can arise due to chance even from completely symmetric initial conditions.
  arXiv  Detail & Related papers  (2025-10-08T19:23:57Z)
• Optimal bounds for dissatisfaction in perpetual voting [84.02572742131521]
  We consider a perpetual approval voting method that guarantees that no voter is dissatisfied too many times.<n>We identify a sufficient condition on voter behavior under which a sublinear growth of dissatisfaction is possible.<n>We present a voting method with sublinear guarantees on dissatisfaction under bounded conflicts, based on the standard techniques from prediction with expert advice.
  arXiv  Detail & Related papers  (2024-12-20T19:58:55Z)
• Fairness-Accuracy Trade-Offs: A Causal Perspective [58.06306331390586]
  We analyze the tension between fairness and accuracy from a causal lens for the first time.<n>We show that enforcing a causal constraint often reduces the disparity between demographic groups.<n>We introduce a new neural approach for causally-constrained fair learning.
  arXiv  Detail & Related papers  (2024-05-24T11:19:52Z)
• Multi-Armed Bandits with Abstention [62.749500564313834]
  We introduce a novel extension of the canonical multi-armed bandit problem that incorporates an additional strategic element: abstention. In this enhanced framework, the agent is not only tasked with selecting an arm at each time step, but also has the option to abstain from accepting the instantaneous reward before observing it.
  arXiv  Detail & Related papers  (2024-02-23T06:27:12Z)
• Optimal Best Arm Identification with Fixed Confidence in Restless Bandits [66.700654953613]
  We study best arm identification in a restless multi-armed bandit setting with finitely many arms. The discrete-time data generated by each arm forms a homogeneous Markov chain taking values in a common, finite state space. It is demonstrated that tracking the long-term behavior of a certain Markov decision process and its state-action visitation proportions are the key ingredients in analyzing the converse and achievability bounds.
  arXiv  Detail & Related papers  (2023-10-20T10:04:05Z)
• The Leximin Approach for a Sequence of Collective Decisions [6.3734441349747035]
  We analyze the fairness of three known mechanisms: round-robin, maximum Nash welfare, and leximin. In the offline setting, we show that the three mechanisms fail to find a proportional or approximate-proportional outcome. In the online setting, we show that it is impossible to guarantee proportionality or its relaxations.
  arXiv  Detail & Related papers  (2023-05-29T11:28:27Z)
• Proportional Fairness in Obnoxious Facility Location [70.64736616610202]
  We propose a hierarchy of distance-based proportional fairness concepts for the problem. We consider deterministic and randomized mechanisms, and compute tight bounds on the price of proportional fairness. We prove existence results for two extensions to our model.
  arXiv  Detail & Related papers  (2023-01-11T07:30:35Z)
• Achieving Proportionality up to the Maximin Item with Indivisible Goods [14.002498730240902]
  We study the problem of fairly allocating indivisible goods and focus on the classic fairness notion of proportionality. Recent work has established that even approximate versions of proportionality (PROPx) may be impossible to achieve even for small instances. We show how to reach an allocation satisfying this notion for any instance involving up to five agents with additive valuations.
  arXiv  Detail & Related papers  (2020-09-20T19:21:19Z)
• Fair Influence Maximization: A Welfare Optimization Approach [34.39574750992602]
  We provide a principled characterization of the properties that a fair influence algorithm should satisfy. Under this framework, the trade-off between fairness and efficiency can be controlled by a single design aversion parameter. Our framework encompasses as special cases leximin and proportional fairness.
  arXiv  Detail & Related papers  (2020-06-14T14:08:10Z)
• Public Bayesian Persuasion: Being Almost Optimal and Almost Persuasive [57.47546090379434]
  We study the public persuasion problem in the general setting with: (i) arbitrary state spaces; (ii) arbitrary action spaces; (iii) arbitrary sender's utility functions. We provide a quasi-polynomial time bi-criteria approximation algorithm for arbitrary public persuasion problems that, in specific settings, yields a QPTAS.
  arXiv  Detail & Related papers  (2020-02-12T18:59:18Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.