Choosing collectively optimal sets of alternatives based on the Condorcet criterion
Edith Elkind, Jérôme Lang and Abdallah Saffidine
In elections, an alternative is said to be a Condorcet winner if it is preferred to any other alternative by a majority of voters. While this is a very attractive solution concept, many elections do not have a Condorcet winner. In this paper, we propose a set-valued relaxation of this concept, which we call a "Condorcet winning set": such sets consist of alternatives that collectively dominate any other alternative. We also consider a more general version of this concept, where instead of domination by a majority of voters we require domination by a given fraction theta of voters; we refer to this concept as "theta-winning set". We explore social choice-theoretic and algorithmic aspects of these solution concepts, both theoretically and empirically, and argue that they are relevant for applications of voting in multi-agent decision-making scenarios.