Classification of truth revealing social choice algorithms
Time: 14:00 -- Location: LRI, 445
summary: The talk will be on the field of social choices. A group of players want to choose
a subset of a set of objects respecting some properties (maximal weight of the subset,
maximal amount of objects in the subset, ...). To do so, they vote and use a social choice
algorithm to elect the winning subset.
Most of the algorithms we studied aim to solve an optimization problem: maximizing the social
welfare, maximizing the social utility of the least pleased player, etc. Our goal is to find
algorithms which show the property of strategy-proofness: The player's incentive should be
to tell the truth.
Most of the optimal algorithms do not satisfy this property. Worse: if the algorithm allows to
learn and use data on player utilities, it gets easier for these players to lie and obtain a
better utility. The following question emerges from these facts: Can we classify social choice
algorithms based on strategy-proofness? We will show some examples of strategy-proof and not
strategy-proof algorithms, some more general classes which are or are not strategy-proof and
talk about some ongoing work with Johanne Cohen, Victor Glaser, and Daniel Cordeiro to extend
this classification.