Edith
Elkind,
Department
of
Computer
Science
University
of
Oxford
Suppose that a group of agents want to select k > 1 alternatives from a given set, and each agent indicates which of the alternatives are acceptable to her: the alternatives could be conference submissions, applicants for a scholarship or locations for a fast food chain. In this setting it is natural to require that the set of winners represents the voters fairly, in the sense that large groups of voters with similar preferences have at least some of their approved alternatives in the winning set.
We describe several ways to formalize this idea; our axiomatization enables us to characterize a voting rule that was proposed by a Danish polymath Thiele in the XIXth century. However, this rule has an NP-hard winner determination algorithm; to overcome this issue we design an efficient approximation algorithm for this rule that satisfies the most demanding of our axioms.
Bio: Edith Elkind is a Professor at University of Oxford, where her work is supported by an ERC Starting Grant. She obtained her PhD from Princeton in 2005, and has held positions in UK, Israel and Singapore since then. Her interests are in algorithmic game theory and computational social choice, and she has published over 100 papers in top AI and algorithmic game theory venues on these topics. She has served as a program chair of AAMAS ’15 and ACM EC ’18 and a general chair of AAMAS ’19, and she was recently elected to be the program chair of IJCAI ’23.