A Linear Theory of Multi-Winner Voting

• URL: http://arxiv.org/abs/2503.03082v1
• Date: Wed, 05 Mar 2025 00:44:56 GMT
• Title: A Linear Theory of Multi-Winner Voting
• Authors: Lirong Xia,
• Abstract summary: We introduce a general linear framework that unifies the study of multi-winner voting rules and proportionality axioms.<n>Key proportionality axioms such as Justified Representation (JR), Extended JR (EJR), and their strengthened variants (PJR+, EJR+) can fit within this linear structure as well.<n>Our approach yields near-optimal guarantees for diverse classes of rules, including Thiele methods and ordered weighted average rules.
• Score: 31.513684347195287
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We introduces a general linear framework that unifies the study of multi-winner voting rules and proportionality axioms, demonstrating that many prominent multi-winner voting rules-including Thiele methods, their sequential variants, and approval-based committee scoring rules-are linear. Similarly, key proportionality axioms such as Justified Representation (JR), Extended JR (EJR), and their strengthened variants (PJR+, EJR+), along with core stability, can fit within this linear structure as well. Leveraging PAC learning theory, we establish general and novel upper bounds on the sample complexity of learning linear mappings. Our approach yields near-optimal guarantees for diverse classes of rules, including Thiele methods and ordered weighted average rules, and can be applied to analyze the sample complexity of learning proportionality axioms such as approximate core stability. Furthermore, the linear structure allows us to leverage prior work to extend our analysis beyond worst-case scenarios to study the likelihood of various properties of linear rules and axioms. We introduce a broad class of distributions that extend Impartial Culture for approval preferences, and show that under these distributions, with high probability, any Thiele method is resolute, CORE is non-empty, and any Thiele method satisfies CORE, among other observations on the likelihood of commonly-studied properties in social choice. We believe that this linear theory offers a new perspective and powerful new tools for designing and analyzing multi-winner rules in modern social choice applications.

Related papers

• Optimal Baseline Corrections for Off-Policy Contextual Bandits [61.740094604552475]
  We aim to learn decision policies that optimize an unbiased offline estimate of an online reward metric. We propose a single framework built on their equivalence in learning scenarios. Our framework enables us to characterize the variance-optimal unbiased estimator and provide a closed-form solution for it.
  arXiv  Detail & Related papers  (2024-05-09T12:52:22Z)
• Synergistic eigenanalysis of covariance and Hessian matrices for enhanced binary classification [72.77513633290056]
  We present a novel approach that combines the eigenanalysis of a covariance matrix evaluated on a training set with a Hessian matrix evaluated on a deep learning model. Our method captures intricate patterns and relationships, enhancing classification performance.
  arXiv  Detail & Related papers  (2024-02-14T16:10:42Z)
• Likelihood Ratio Confidence Sets for Sequential Decision Making [51.66638486226482]
  We revisit the likelihood-based inference principle and propose to use likelihood ratios to construct valid confidence sequences. Our method is especially suitable for problems with well-specified likelihoods. We show how to provably choose the best sequence of estimators and shed light on connections to online convex optimization.
  arXiv  Detail & Related papers  (2023-11-08T00:10:21Z)
• Towards Practical Non-Adversarial Distribution Matching [19.196082965354904]
  Distribution matching can be used to learn invariant representations with applications in fairness and robustness. Most prior works resort to adversarial matching methods but the resulting minimax problems are unstable and challenging to optimize. We propose a non-adversarial VAE-based matching method that can be applied to any model pipeline.
  arXiv  Detail & Related papers  (2023-10-30T16:05:46Z)
• Random Matrix Analysis to Balance between Supervised and Unsupervised Learning under the Low Density Separation Assumption [9.620832983703863]
  We introduce QLDS, a linear classification model, where the low density separation assumption is implemented via quadratic margin. We show that particular cases of our algorithm are the least-square support vector machine in the supervised case, the spectral clustering in the fully unsupervised regime, and a class of semi-supervised graph-based approaches.
  arXiv  Detail & Related papers  (2023-10-20T11:46:12Z)
• Dynamic selection of p-norm in linear adaptive filtering via online kernel-based reinforcement learning [8.319127681936815]
  This study addresses the problem of selecting dynamically, at each time instance, the optimal'' p-norm to combat outliers in linear adaptive filtering. Online and data-driven framework is designed via kernel-based reinforcement learning (KBRL)
  arXiv  Detail & Related papers  (2022-10-20T14:49:39Z)
• Revisiting GANs by Best-Response Constraint: Perspective, Methodology, and Application [49.66088514485446]
  Best-Response Constraint (BRC) is a general learning framework to explicitly formulate the potential dependency of the generator on the discriminator. We show that even with different motivations and formulations, a variety of existing GANs ALL can be uniformly improved by our flexible BRC methodology.
  arXiv  Detail & Related papers  (2022-05-20T12:42:41Z)
• Optimal Online Generalized Linear Regression with Stochastic Noise and Its Application to Heteroscedastic Bandits [88.6139446295537]
  We study the problem of online generalized linear regression in the setting of a generalized linear model with possibly unbounded additive noise. We provide a sharp analysis of the classical follow-the-regularized-leader (FTRL) algorithm to cope with the label noise. We propose an algorithm based on FTRL to achieve the first variance-aware regret bound.
  arXiv  Detail & Related papers  (2022-02-28T08:25:26Z)
• Rule Generation for Classification: Scalability, Interpretability, and Fairness [0.0]
  We propose a new rule-based optimization method for classification with constraints. We address interpretability and fairness by assigning cost coefficients to the rules and introducing additional constraints. The proposed method exhibits a good compromise between local interpretability and fairness on the one side, and accuracy on the other side.
  arXiv  Detail & Related papers  (2021-04-21T20:31:28Z)
• MCMH: Learning Multi-Chain Multi-Hop Rules for Knowledge Graph Reasoning [46.68583750992613]
  We consider a generalized form of multi-hop rules, where each rule is a set of relation chains. We propose a two-step approach that first selects a small set of relation chains as a rule and then evaluates the confidence of the target relationship. Empirical results show that our multi-chain multi-hop (MCMH) rules result in superior results compared to the standard single-chain approaches.
  arXiv  Detail & Related papers  (2020-10-05T01:32:20Z)
• On Connections between Regularizations for Improving DNN Robustness [67.28077776415724]
  This paper analyzes regularization terms proposed recently for improving the adversarial robustness of deep neural networks (DNNs) We study possible connections between several effective methods, including input-gradient regularization, Jacobian regularization, curvature regularization, and a cross-Lipschitz functional.
  arXiv  Detail & Related papers  (2020-07-04T23:43:32Z)
• Sparse Methods for Automatic Relevance Determination [0.0]
  We first review automatic relevance determination (ARD) and analytically demonstrate the need to additional regularization or thresholding to achieve sparse models. We then discuss two classes of methods, regularization based and thresholding based, which build on ARD to learn parsimonious solutions to linear problems.
  arXiv  Detail & Related papers  (2020-05-18T14:08:49Z)

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.