<Para ID="Par1">An alternative is said to be a Condorcet winner of an election 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 <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$$\theta $$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mi mathvariant="italic">θ</mi> </math> </EquationSource> </InlineEquation> of voters; we refer to such sets as <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$$\theta $$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mi mathvariant="italic">θ</mi> </math> </EquationSource> </InlineEquation>-winning sets. We explore social choice-theoretic and algorithmic aspects of these solution concepts, both theoretically and empirically. Copyright Springer-Verlag Berlin Heidelberg 2015
