Optimal bounds for the no-show paradox via SAT solving

摘要

AbstractOne of the most important desirable properties in social choice theory isCondorcet-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 isparticipation, 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.Highlights?We give a tight bound on the number of voters required for Moulin’s no-show theorem to hold.?展开▼