Preference Aggregation in the Generalised Unavailable Candidate Model - Sorbonne Université Access content directly
Conference Papers Year : 2021

Preference Aggregation in the Generalised Unavailable Candidate Model

Nicolas Maudet
Patrice Perny
Paolo Viappiani


While traditional social choice models assume that the set of candidates is known and fixed in advance, recently several researchers have proposed to reject this hypothesis. In particular, the unavailable candidate model of Lu and Boutilier considers voting situations in which some candidates may not be available and focuses on minimising the number of binary disagreements between the voters and the consensus ranking. In this paper, we extend this model and present two new voting rules based on a finer notion of disagreement, called dissatisfaction. The dissatisfaction of a voter is defined as the disutility gap between its preferred available candidate and the candidate elected by the consensus ranking. In the first approach, called ex ante dissatisfaction rule, the disutility is independent of the set of available candidates whereas the second approach, called ex post dissatisfaction rule, assumes that the disutility depends on which candidates are actually available. We provide several results for the two rules. On the one hand, we show that the ex ante rule actually coincides with standard positional scoring rules; therefore, a consensus ranking can be computed in polynomial time. On the other hand, we exhibit strong links between ex post rule and Kemeny rule and we provide a polynomial-time approximation scheme (PTAS) for the ex post problem.
Fichier principal
Vignette du fichier
paper_44 (2).pdf (373.72 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

hal-03384439 , version 1 (18-10-2021)



Arnaud Grivet Sébert, Nicolas Maudet, Patrice Perny, Paolo Viappiani. Preference Aggregation in the Generalised Unavailable Candidate Model. 7th International Conference on Algorithmic Decision Theory, University of Toulouse, Nov 2021, Toulouse, France. pp.35-50, ⟨10.1007/978-3-030-87756-9_3⟩. ⟨hal-03384439⟩
86 View
119 Download



Gmail Mastodon Facebook X LinkedIn More