14 marca 2017 10:15
[Seminarium ZOK] Piotr Skowron, "Multiwinner Elections: Overview and Challenges"
Wtorek, 10:15, sala 140.
Abstract: In a multiwinner election we are given a set of m alternatives, A, a population of n voters, N, each endowed with preferences over the alternatives, and an integer k. In the most typical election model, voters express their preferences by providing orders over the set of alternatives: a voter ranks his or her most preferred alternative first, his or her second best alternative second, etc. A multiwinner election rule is a formal process of selecting a subset of k alternatives that, in some sense, are best from the perspective of the population.
Multiwinner election rules are very interesting due to their diverse applications. Selecting a parliament is perhaps the most classic example of their applicability. Yet, they are used in a variety of other scenarios ranging from picking a list of items a search engine should display, through deciding which set of products a company should offer to its customers, shortlisting candidates for an interview, solving a wide range of resource allocation problems, segmentation problems, and facility location problems to improving genetic algorithms.
In my talk I will give an overview of several interesting classes of multiwinner election systems and describe a few examples of problems regarding these classes of voting rules. These are mostly computational problems, but our community is also interested in studying structural properties of election systems, which usually requires applying different techniques of discrete mathematics. I will mention a few open problems, which I find particularly interesting.