A General Theory of Proportionality with Additive Utilities

• URL: http://arxiv.org/abs/2602.08504v1
• Date: Mon, 09 Feb 2026 10:55:13 GMT
• Title: A General Theory of Proportionality with Additive Utilities
• Authors: Piotr Skowron,
• Abstract summary: We consider a model where a subset of candidates must be selected based on voter preferences.<n>This model generalizes committee elections with diversity constraints, participatory budgeting, and public decision-making.
• Score: 7.568094754725703
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider a model where a subset of candidates must be selected based on voter preferences, subject to general constraints that specify which subsets are feasible. This model generalizes committee elections with diversity constraints, participatory budgeting (including constraints specifying how funds must be allocated to projects from different pools), and public decision-making. Axioms of proportionality have recently been defined for this general model, but the proposed rules apply only to approval ballots, where each voter submits a subset of candidates she finds acceptable. We propose proportional rules for cardinal ballots, where each voter assigns a numerical value to each candidate corresponding to her utility if that candidate is selected. In developing these rules, we also introduce methods that produce proportional rankings, ensuring that every prefix of the ranking satisfies proportionality.

Related papers

• To Each Metric Its Decoding: Post-Hoc Optimal Decision Rules of Probabilistic Hierarchical Classifiers [43.97690773039761]
  We propose a framework for the optimal decoding of an output probability distribution with respect to a target metric.<n>We derive optimal decision rules for increasingly complex prediction settings, providing universal algorithms when candidates are limited to the set of nodes.
  arXiv  Detail & Related papers  (2025-06-02T11:29:40Z)
• Proportionality in Thumbs Up and Down Voting [20.84797796151438]
  We propose two conceptually distinct approaches to interpret proportionality in the presence of up and down votes.<n>The first approach treats the satisfaction from electing candidates as comparable, leading to combined proportionality guarantees.<n>The second approach considers veto power separately, introducing guarantees distinct from traditional proportionality.
  arXiv  Detail & Related papers  (2025-03-03T19:02:37Z)
• A consensus set for the aggregation of partial rankings: the case of the Optimal Set of Bucket Orders Problem [46.752018687842344]
  In rank aggregation problems (RAP), the solution is usually a consensus ranking that generalizes a set of input orderings.<n>We propose to provide, as the solution to an RAP, a set of rankings to better explain the preferences expressed in the input orderings.
  arXiv  Detail & Related papers  (2025-02-19T14:32:16Z)
• Verifying Proportionality in Temporal Voting [29.69443607539022]
  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.<n>We focus on the complexity of verifying whether a given outcome offers proportional representation.
  arXiv  Detail & Related papers  (2025-02-09T16:30:34Z)
• 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)
• Centralized Selection with Preferences in the Presence of Biases [25.725937202777267]
  The paper focuses on the setting in which candidates are divided into multiple groups and the observed utilities of candidates in some groups are biased--systematically lower than their true utilities. An algorithm is presented along with proof that it produces selections that achieve near-optimal group fairness with respect to preferences while also nearly maximizing the true utility under distributional assumptions.
  arXiv  Detail & Related papers  (2024-09-07T19:47:13Z)
• The Distortion of Binomial Voting Defies Expectation [26.481697906062095]
  We study the expected distortion of voting rules with respect to an underlying distribution over voter utilities. Our main contribution is the design and analysis of a novel and intuitive rule, binomial voting.
  arXiv  Detail & Related papers  (2023-06-27T17:50:58Z)
• Beyond Normal: On the Evaluation of Mutual Information Estimators [52.85079110699378]
  We show how to construct a diverse family of distributions with known ground-truth mutual information. We provide guidelines for practitioners on how to select appropriate estimator adapted to the difficulty of problem considered.
  arXiv  Detail & Related papers  (2023-06-19T17:26:34Z)
• Best of Both Distortion Worlds [29.185700008117173]
  We study the problem of designing voting rules that take as input the ordinal preferences of $n$ agents over a set of $m$ alternatives. The input to the voting rule is each agent's ranking of the alternatives from most to least preferred, yet the agents have more refined (cardinal) preferences that capture the intensity with which they prefer one alternative over another. We prove that one can achieve the best of both worlds by designing new voting rules, that simultaneously achieve near-optimal distortion guarantees in both distortion worlds.
  arXiv  Detail & Related papers  (2023-05-30T23:24:01Z)
• Dense Hybrid Proposal Modulation for Lane Detection [72.49084826234363]
  We present a dense hybrid proposal modulation (DHPM) method for lane detection. We densely modulate all proposals to generate topologically and spatially high-quality lane predictions. Our DHPM achieves very competitive performances on four popular datasets.
  arXiv  Detail & Related papers  (2023-04-28T14:31:11Z)
• Expected Frequency Matrices of Elections: Computation, Geometry, and Preference Learning [58.23459346724491]
  We use the "map of elections" approach of Szufa et al. (AAMAS 2020) to analyze several well-known vote distributions. We draw the "skeleton map" of distributions, evaluate its robustness, and analyze its properties.
  arXiv  Detail & Related papers  (2022-05-16T17:40:22Z)
• BRIO: Bringing Order to Abstractive Summarization [107.97378285293507]
  We propose a novel training paradigm which assumes a non-deterministic distribution. Our method achieves a new state-of-the-art result on the CNN/DailyMail (47.78 ROUGE-1) and XSum (49.07 ROUGE-1) datasets.
  arXiv  Detail & Related papers  (2022-03-31T05:19:38Z)
• On the Complexity of Winner Determination and Strategic Control in Conditional Approval Voting [11.180055556912208]
  Conditional Minisum (CMS) is a voting rule for multi-issue elections with preferential dependencies.<n>We show that CMS can be viewed as a solution that achieves a satisfactory tradeoff between expressiveness and computational efficiency.
  arXiv  Detail & Related papers  (2022-02-03T16:15:54Z)
• Bribery as a Measure of Candidate Success: Complexity Results for Approval-Based Multiwinner Rules [58.8640284079665]
  We study the problem of bribery in multiwinner elections, for the case where the voters cast approval ballots (i.e., sets of candidates they approve) We consider a number of approval-based multiwinner rules (AV, SAV, GAV, RAV, approval-based Chamberlin--Courant, and PAV) In general, our problems tend to be easier when we limit out bribery actions on increasing the number of approvals of the candidate that we want to be in a winning committee.
  arXiv  Detail & Related papers  (2021-04-19T08:26:40Z)
• Evaluating approval-based multiwinner voting in terms of robustness to noise [10.135719343010177]
  We show that approval-based multiwinner voting is always robust to reasonable noise. We further refine this finding by presenting a hierarchy of rules in terms of how robust to noise they are.
  arXiv  Detail & Related papers  (2020-02-05T13:17:43Z)

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.