The Smoothed Possibility of Social Choice

• URL: http://arxiv.org/abs/2006.06875v3
• Date: Fri, 8 Jan 2021 14:50:56 GMT
• Title: The Smoothed Possibility of Social Choice
• Authors: Lirong Xia
• Abstract summary: We develop a framework to circumvent paradoxes and impossibility theorems in social choice powered by AI and ML. For Condrocet's paradox, we prove that the smoothed likelihood of the paradox either vanishes at an exponential rate as the number of agents increases, or does not vanish at all. For the ANR impossibility on the non-existence of voting rules that simultaneously satisfy anonymity, neutrality, and resolvability, we characterize the rate for the impossibility to vanish.
• Score: 30.930621357547487
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We develop a framework that leverages the smoothed complexity analysis by Spielman and Teng to circumvent paradoxes and impossibility theorems in social choice, motivated by modern applications of social choice powered by AI and ML. For Condrocet's paradox, we prove that the smoothed likelihood of the paradox either vanishes at an exponential rate as the number of agents increases, or does not vanish at all. For the ANR impossibility on the non-existence of voting rules that simultaneously satisfy anonymity, neutrality, and resolvability, we characterize the rate for the impossibility to vanish, to be either polynomially fast or exponentially fast. We also propose a novel easy-to-compute tie-breaking mechanism that optimally preserves anonymity and neutrality for even number of alternatives in natural settings. Our results illustrate the smoothed possibility of social choice -- even though the paradox and the impossibility theorem hold in the worst case, they may not be a big concern in practice.

Related papers

• Convex Markov Games: A Framework for Fairness, Imitation, and Creativity in Multi-Agent Learning [31.958202912400925]
  We introduce the class of convex Markov games that allow general convex preferences over occupancy measures. Despite infinite time horizon and strictly higher generality than Markov games, pure strategy Nash equilibria exist under strict convexity. Our experiments imitate human choices in ultimatum games, reveal novel solutions to the repeated prisoner's dilemma, and find fair solutions in a repeated asymmetric coordination game.
  arXiv  Detail & Related papers  (2024-10-22T00:55:04Z)
• A refined Frauchiger--Renner paradox based on strong contextuality [0.0]
  We observe that logical contextuality is the key ingredient of the FR paradox. We propose a natural extension of Peres's dictum to resolve these extended Wigner's friend paradoxes.
  arXiv  Detail & Related papers  (2024-09-09T10:36:47Z)
• Multi-Armed Bandits with Abstention [62.749500564313834]
  We introduce a novel extension of the canonical multi-armed bandit problem that incorporates an additional strategic element: abstention. In this enhanced framework, the agent is not only tasked with selecting an arm at each time step, but also has the option to abstain from accepting the instantaneous reward before observing it.
  arXiv  Detail & Related papers  (2024-02-23T06:27:12Z)
• On Imperfect Recall in Multi-Agent Influence Diagrams [57.21088266396761]
  Multi-agent influence diagrams (MAIDs) are a popular game-theoretic model based on Bayesian networks. We show how to solve MAIDs with forgetful and absent-minded agents using mixed policies and two types of correlated equilibrium. We also describe applications of MAIDs to Markov games and team situations, where imperfect recall is often unavoidable.
  arXiv  Detail & Related papers  (2023-07-11T07:08:34Z)
• Reproducible Bandits [95.8830340560603]
  A policy in the bandit environment is called reproducible if it pulls, with high probability, the exact same sequence of arms in two different executions. We show that not only do reproducible policies exist, but also they achieve almost the same optimal (non-reproducible) regret bounds in terms of the time horizon. Our results show that even though randomization is crucial for the exploration-exploitation trade-off, an optimal balance can still be achieved while pulling the exact same arms in two different rounds of executions.
  arXiv  Detail & Related papers  (2022-10-04T20:36:45Z)
• 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)
• The Smoothed Likelihood of Doctrinal Paradox [34.534516291695155]
  We show that under mild conditions, the smoothed likelihood of the doctrinal paradox is either $0$, $exp(-Theta(n))$, $Theta(n-1/2)$ or $Theta(1)$. Our main theorem states that under mild conditions, the smoothed likelihood of the doctrinal paradox is either $0$, $exp(-Theta(n))$, $Theta(n-1/2)$ or $Theta(1)$.
  arXiv  Detail & Related papers  (2021-05-11T15:55:47Z)
• On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization [55.937424268654645]
  We consider algorithm-independent lower bounds for the problem of black-box optimization of functions having a bounded norm. We provide a novel proof technique for deriving lower bounds on the regret, with benefits including simplicity, versatility, and an improved dependence on the error probability.
  arXiv  Detail & Related papers  (2020-08-20T03:48:14Z)
• Crush Optimism with Pessimism: Structured Bandits Beyond Asymptotic Optimality [25.627939043735683]
  We study structured bandits for minimizing regret. In this paper we focus on the finite hypothesis and ask if one can achieve the optimality while enjoying bounded regret.
  arXiv  Detail & Related papers  (2020-06-15T20:46:52Z)
• 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.