Optimal Bounds for the No-Show Paradox via SAT Solving

Speaker : Emma Caizergues
Nokia Bell Labs / Université Paris Dauphine-PSL
Date: 11/01/2023
Time: 11:30 am - 12:30 pm
Location: Room 4A113


The participation criterion is a social choice criterion that characterizes voting rules. A voting rule satisfies this criterion if, considering a is the winner of the election, the addition of a ballot where candidate a is preferred to candidate b should not make b win.
When a voting rule fails the participation criterion, the phenomenon is called the no-show paradox (Fishburn and Brams, 1983). With this paradox comes several questions. One of them is to obtain a bound (on the number of candidates and/or voters) that characterizes the criterion’s satisfaction for a given voting rule.
In this talk, I will first present the participation criterion, some voting rules that satisfy it and some that do not (Moulin, 1987). Then, I will focus an article of Brandt et al. (2017), which presents a way to obtain optimal bounds for the no-show paradox via SAT solving.

Felix Brandt, Christian Geist, and Dominik Peters. Optimal bounds for the no-show paradox via SAT solving. 2017.
Peter C. Fishburn and Steven J. Brams. Paradoxes of preferential voting. 1983.
Hervé Moulin. Condorcet’s principle implies the no show paradox. 1987.