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.