1 Problem statement, notation, and proof overview↩︎

An election consists of a set \(V\) of \(n\) voters, a set \(C\) of \(m\) candidates, and a linear preference order \(\succ_v\) over the candidates for each voter \(v \in V\). We use \(\tfrac1n|a \succ S|\) to denote the fraction of voters that prefer candidate \(a\) over each candidate in the committee (set of candidates) \(S\). A Condorcet winning set (introduced by [2], [3]) is a committee \(S\) such that for all candidates \(a \in C\), \(\tfrac1n|a \succ S| < \frac{1}{2}\).

The goal of this note is to prove the following result, due to [1].

The general proof strategy used by [1], as well as its antecedents [4] and [5], is the following:

1. Construct a distribution \(D\) over candidates such that all candidates \(a\) tend to be “ranked low” by voters (in comparison to \(D\)).

2. Show that if we construct the committee \(S\) using samples from \(D\), with positive probability \(S\) tends to be “ranked high” by voters (in comparison to \(D\)).

3. Argue that if \(a\) tends to be ranked low and \(S\) tends to be ranked high, then a majority of voters cannot prefer \(a\) over \(S\).

[4] and [5] use distributions adapted from a stable lottery [6], the equilibrium distribution of a certain two-player game, whose existence is proved via the minimax theorem. [1] use a distribution adapted from a Lindahl equilibrium, whose existence is proved via the Kakutani fixed-point theorem. At a very high level, the Lindahl equilibrium is a market equilibrium which gives each voter a fixed budget and personalized prices for each candidate, and assigns the voters a common fractional allocation of candidates that each voter likes as much as what they would get if they could spend their budget freely. (We note that usually the agents in a Lindahl equilibrium have cardinal utilities, and some effort is needed to adapt to a setting with ordinal preferences.)

While the market setup of the Lindahl equilibrium provides helpful intuition for why the distribution \(D\) is reasonable, it can take some effort to parse for readers unfamiliar with market equilibria. In an effort to make the proof more accessible to this audience, we will present a more streamlined version of the [1] proof which applies the Kakutani fixed-point theorem directly rather than going through the Lindahl equilibrium. An upcoming paper of [7] also uses a similar approach to give a proof of [thm:five] and several other results, and we emphasize that this note is purely for expository purposes.

As a final piece of notation, we formalize what it means for candidates to be “ranked low” or “ranked high” by voters. Voter \(v\)’s rank of a candidate \(a\) with respect to a distribution \(D\) over candidates is the probability that \(v\) prefers \(a\) over a random candidate \(b\sim D\). Borrowing notation from [5], \[\mathop{\mathrm{rank}}_v(a; D) := \Pr_{b\sim D}[a \succ b].\]

The intuition for the ranks is best understood with the following picture. Imagine creating a block for each candidate \(a\), whose width is the probability mass of \(a\) in \(D\), and having each voter arrange these blocks along the interval \([0, 1]\) in increasing order of preference (see 1 for an example). Then \(\mathop{\mathrm{rank}}_v(a;D)\) is precisely the bottom (leftmost point) of the block corresponding to \(a\).

The pictorial representation also gives a helpful alternative way of understanding samples from \(D\). From each voter’s perspective, \(b\sim D\) is equivalent to sampling a real number \(r\sim \Unif(0, 1)\), and choosing the candidate whose block contains \(r\). (Formally, the candidate \(b\) for which \(\mathop{\mathrm{rank}}_v(b;D)\) is maximal subject to being at most \(r\).) With this view we get the following two immediate consequences:

• The random variable \(\mathop{\mathrm{rank}}_v(b;D)\) with \(b \sim D\) is stochastically dominated by \(r\sim \Unif(0, 1)\).

• The random variable \(\displaystyle\min_{a: a\succ_v b} \mathop{\mathrm{rank}}_v(a;D)\) with \(b \sim D\) stochastically dominates \(r\sim \Unif(0, 1)\).¹

2 Five candidates suffice↩︎

The following key lemma captures the sense in which all candidates tend to be “ranked low” by the voters. See 2 for a visual depiction of what the lemma shows.

Note that [lem:key] can be extended² to show that for any continuous non-decreasing function \(g: [0,1] \to \mathbb{R}_{\geq 0}\), there exists a distribution \(D_g\) such that for all candidates \(a\), \[\Ev_{v\sim V}[g(\mathop{\mathrm{rank}}_v(a;D_g))] \leq \int_0^1 g(x) \mathop{}\!\mathrm{d}x.\] In fact, the proof is a little simpler, since we can just use \(h(a;D) = \Ev_{v\sim V}[g(\mathop{\mathrm{rank}}_v(a;D))]\) in place of \(h^+\) and \(h^-\), and the continuity of \(g\) makes the Kakutani conditions trivial to check. This approach is isomorphic to how the argument of [1] actually works, with \(g\) representing the “random income distribution.” They ultimately set \(g\) to be a continuous approximation of the function \(x \mapsto \boldsymbol{1}[x > t]\) to show a version of [lem:key] with \(1 - t\) replaced with \(1 - t + \varepsilon\) for any fixed \(\varepsilon > 0\) (which is a practically inconsequential but unnecessary difference).

For the interested reader, we explain exactly how to check that \(\Psi\) (defined in the proof of [lem:key]) satisfies the conditions of the Kakutani fixed-point theorem below.

