TY - JOUR

T1 - Optimal bounds for the no-show paradox via SAT solving

AU - Brandt, Felix

AU - Geist, Christian

AU - Peters, Dominik

N1 - Publisher Copyright:
© 2016 Elsevier B.V.

PY - 2017/11

Y1 - 2017/11

N2 - One of the most important desirable properties in social choice theory is Condorcet-consistency, which requires that a voting rule should return an alternative that is preferred to any other alternative by some majority of voters. Another desirable property is participation, which requires that no voter should be worse off by joining an electorate. A seminal result by Moulin (1988) has shown that Condorcet-consistency and participation are incompatible whenever there are at least 4 alternatives and 25 voters. We leverage SAT solving to obtain an elegant human-readable proof of Moulin's result that requires only 12 voters. Moreover, the SAT solver is able to construct a Condorcet-consistent voting rule that satisfies participation as well as a number of other desirable properties for up to 11 voters, proving the optimality of the above bound. We also obtain tight results for set-valued and probabilistic voting rules, which complement and significantly improve existing theorems.

AB - One of the most important desirable properties in social choice theory is Condorcet-consistency, which requires that a voting rule should return an alternative that is preferred to any other alternative by some majority of voters. Another desirable property is participation, which requires that no voter should be worse off by joining an electorate. A seminal result by Moulin (1988) has shown that Condorcet-consistency and participation are incompatible whenever there are at least 4 alternatives and 25 voters. We leverage SAT solving to obtain an elegant human-readable proof of Moulin's result that requires only 12 voters. Moreover, the SAT solver is able to construct a Condorcet-consistent voting rule that satisfies participation as well as a number of other desirable properties for up to 11 voters, proving the optimality of the above bound. We also obtain tight results for set-valued and probabilistic voting rules, which complement and significantly improve existing theorems.

UR - http://www.scopus.com/inward/record.url?scp=85005982556&partnerID=8YFLogxK

U2 - 10.1016/j.mathsocsci.2016.09.003

DO - 10.1016/j.mathsocsci.2016.09.003

M3 - Article

AN - SCOPUS:85005982556

SN - 0165-4896

VL - 90

SP - 18

EP - 27

JO - Mathematical social sciences

JF - Mathematical social sciences

ER -