Most Equitable Voting Rules

• URL: http://arxiv.org/abs/2205.14838v3
• Date: Thu, 13 Jul 2023 08:06:49 GMT
• Title: Most Equitable Voting Rules
• Authors: Lirong Xia
• Abstract summary: ANR impossibility -- there is no voting rule that satisfies anonymity, neutrality, and resolvability -- holds even in the simple setting of two alternatives and two agents. We propose a novel and strong notion of most equitable refinements that optimally preserves anonymity and neutrality for any irresolute rule that satisfies the two axioms.
• Score: 30.930621357547487
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In social choice theory, anonymity (all agents being treated equally) and neutrality (all alternatives being treated equally) are widely regarded as ``minimal demands'' and ``uncontroversial'' axioms of equity and fairness. However, the ANR impossibility -- there is no voting rule that satisfies anonymity, neutrality, and resolvability (always choosing one winner) -- holds even in the simple setting of two alternatives and two agents. How to design voting rules that optimally satisfy anonymity, neutrality, and resolvability remains an open question. We address the optimal design question for a wide range of preferences and decisions that include ranked lists and committees. Our conceptual contribution is a novel and strong notion of most equitable refinements that optimally preserves anonymity and neutrality for any irresolute rule that satisfies the two axioms. Our technical contributions are twofold. First, we characterize the conditions for the ANR impossibility to hold under general settings, especially when the number of agents is large. Second, we propose the most-favorable-permutation (MFP) tie-breaking to compute a most equitable refinement and design a polynomial-time algorithm to compute MFP when agents' preferences are full rankings.

Related papers

• DeepVoting: Learning Voting Rules with Tailored Embeddings [13.037431161285971]
  We recast the problem of designing a good voting rule into one of learning probabilistic versions of voting rules. We show that embeddings of preference profiles derived from the social choice literature allows us to learn existing voting rules more efficiently. We also show that rules learned using embeddings can be tweaked to create novel voting rules with improved axiomatic properties.
  arXiv  Detail & Related papers  (2024-08-24T17:15:20Z)
• Thompson Exploration with Best Challenger Rule in Best Arm Identification [66.33448474838342]
  We study the fixed-confidence best arm identification problem in the bandit framework. We propose a novel policy that combines Thompson sampling with a computationally efficient approach known as the best challenger rule.
  arXiv  Detail & Related papers  (2023-10-01T01:37:02Z)
• Proportional Aggregation of Preferences for Sequential Decision Making [20.374669324368625]
  We study the problem of fair sequential decision making given voter preferences. In each round, a decision rule must choose a decision from a set of alternatives where each voter reports which of these alternatives they approve. We formalize this aim using axioms based on Proportional Justified Representation.
  arXiv  Detail & Related papers  (2023-06-26T17:10:10Z)
• 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)
• Social Mechanism Design: A Low-Level Introduction [31.564788318133264]
  We show that agents have preferences over both decision outcomes and the rules or procedures used to make decisions. We identify simple, intuitive preference structures at low levels that can be generalized to form the building blocks of preferences at higher levels. We analyze algorithms for acceptance in two different domains: asymmetric dichotomous choice and constitutional amendment.
  arXiv  Detail & Related papers  (2022-11-15T20:59:34Z)
• A Unifying Framework for Online Optimization with Long-Term Constraints [62.35194099438855]
  We study online learning problems in which a decision maker has to take a sequence of decisions subject to $m$ long-term constraints. The goal is to maximize their total reward, while at the same time achieving small cumulative violation across the $T$ rounds. We present the first best-of-both-world type algorithm for this general class problems, with no-regret guarantees both in the case in which rewards and constraints are selected according to an unknown model, and in the case in which they are selected at each round by an adversary.
  arXiv  Detail & Related papers  (2022-09-15T16:59:19Z)
• Necessarily Optimal One-Sided Matchings [49.0517583218216]
  We study the classical problem of matching $n$ agents to $n$ objects, where the agents have ranked preferences over the objects. Instead of asking the agents to report their complete preferences, our goal is to learn a desirable matching from partial preferences. We design efficient algorithms to check if a given matching is NPO or NRM, and to check whether such a matching exists given top-$k$ partial preferences.
  arXiv  Detail & Related papers  (2020-07-17T16:01:34Z)
• SetRank: A Setwise Bayesian Approach for Collaborative Ranking from Implicit Feedback [50.13745601531148]
  We propose a novel setwise Bayesian approach for collaborative ranking, namely SetRank, to accommodate the characteristics of implicit feedback in recommender system. Specifically, SetRank aims at maximizing the posterior probability of novel setwise preference comparisons. We also present the theoretical analysis of SetRank to show that the bound of excess risk can be proportional to $sqrtM/N$.
  arXiv  Detail & Related papers  (2020-02-23T06:40:48Z)
• 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.