3 May 2019, Computational Social Choice Seminar, Suzanne Bloks

Abstract

This talk approaches an open question in Computational Social Choice Theory, posed by Elkind, Lang and Saffidine in 2015: Do there exist preference profiles in which the minimum size of a Condorcet winning set is bigger than 3? A Condorcet winning set is a generalization of the Condorcet winner. A set Y is a Condorcet winning set if for every candidate z not in Y a majority of voters prefer some candidate in Y to z. Elkind, Lang and Saffidine have constructed a preference profile in which the minimum size of a Condorcet winning set is 3. That is, there is no Condorcet winner or a Condorcet winning set of size 2 in the constructed profile. It remains an open question whether preference profiles can be constructed with minimum Condorcet winning sets of size 4 or higher. In this talk, we will explore this question by relating Condorcet winning sets in preference profiles to dominating sets in tournaments. The concept of dominating sets in tournaments is related to but stronger than the concept of Condorcet winning sets in preference profiles. We will use this relation to make advancements towards constructing preference profiles with Condorcet dimension 4 or higher.

For more information on the Computational Social Choice Seminar, please consult https://staff.science.uva.nl/u.endriss/seminar/.