The Condorcet Dimension of Metric Spaces

An ideal winner in such an election is a Condorcet winner, a candidate that "beats" any other candidate in a pairwise voting contest. Formally, i C is a Condorcet winner if, for every candidate j C\{i}, more than half of the voters prefer i over j. To avoid ties, we assume the number n of voters is odd. Unfortunately, it is easy to construct elections where a Condorcet winner does not exist; indeed typically there is no Condorcet winner. Given this, Elkind, Lang and Saffidine [12] proposed a relaxation where, rather than a single winning candidate, we desire a set of winning candidates that collectively beats any other candidate. Specifically, a set of candidates S C is a Condorcet winning set if, for every candidate j C \S, more than half of the voters prefer some (voter-dependent) candidate in S to j. Elkind et al. [12] showed that a Condorcet winning set always exists provided we allow the winning set to be large enough.