Dear all,
The next Computational Social Choice Seminar at the ILLC will take place this Friday. Suzanne Bloks will speak about the work she did for her Master's thesis on Condorcet winning sets at the London School of Economics, before joining the ILLC a month ago. The abstract is included below.
As always, for more information on the COMSOC Seminar, please consult https://staff.science.uva.nl/u.endriss/seminar/.
All the best, Ulle
-------------------------------------------------------------------------
Speaker: Suzanne Bloks (ILLC) Title: Minimum-sized Condorcet Winning Sets in Preference Profiles Date: Friday 3 May 2019 Time: 16:00 Location: Room F1.15, Science Park 107, Amsterdam
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.