Proportional Aggregation of Preferences for Sequential Decision Making

• URL: http://arxiv.org/abs/2306.14858v1
• Date: Mon, 26 Jun 2023 17:10:10 GMT
• Title: Proportional Aggregation of Preferences for Sequential Decision Making
• Authors: Nikhil Chandak, Shashwat Goel, Dominik Peters
• Abstract summary: 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.
• Score: 20.374669324368625
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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. Instead of going with the most popular choice in each round, we aim for proportional representation. We formalize this aim using axioms based on Proportional Justified Representation (PJR), which were proposed in the literature on multi-winner voting and were recently adapted to multi-issue decision making. The axioms require that every group of $\alpha\%$ of the voters, if it agrees in every round (i.e., approves a common alternative), then those voters must approve at least $\alpha\%$ of the decisions. A stronger version of the axioms requires that every group of $\alpha\%$ of the voters that agrees in a $\beta$ fraction of rounds must approve $\beta\cdot\alpha\%$ of the decisions. We show that three attractive voting rules satisfy axioms of this style. One of them (Sequential Phragm\'en) makes its decisions online, and the other two satisfy strengthened versions of the axioms but make decisions semi-online (Method of Equal Shares) or fully offline (Proportional Approval Voting). The first two are polynomial-time computable, and the latter is based on an NP-hard optimization, but it admits a polynomial-time local search algorithm that satisfies the same axiomatic properties. We present empirical results about the performance of these rules based on synthetic data and U.S. political elections. We also run experiments where votes are cast by preference models trained on user responses from the moral machine dataset about ethical dilemmas.

Related papers

• Representation Bias in Political Sample Simulations with Large Language Models [54.48283690603358]
  This study seeks to identify and quantify biases in simulating political samples with Large Language Models. Using the GPT-3.5-Turbo model, we leverage data from the American National Election Studies, German Longitudinal Election Study, Zuobiao dataset, and China Family Panel Studies.
  arXiv  Detail & Related papers  (2024-07-16T05:52:26Z)
• Efficient Weighting Schemes for Auditing Instant-Runoff Voting Elections [57.67176250198289]
  AWAIRE involves adaptively weighted averages of test statistics, essentially "learning" an effective set of hypotheses to test. We explore schemes and settings more extensively, to identify and recommend efficient choices for practice. A limitation of the current AWAIRE implementation is its restriction to a small number of candidates.
  arXiv  Detail & Related papers  (2024-02-18T10:13:01Z)
• Domain Generalization via Rationale Invariance [70.32415695574555]
  This paper offers a new perspective to ease the challenge of domain generalization, which involves maintaining robust results even in unseen environments. We propose treating the element-wise contributions to the final results as the rationale for making a decision and representing the rationale for each sample as a matrix. Our experiments demonstrate that the proposed approach achieves competitive results across various datasets, despite its simplicity.
  arXiv  Detail & Related papers  (2023-08-22T03:31:40Z)
• 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)
• Data as voters: instance selection using approval-based multi-winner voting [1.597617022056624]
  We present a novel approach to the instance selection problem in machine learning (or data mining) In our model, instances play a double role as voters and candidates. For SVMs, we have obtained slight increases in the average accuracy by using several voting rules that satisfy EJR or PJR.
  arXiv  Detail & Related papers  (2023-04-19T22:00:23Z)
• Most Equitable Voting Rules [30.930621357547487]
  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.
  arXiv  Detail & Related papers  (2022-05-30T03:56:54Z)
• Obvious Manipulability of Voting Rules [105.35249497503527]
  The Gibbard-Satterthwaite theorem states that no unanimous and non-dictatorial voting rule is strategyproof. We revisit voting rules and consider a weaker notion of strategyproofness called not obvious manipulability.
  arXiv  Detail & Related papers  (2021-11-03T02:41:48Z)
• Learning to Elect [7.893831644671976]
  Voting systems have a wide range of applications including recommender systems, web search, product design and elections. We show that set-input neural network architectures such as Set Transformers, fully-connected graph networks and DeepSets are both theoretically and empirically well-suited for learning voting rules.
  arXiv  Detail & Related papers  (2021-08-05T17:55:46Z)
• 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)
• Bandit Linear Optimization for Sequential Decision Making and Extensive-Form Games [102.23975166536326]
  Tree-form sequential decision making (TFSDM) extends classical one-shot decision making by modeling tree-form interactions between an agent and a potentially adversarial environment. It captures the online decision-making problems that each player faces in an extensive-form game, as well as Markov decision processes and partially-observable Markov decision processes where the agent conditions on observed history. In this paper, we give the first algorithm for the bandit linear optimization problem for dilatedDM that offers both (i) linear-time losses and (ii) $O(sqrtT)$ cumulative regret in
  arXiv  Detail & Related papers  (2021-03-08T05:00:13Z)
• Modeling Voters in Multi-Winner Approval Voting [24.002910959494923]
  We study voting behavior in single-winner and multi-winner approval voting scenarios with varying degrees of uncertainty. We find that people generally manipulate their vote to obtain a better outcome, but often do not identify the optimal manipulation. We propose a novel model that takes into account the size of the winning set and human cognitive constraints.
  arXiv  Detail & Related papers  (2020-12-04T19:24:28Z)

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.