Voting with Limited Information and Many Alternatives

DOI10.1137/130936592MaRDI QIDQ5173249zbMATH OpenOpenAlexFDO

Authors Flavio Chierichetti, Jon M. Kleinberg

Publication date 9 February 2015

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1110.1785

zbMATH Keywords

samplingvoting systems

Mathematics Subject Classification ID

Combinatorial probability (60C05) Signaling and communication in game theory (91A28) Voting theory (91B12)

Abstract: The traditional axiomatic approach to voting is motivated by the problem of reconciling differences in subjective preferences. In contrast, a dominant line of work in the theory of voting over the past 15 years has considered a different kind of scenario, also fundamental to voting, in which there is a genuinely "best" outcome that voters would agree on if they only had enough information. This type of scenario has its roots in the classical Condorcet Jury Theorem; it includes cases such as jurors in a criminal trial who all want to reach the correct verdict but disagree in their inferences from the available evidence, or a corporate board of directors who all want to improve the company's revenue, but who have different information that favors different options. This style of voting leads to a natural set of questions: each voter has a {em private signal} that provides probabilistic information about which option is best, and a central question is whether a simple plurality voting system, which tabulates votes for different options, can cause the group decision to arrive at the correct option. We show that plurality voting is powerful enough to achieve this: there is a way for voters to map their signals into votes for options in such a way that --- with sufficiently many voters --- the correct option receives the greatest number of votes with high probability. We show further, however, that any process for achieving this is inherently expensive in the number of voters it requires: succeeding in identifying the correct option with probability at least $1-eta$ requires $Omega(n^{3}epsilo{n}^{-2}loget{a}^{-1})$ voters, where $n$ is the number of options and $epsilon$ is a distributional measure of the minimum difference between the options.

Recommendations

• Voting with limited information and many alternatives
• Voting in the full-information best-choice problem
• Voting under constraints
• Elections with limited information: A multidimensional model
• Incomplete information and communication in voting
• Voting with public information
• Voting and social pressure under imperfect information
• Incomplete information, proportional representation and strategic voting
• Elections, information aggregation, and strategic voting

Cited in

(10)

• One person/one vote is not efficient given information on factions
• Elections with limited information: A multidimensional model
• Who should cast the casting vote? Using sequential voting to amalgamate information
• Voting on tricky questions
• Optimizing positional scoring rules for rank aggregation
• Voting on Actions with Uncertain Outcomes
• Ultimate fate of constrained voters
• Reaching a joint decision with minimal elicitation of voter preferences
• Voting with limited information and many alternatives
• Instance-optimal information-based voting

This page was built for publication: Voting with Limited Information and Many Alternatives

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5173249)