On the Complexity of Finding a Diverse and Representative Committee using a Monotone, Separable Positional Multiwinner Voting Rule

• URL: http://arxiv.org/abs/2211.13217v1
• Date: Wed, 23 Nov 2022 18:56:44 GMT
• Title: On the Complexity of Finding a Diverse and Representative Committee using a Monotone, Separable Positional Multiwinner Voting Rule
• Authors: Kunal Relia
• Abstract summary: A growing line of research in computational social choice concerns the use of constraints to ensure fairness in elections. Recent work proposed a model to find a diverse emphand representative committee and studied the model's computational aspects. Here, we classify the complexity of finding a diverse and representative committee using a monotone, separable positional multiwinner voting rule.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Fairness in multiwinner elections, a growing line of research in computational social choice, primarily concerns the use of constraints to ensure fairness. Recent work proposed a model to find a diverse \emph{and} representative committee and studied the model's computational aspects. However, the work gave complexity results under major assumptions on how the candidates and the voters are grouped. Here, we close this gap and classify the complexity of finding a diverse and representative committee using a monotone, separable positional multiwinner voting rule, conditioned \emph{only} on the assumption that P $\neq$ NP.

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)
• On Efficient Computation of DiRe Committees [4.8951183832371]
  Consider a committee election consisting of a set of candidates who are divided into arbitrary groups each of size emphat most two. A diversity constraint stipulates the selection of emphat least one candidate from each group. A representation constraint stipulates the selection of emphat least one candidate from each population who has a non-null set of approved candidates.
  arXiv  Detail & Related papers  (2024-02-29T17:13:30Z)
• Temporal Fairness in Multiwinner Voting [28.930682052949017]
  Multiwinner voting captures a wide variety of settings, from parliamentary elections in democratic systems to product placement in online shopping platforms. There is a large body of work dealing with axiomatic characterizations, computational complexity, and algorithmic analysis of multiwinner voting rules. We propose a unified framework for studying temporal fairness in this domain, drawing connections with various existing bodies of work, and consolidating them within a general framework.
  arXiv  Detail & Related papers  (2023-12-07T16:38:32Z)
• Synergies between Disentanglement and Sparsity: Generalization and Identifiability in Multi-Task Learning [79.83792914684985]
  We prove a new identifiability result that provides conditions under which maximally sparse base-predictors yield disentangled representations. Motivated by this theoretical result, we propose a practical approach to learn disentangled representations based on a sparsity-promoting bi-level optimization problem.
  arXiv  Detail & Related papers  (2022-11-26T21:02:09Z)
• Fairly Allocating Utility in Constrained Multiwinner Elections [0.0]
  A common denominator to ensure fairness across all such contexts is the use of constraints. Across these contexts, the candidates selected to satisfy the given constraints may systematically lead to unfair outcomes for historically disadvantaged voter populations. We develop a model to select candidates that satisfy the constraints fairly across voter populations.
  arXiv  Detail & Related papers  (2022-11-23T10:04:26Z)
• 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)
• The Complexity of Learning Approval-Based Multiwinner Voting Rules [9.071560867542647]
  We study the learnability of multiwinner voting, focusing on the class of approval-based committee scoring (ABCS) rules. Our goal is to learn a target rule (i.e., to learn the corresponding scoring function) using information about the winning committees of a small number of profiles. We prove that deciding whether there exists some ABCS rule that makes a given committee winning in a given profile is a hard problem.
  arXiv  Detail & Related papers  (2021-10-01T08:25:05Z)
• DiRe Committee : Diversity and Representation Constraints in Multiwinner Elections [0.0]
  We develop a model, DiRe Committee Winner Determination (DRCWD), which delineates candidate and voter attributes to select a committee. We develop a feasibility-based algorithm, which finds the winning DiRe committee in under two minutes on 63% of the instances of synthetic datasets and on 100% of instances of real-world datasets. Overall, DRCWD motivates that a study of multiwinner elections should consider both its actors, namely candidates and voters, as candidate-specific "fair" models can unknowingly harm voter populations, and vice versa.
  arXiv  Detail & Related papers  (2021-07-15T14:32:56Z)
• Preference learning along multiple criteria: A game-theoretic perspective [97.94912276610002]
  We generalize the notion of a von Neumann winner to the multi-criteria setting by taking inspiration from Blackwell's approachability. Our framework allows for non-linear aggregation of preferences across criteria, and generalizes the linearization-based approach from multi-objective optimization. We show that the Blackwell winner of a multi-criteria problem instance can be computed as the solution to a convex optimization problem.
  arXiv  Detail & Related papers  (2021-05-05T03:23:11Z)
• 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)
• 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.