A Few Good Choices

A Condorcet winning set addresses the Condorcet paradox by selecting a few candidates-rather than a single winner-such that no unselected alternative is preferred to all of them by a majority of voters. This idea extends to α-undominated sets, which ensure the same property for any α-fraction of voters and are guaranteed to exist in constant size for any α. However, the requirement that an outsider be preferred to every member of the set can be overly restrictive and difficult to justify in many applications. Motivated by this, we introduce a more flexible notion: (t, α)-undominated sets. Here, each voter compares an outsider to their t-th most preferred member of the set, and the set is undominated if no outsider is preferred by more than an α-fraction of voters. This framework subsumes prior definitions, recovering Condorcet winning sets when (t = 1, α = 1/2) and α-undominated sets when t = 1, and introduces a new, tunable notion of collective acceptability for t > 1. We establish three main results:

• We prove that a (t, α)-undominated set of size O(t/α) exists for all values of t and α.

• We show that as t becomes large, the minimum size of such a set approaches t/α, which is asymptotically optimal.

• In the special case t = 1, we improve the bound on the size of an α-undominated set given by Charikar et al. (2025a). As a consequence, we show that a Condorcet winning set of five candidates exists, improving their bound of six.