2.0.0.1 Checking the Kakutani conditions.

As a reminder, here is the statement of the theorem, taken from Wikipedia.

To start, we check the easy conditions. Since \(\Delta(C)\) is a simplex, it is clearly non-empty, compact, and convex. We can also see that \(M(D)\) is nonempty for each \(D\in \Delta(C)\), since \(h^+(a;D)\geq h^-(a;D)\) implies that any candidate \(a\) that maximizes \(h^-(a;D)\) is in \(M(D)\). Since \(\Delta(M(D))\) is a non-empty simplex, it is convex (and compact as well).

The only condition we have to check carefully is that \(\Psi\) has a closed graph, meaning that the set of points \(\{(D, Q): Q \in \Psi(D)\}\) is a closed subset of \(\Delta(C)\times \Delta(C)\). In other words, for all sequences of points \(D^{(i)} \to D\) and \(Q^{(i)} \to Q\) such that \(Q^{(i)}\in \Psi(D^{(i)})\) for each \(i\), we have that \(Q \in \Psi(D)\).

First, we argue that \(h^{-}(a;D)\) is lower semicontinuous, and \(h^{+}(a;D)\) is upper semicontinuous. The characteristic property of a lower semicontinuous function \(f\) is that \[\liminf_{x\to x_0} f(x) \geq f(x_0),\] while an upper semicontinuous function \(f\) is one that satisfies \[\limsup_{x\to x_0} f(x) \leq f(x_0).\] (These properties are the reason to define \(h^-\) and \(h^+\) separately.)

It is not hard to check that an indicator function on an open set is lower semicontinuous, and an indicator function on a closed set is upper semicontinuous. (This fact is mentioned on the Wikipedia page for Semicontinuity.)

Since \(\mathop{\mathrm{rank}}_v(a; D) = \sum_{b:a \succ_v b}\Pr_D(b)\) is an affine function of \(D\), the set \(\{D: \mathop{\mathrm{rank}}_v(a;D) > t\}\) is open and \(\{D: \mathop{\mathrm{rank}}_v(a;D) \geq t\}\) is closed. It follows that \(\boldsymbol{1}[\mathop{\mathrm{rank}}_v(a; D) > t]\) and \(\boldsymbol{1}[\mathop{\mathrm{rank}}_v(a; D) \geq t]\) are lower and upper semicontinuous respectively. Since convex combinations of lower/upper semicontinuous functions are also lower/upper semicontinuous, it follows that \(h^{-}(a;D)\) and \(h^{+}(a;D)\) are lower and upper semicontinuous respectively.

Now we are ready to show that \(\Psi\) has a closed graph. Suppose that \(D^{(i)} \to D\) and \(Q^{(i)} \to Q\) with \(Q^{(i)}\in \Psi(D^{(i)})\) for each \(i\). Suppose that \(b\) is in the support of \(Q\), i.e., \(\Pr_Q(b)>0\). Then since \(Q^{(i)} \to Q\), we know that for sufficiently large \(i\), we must have that \(\Pr_{Q^{(i)}}(b)>0\). Since \(Q^{(i)} \in \Delta(M(D^{(i)}))\), it follows that for sufficiently large \(i\), \(b \in M(D^{(i)})\). Unpacking the definition, this means that for all candidates \(a \in C\), \(h^+(b;D^{(i)}) \geq h^-(a;D^{(i)})\). But then using the characteristic properties of lower semicontinuity and upper semicontinuity, we get \[h^+(b;D) \geq \limsup_{i\to\infty} h^+(b;D^{(i)}) \geq \liminf_{i\to\infty} h^-(a;D^{(i)}) \geq h^-(a;D)\] for all candidates \(a\in C\). It follows that \(b\in M(D)\), and more generally that every candidate in the support of \(Q\) is in \(M(D)\). In other words, \(Q \in \Delta(M(D)) = \Psi(D)\) as desired.
Now we are ready to prove the main theorem.

In particular, for \(k = 5\), \(\min_{t\in [0, 1]} (1 - t + t^k) = 1 - \frac{4}{5^{5/4}}\approx 0.465\), which is less than \(\frac{1}{2}\). It follows that every election has a Condorcet winning set of size at most 5.

3 Approximately stable committees↩︎

As a brief addendum, we note that even though [thm:five-specific] gets strong bounds for small values of \(k\), the asymptotics as a function of \(k\) are not optimal. In particular, \(\min_{t\in [0, 1]} (1 - t + t^k) = \Theta(\frac{\log k}{k})\), but it is possible to get \(O(\frac{1}{k})\).

The key additional idea is to construct the committee recursively. Intuitively, if \(k\) is large, rather than sampling the committee in one shot, it can be smarter to start with a few candidates, and then target the rest towards the voters that have low ranks for the current candidates.

[4] and [5] use this recursive approach to give bounds of \(\frac{16}{k}\) and \(\frac{9.821\ldots}{k}\) respectively, and using the new ideas of [1], the bound can be improved to \(\frac{4.910\ldots}{k}\). We sketch the proof below.

In the parlance of [4], the theorem says that \(4.91\)-stable committees always exist in the ranking setting.

3.0.0.1 Acknowledgments.

We thank Thành Nguyen for helpful comments and for pointing us to his upcoming paper [7].

References↩︎