DeepVoting: Learning Voting Rules with Tailored Embeddings

• URL: http://arxiv.org/abs/2408.13630v1
• Date: Sat, 24 Aug 2024 17:15:20 GMT
• Title: DeepVoting: Learning Voting Rules with Tailored Embeddings
• Authors: Leonardo Matone, Ben Abramowitz, Nicholas Mattei, Avinash Balakrishnan,
• Abstract summary: 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.
• Score: 13.037431161285971
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Aggregating the preferences of multiple agents into a collective decision is a common step in many important problems across areas of computer science including information retrieval, reinforcement learning, and recommender systems. As Social Choice Theory has shown, the problem of designing algorithms for aggregation rules with specific properties (axioms) can be difficult, or provably impossible in some cases. Instead of designing algorithms by hand, one can learn aggregation rules, particularly voting rules, from data. However, the prior work in this area has required extremely large models, or been limited by the choice of preference representation, i.e., embedding. We recast the problem of designing a good voting rule into one of learning probabilistic versions of voting rules that output distributions over a set of candidates. Specifically, we use neural networks to learn probabilistic social choice functions from the literature. We show that embeddings of preference profiles derived from the social choice literature allows us to learn existing voting rules more efficiently and scale to larger populations of voters more easily than other work if the embedding is tailored to the learning objective. Moreover, we show that rules learned using embeddings can be tweaked to create novel voting rules with improved axiomatic properties. Namely, we show that existing voting rules require only minor modification to combat a probabilistic version of the No Show Paradox.

Related papers

• Abductive and Contrastive Explanations for Scoring Rules in Voting [5.928530455750507]
  We design algorithms for computing abductive and contrastive explanations for scoring rules. For the Borda rule, we find a lower bound on the size of the smallest abductive explanations. We conduct simulations to identify correlations between properties of preference profiles and the size of their smallest abductive explanations.
  arXiv  Detail & Related papers  (2024-08-23T09:12:58Z)
• Abstracting Concept-Changing Rules for Solving Raven's Progressive Matrix Problems [54.26307134687171]
  Raven's Progressive Matrix (RPM) is a classic test to realize such ability in machine intelligence by selecting from candidates. Recent studies suggest that solving RPM in an answer-generation way boosts a more in-depth understanding of rules. We propose a deep latent variable model for Concept-changing Rule ABstraction (CRAB) by learning interpretable concepts and parsing concept-changing rules in the latent space.
  arXiv  Detail & Related papers  (2023-07-15T07:16:38Z)
• 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)
• Machine Learning with Probabilistic Law Discovery: A Concise Introduction [77.34726150561087]
  Probabilistic Law Discovery (PLD) is a logic based Machine Learning method, which implements a variant of probabilistic rule learning. PLD is close to Decision Tree/Random Forest methods, but it differs significantly in how relevant rules are defined. This paper outlines the main principles of PLD, highlight its benefits and limitations and provide some application guidelines.
  arXiv  Detail & Related papers  (2022-12-22T17:40:13Z)
• 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)
• 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)
• 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)
• RNNLogic: Learning Logic Rules for Reasoning on Knowledge Graphs [91.71504177786792]
  This paper studies learning logic rules for reasoning on knowledge graphs. Logic rules provide interpretable explanations when used for prediction as well as being able to generalize to other tasks. Existing methods either suffer from the problem of searching in a large search space or ineffective optimization due to sparse rewards.
  arXiv  Detail & Related papers  (2020-10-08T14:47:02Z)
• An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
  We present a general framework for mining constraints from data. In particular, we consider the inference in structured output prediction as an integer linear programming (ILP) problem. We show that our approach can learn to solve 9x9 Sudoku puzzles and minimal spanning tree problems from examples without providing the underlying rules.
  arXiv  Detail & Related papers  (2020-06-18T20:09:53Z)
• Objective Social Choice: Using Auxiliary Information to Improve Voting Outcomes [16.764511357821043]
  How should one combine noisy information from diverse sources to make an inference about an objective ground truth? We propose a multi-arm bandit noise model and count-based auxiliary information set. We find that our rules successfully use auxiliary information to outperform the naive baselines.
  arXiv  Detail & Related papers  (2020-01-27T21:21:19Z)
• Optimal Clustering from Noisy Binary Feedback [75.17453757892152]
  We study the problem of clustering a set of items from binary user feedback. We devise an algorithm with a minimal cluster recovery error rate. For adaptive selection, we develop an algorithm inspired by the derivation of the information-theoretical error lower bounds.
  arXiv  Detail & Related papers  (2019-10-14T09:18:26Z)

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.