Nie jesteś zalogowany |
Fast Preference Elicitation and Fairness in Voting
- Prelegent(ci)
- Dominik Peters
- Afiliacja
- Université Paris Dauphine-PSL
- Termin
- 28 kwietnia 2022 10:15
- Pokój
- p. 4050
- Seminarium
- Seminarium „Gry, mechanizmy i sieci społeczne”
Talk 1: Many decision making systems require users to indicate their preferences via a ranking. It is common to elicit such rankings through pairwise comparison queries. By using sorting algorithms, this can be achieved by asking at most O(m log m) adaptive comparison queries. However, in many cases we have some advance (probabilistic) information about the user’s preferences, for instance if we have a learnt model of the user’s preferences or if we expect the user’s preferences to be correlated with those of previous users. For these cases, we design elicitation algorithms that ask fewer questions in expectation, by building on results for average-case sorting.
Talk 2: A voting rule decides on a probability distribution over a set of m alternatives, based on rankings of those alternatives provided by agents. We assume that agents have cardinal utility functions over the alternatives, but voting rules have access to only the rankings induced by these utilities. We evaluate how well voting rules do on measures of social welfare and of proportional fairness, computed based on the hidden utility functions. Using tools from the theory of fair multi-winner elections, we propose the first voting rule which achieves the optimal social welfare distortion Θ(√m) for unit-sum utilities. For fairness, we develop a rule that achieves an optimal O(log m) approximation.
