Is there a truly general voting impossibility theorem that applies to real elections?

Question

The purpose of most political elections is to select from the set of candidates a predetermined number $n$ of successful candidates. (Often $n = 1$.) In brief, my question is:

Has it been proved that no voting procedure whatsoever will allow this to be done in a reasonable way?

For comparison, Arrow's theorem states (roughly) that when each voter puts a total order on the set $C$ of candidates, there is no good way to average those orders to produce an overall total order on $C$. This result has of course been enormously influential, spawning many other voting impossibility theorems. However, it does not model the most common real-life situation, where the output we want is a subset of $C$ of cardinality $n$ (the top $n$ candidates, whatever "top" means) rather than a total order on $C$.

Let me emphasize how general my question is. Suppose there are 25 candidates, 3 of whom are to be elected as our representatives. Is there anything whatsoever that voters could be asked to do in the polling booth that could then be processed in some way to select the best 3, in such a way that reasonable conditions hold? By "reasonable conditions" I mean the usual kind that appear in social choice theory, e.g. in Arrow's theorem or the Gibbard- Satterthwaite theorem: non-dictatorship, tactical voting unhelpful, etc.

For instance, perhaps each voter has to mark each candidate out of 10. Or perhaps voters are allowed to make various statements such as "if X is elected but Y is not then Z should be". Or perhaps voters put a partial order on the set of candidates, and whenever they prefer X to Y, they choose a real number specifying how much they prefer X to Y. There are endless possibilities, and my question is whether there's some theorem stating that no matter what voters are required to do, there's no good way to select the top $n$ candidates.

---

Edit In response to comments, let me emphasize further the generality of this question. Many existing impossibility theorems are of the following form: if each voter provides input of some given type, then there is no good way to produce from it an output of another given type. For instance, in Arrow's theorem, both the input and the output type are "total order on the set of candidates". I'm fixing the output type (cardinality-$n$ subset of the set of candidates, for some fixed $n$) and looking for a theorem stating that no matter what input type is used, there is no good system. I don't want to restrict to total orders, or input types that can be derived from total orders. Anything!

Answer 1

This is also a comment, along the lines of usul's comment but a little different. I think it is best not to phrase your question in terms of "no matter what input type is used" but "no matter how apathetic the voters are." To be more clear, the way I think of Arrow's theorem is not that if you design a ballot with a total order then you are in trouble; rather, it's that if voters have such sophisticated preferences that they are able to rank all the candidates in a total order then you are in trouble. What I think you're trying to get at with the partial orders is to ask, what if voters don't actually care about the candidates so much that they are able to rank them in strict order? Intuitively, the more apathetic the voters are, the easier it should be to mollify them.

Thus the most general impossibility theorem would be something like, even if the voters don't care about any of the candidates at all, there's no way to select a satisfactory candidate, and now we can easily see that there trivially can't be a theorem that general. If nobody cares, then just pick anybody, and there can't be any objection.

Somewhat less trivially, if every voter has just one candidate that they like and they are totally indifferent among the others, then picking the candidate with the most votes is going to be paradox-free according to almost any reasonable criteria for a satisfactory voting system.

So I think what you are asking for is, what is the most apathetic voter population that cannot always be appeased? I'm a bit skeptical that there can be a unique "optimal" impossibility theorem in this sense, but maybe there is.

---

Edit: In light of some of the discussion, I'm going to try to articulate some tacit assumptions that I think people are making that I think are confusing the issue.

I suspect that many people, including Tom I think, are tacitly imagining voters as actually having opinions about all sorts of things. Perhaps some voter prefers that if three out of candidates $C_1, \ldots, C_n$ be picked, then it should be $C_1, C_2, C_3$, unless it so happens that my neighbor also likes that choice, in which case I would prefer $C_4,C_5,C_6$ just to see my neighbor suffer—but if my wife tells me that she hates $C_6$ then I'd prefer $C_4,C_5,C_7$ (at least, if she tells me this six or more days before my dad tells me that he hates $C_7$, and I don't think my dad is lying, and $C_7$ placed no worse than second place in the last two elections), etc. Every conceivable opinion is there in the voters' heads. Designing a voting system amounts to some method of sampling from that vast sea of information, and the designer wants to make sure that the system doesn't suffer from paradoxes.

If one is trying to generalize Arrow's theorem (and the like) in the direction that Tom seems to want to do, then I think that this way of thinking about the voters is unhelpful. The reason paradoxes arise is precisely because when the voter preferences exceed some threshold of complexity, there is no consistent way to define "the will of the people". As long as people secretly have those complex, paradoxical preferences, the result of any voting system is going to fail to express the will of the people, simply because that will does not exist. It doesn't matter whether the voting system samples more or less information or in what way; the most it can do is to make it obvious that there is no will of the people, but even if you sample information in a way that fails to lay bare this ugly secret, you have not successfully expressed the will of the people. You've just buried your head in the sand.

The way to approach the issue, in my opinion, is to drop the assumption that voters have opinions about every conceivable thing, even those that don't appear on the ballot. Instead, assume that the ballots capture everything that there is to know about a voter's preferences. If a preference does not appear on a ballot, then it doesn't exist. This is not really a limitation, because we are free to design any kind of ballot we want. The ballot could be a long questionnaire that solicits opinions about your neighbors and the last election and whether you're in a bad mood today or whatever. The only rule is that if a preference is not on the ballot then it doesn't exist. This simple convention short-circuits all the complications about whether a voting system is burying its head in the sand because it asks for partial information only, when if it asked for full information then a difficulty would be revealed. There is no difference now between what voters prefer and what the ballot indicates. This makes the problem much simpler and clearer.

Now perhaps my original suggestion will be clearer. To generalize Arrow's theorem, we want to look at ballots that do not express more preferences than a total order. It could express strictly fewer preferences (a partial order) or it could express a set of preferences that is different, perhaps seemingly more complicated, but not strictly more than what is contained in a total order. There is plenty of room for impossibility theorems here; that requires detailed research. But the point is that it is helpful to think in terms of different states of the voters' actual preferences, rather than in terms of different ways of sampling some infinite but unknown sets of preferences.

Answer 2

This is an interesting question, but in fact it mixes together several different issues, each of which is the subject of its own research program within the social choice literature.

One question is: Can we design a voting rule which prevents or somehow minimizes strategic voting? The Gibbard-Satterthwaite Theorem is the original "impossibility theorem" in this area, but this has engendered a huge amount of research in what is now called implementation theory and mechanism design. The literature on these topics has a lot of "impossibility theorems", but it also has some positive results. Two important takeaways from this literature:

• Any analysis of "strategic voting" necessarily involves game theory, and thus, must invoke some equilibrium concept to describe the "optimal strategic behaviour" of the agents. For example, the Gibbard-Satterthwaite theorem involves "dominant strategy equilibrium", which is an extremely demanding notion of "strategic behaviour". So in some sense, it is not surprising that we get an impossibility result. A weaker solution concept is Nash equilibrium. In a game which unfolds over time, this can be refined to subgame perfect Nash equilibrium. In a game where the players have incomplete information about one another, it can be refined to a Bayesian Nash equilibrium. Each of these concepts leads to different results about strategic voting and its prevention.

• Many impossibility results are driven by allowing too much "diversity" in the voters' preferences. If we impose some constraints on the sort of preferences the voters can have, then we can get positive results. In the literature, these constraints are called "domain restrictions". For example, a classic result says that the simple plurality voting rule has all kinds of good properties (including strategy-proofness) if the alternatives can be arranged along a line (e.g. from "left" to "right", politically speaking), and each voter has an "ideal point" on this line. (This is called the domain of "single-peaked preferences".) For another example, Will Sawin already mentioned the Vickrey-Groves-Clarke mechanism; this mechanism depends on the assumption that voters have "quasilinear" utility functions (i.e. each voter's utility has the form $w + u(a)$, where $w$ is her wealth level, and $u(a)$ is the cardinal utility she assigns to alternative $a$.)

However, much of social choice theory has nothing to do with strategic voting. For example, Arrow's Impossibility Theorem is not about strategic voting. It seemed to me that Tom's original question also was not confined to strategic voting. There is now a huge literature in social choice theory considering the purely normative properties of social choice rules, even if we neglect strategic voting issues. This literature begins with "axioms", each of which encodes some notion of "fairness", "consistency", "rationality", or some other normatively desirable property of a social choice rule. (Arrow's original axioms are the prototypical example.) The results in this literature are generally of two kinds:

• Axiomatic characterizations of the form, "Social choice rule $X$ is the only social choice rule which satisfies axioms $A_1, A_2,\ldots, A_N$."
• Impossibility theorems of the form, "There is no social choice rule which satisfies axioms $A_1, A_2,\ldots, A_{N+1}$."

Note that you can typically get an impossibility result from an axiomatic characterization, just by adding one more axiom. So axiomatic characterizations live at the "boundary" of impossibility.

Different axioms lead to different social choice rules (or impossibilities), and it is really a philosophical question which list of axioms is the most normatively compelling. So in this sense, there is no unique answer to Tom's question.

However, there is another way to interpret Tom's question. As I understood it, he was also asking about voting rules which use other sorts of data aside from ordinal preferences. Earlier answers have already mentioned approval voting and range voting. Another option is majority judgement, which takes, as input, rankings of alternatives, rather than preference orders, and which assigns to each alternative the median ranking.

We could also suppose that, instead of a preference order, each voter's attitudes are described by a utility function. We could then try to aggregate these utility functions into some "collective" utility function. These are called social welfare functions, and there is a whole literature concerning their axiomatic characterizations. Harsanyi's Social Aggregation Theorem (already mentioned by Qiaochu) is an early example. However, as Qiaochu already mentioned, a big problem in this field is how to make interpersonal comparisons of utility functions in a convincing way.

Generalizing the question still further, there is now a large subfield in social choice theory called judgement aggregation, which considers the question of how to aggregate the voters' beliefs on a set of logically interconnected propositions. (Here, "beliefs" are represented as truth values.) Arrovian preference aggregation can be considered a special case of judgement aggregation, because any preference order can be represented as a list of beliefs of the form, "I think $a$ is better than $b$". The literature on judgement aggregation contains some very general impossibility theorems, which yield Arrow's Impossibility Theorem as a corollary. So perhaps this is the answer Tom is looking for.

However, like all impossibility theorems, the results in judgement aggregation rely on certain axioms; if you don't feel that these axioms are normatively compelling, then you may regard the resulting impossibility theorems as uninteresting. For example, pretty much every impossibility theorem in judgement aggregation involves some version of the Independence axiom, which says that the voters' beliefs on each logical proposition should be aggregated independently of their beliefs on every other logical proposition. (This is a generalization of Arrow's famous Independence of Irrelevant Alternatives axiom.) But one might object that the Independence axiom obviously demands too much; it is not clear why we should impose it. If you are willing discard the Independence axiom, then there are many satisfactory judgement aggregation rules in the literature. This is currently a very active research area within social choice theory.

Answer 3

Approval voting may well be the reasonable solution you are looking for. In approval voting, the voter either approves or disapproves every candidate on the ballot. The winner is the candidate that gets the most approvals. This method is not subject to Arrow's theorem because all approved candidates (and disapproved candidates) on a particular ballot are equally ranked, a condition not covered by Arrow's theorem.

Answer 4

This is a complete rewrite of my original answer, combined with my comments on the original question and various other answers.

Suppose we have a finite set $C$ of candidates, and a finite set $E$ of electors (with $|C|>1$ and $|E|>2$, to avoid some degenerate cases). I will assume that we are just modelling what happens in some kind of secret ballot after campaigning has finished, so each elector independently fills in some kind of form. Let $F(C)$ be the set of possible ways to fill in the form. If all candidates are treated equally, then $F(C)$ should be functorial for bijections of $C$. The collection of voter choices is a point $f\in\text{Map}(E,F(C))$.

Some obvious candidates for $F(C)$ are

• $F(C)=C\amalg\{0\}$: the traditional system in which each voter selects a single candidate, or does not vote (represented by $0$).
• $F(C)=P(C)$ (the set of subsets of $C$): the "approval voting" system where each voter indicates which candidates they find acceptable
• $F(C)=\text{Ord}(C)$ (the set of total orders on $C$): the system assumed in the Arrow and Gibbard-Satterthwaite theorems, where each voter has and records a total preference order.
• $F(C)=\text{Pre}(C)$ (the set of preorders on $C$).

It is not hard to come up with other possibilities.

Note that if $|C|=n$ and $N=\{0,\dotsc,n-1\}$ then $\text{Ord}(C)$ can be identified with the set of bijections $N\to C$. It follows that natural maps $\text{Ord}\to F$ biject with elements of $F(N)$. In particular, there are plenty of such maps, but we see from the above examples that often none of them will be injective. It seems reasonable to assume that there is a given nonempty set $R_0(N)\subseteq F(N)$, consisting of the possible form responses that are not obviously incompatible with the preferences $0<1<\dotsb<N-1$. Given this, we can define by functoriality a subset $R(C)\subseteq\text{Ord}(C)\times F(C)$, consisting of pairs $(o,u)$ where the form response $u$ is not obviously incompatible with the ordering $o$.

Now put $e=|E|$ and $$ S_e(F(C)) = \{m\colon F(C)\to \mathbb{N} : \sum_{u\in F(C)} m(u) = e\}. $$ Given $f\in\text{Map}(E,F(C))$ we can put $\mu(f)(u)=|f^{-1}\{u\}|$ to get a point $\mu(f)\in S_e(F(C))$, which is a complete $\text{Aut}(E)$-invariant for $f$. Any fair voting system should be $\text{Aut}(E)$-invariant and so should factor through $\mu$.

I will assume for the moment that we now want to elect a single candidate, so $n=1$ in Tom's notation.

Ideally we might hope for a map $\sigma\colon S_e(F(C))\to C$ such that $\sigma(\mu(f))$ is the successful candidate. Fairness between candidates dictates that this should be equivariant for $\text{Aut}(C)$. However, this is clearly impossible, because there will usually be many points in $S_e(F(C))$ that are fixed by $\text{Aut}(C)$, but there are no such points in $C$. Thus, we need some way to think about breaking ties, even if they are likely to be rare.

The approach of Duggan and Schwartz (http://dx.doi.org/10.1007%2FPL00007177; http://en.wikipedia.org/wiki/Duggan%E2%80%93Schwartz_theorem) is to consider voting systems $\sigma\colon S_e(\text{Ord}(C))\to P'C$, where $P'C$ is the set of nonempty subsets of $C$. The idea is that $\sigma(f)$ will usually be a singleton, but if not, one of the candidates in $\sigma(f)$ will be chosen by some kind of lottery. They show that under minimal assumptions, any such system is manipulable, no matter what the details of the lottery might be. I think that this completely resolves the question for the case $F=\text{Ord}$, at least if we accept the traditional position that manipulability is the key thing to avoid.

So what if $F\neq\text{Ord}$? I have tried to think of other ways of handling ties, but it seems to me that the Duggan-Schwartz framework is optimal. Thus, we should think about $\text{Aut}(C)$-equivariant voting systems $\sigma\colon S_e(F(C))\to P'C$. We then need to define what it would mean for such a system to be manipulable. It seems inescapable that such a definition must involve the notion that some voters prefer some outcomes to some other outcomes. Thus, we must assume that each voter has a preference preorder. Some voters may be completely apathetic, so their preorders will rank all candidates equally, but some other voters may have a total preference order. Any satisfactory system must be able to handle the special case where every voter's preorder is total, so if we can prove an impossibility theorem in that context, then we are done. Now choose a point $r\in R_0(N)$, giving a map $\rho\colon\text{Ord}(C)\to F(C)$. It might happen that all voters choose to fill in their ballot papers by applying $\rho$ to their total preference order. If we can prove an impossibility theorem in this special case, then again we are done. We now have a map $\sigma\circ\rho_*\colon S_e(\text{Ord}(C))\to P'(C)$. The Duggan-Schwartz theorem gives a list of four properties that this map cannot satisfy simultaneously. Because we have assumed stronger symmetry conditions than Duggan and Schwartz, the Citizen Sovereignty and non-Dictatorship conditions are automatic. The Residual Resoluteness condition says that if all voters have the same preference order, except that one voter might swap the top two candidates, then the majority first choice should be elected. In our context this is a condition on $R_0$ and $\sigma$, and it seems like a condition that we should certainly assume. The theorem then says that $\sigma\circ\rho_*$ represents a voting system that is manipulable according to the Duggan-Schwartz definition. This holds for all $r\in R_0(N)$, and that seems like a reasonable sufficient condition to say that $\sigma$ itself is manipulable.

If we want to elect $n$ candidates with $n>1$, we should probably consider a framework similar to that of Duggan and Schwartz, except that $\sigma$ should be a map from $\text{Map}(E,\text{Ord}(C))$ to $P_{\geq n}(C)$, and precisely $n$ candidates should be chosen by lottery if $\sigma$ produces a set of size strictly larger than $n$. It looks to me as though nothing much should change, but I have not tried to work out the details.

Answer 5

For a sufficiently loose definition of "voting" - one that includes spending money - there is a solution, coming from the field of mechanism design.

The voting system works like this: Each voter must assign to each of the candidates a monetary value. The individual values are not meaningful, but the differences are - they represent the difference in the individual's preferences between the two candidates, measured in dollars.

Whichever candidate gets the most total dollar value wins.

Then the voting system extracts a democracy fee from each voter on the winning side whose vote swayed the total, i.e., if their vote was not counted, a different candidate would have won. The fee is equal to the total dollar value other voters placed on the different candidate, minus the total value placed on the winning candidate. (This is always a number greater than zero and less than the difference in value that voter placed between the two candidates.)

It is pretty easy to check that no voter is ever incentivized to lie about their true monetary preferences, assuming their utility function depends on money in a way independent of the candidate, so that the notion of monetary preferences makes sense. So this voting system is completely perfect, except that:

I. Voter representation is proportional to money, so the rich, or just people who don't care very much about money, are overrepresented.

II. The democracy fees must be spent on something that doesn't affect any voter's utility, which presumably means its wasted. Depending on the number of close elections, this could be a considerable cost to the system.

This is a special case of the Vickrey-Clarke-Groves mechanism from the field of mechanism design in game theory. It can handle elections, auctions, and all forms of group decision-making, with the same caveats, except that the central mechanism can also have to pay the participants and sometimes ends up losing money, which makes it unworkable in practice.

Answer 6

Extended comment. The primary challenge in the question is how one models the voters, which relates directly to what types of inputs they can provide and how one evaluates the solution. Your question seems to presume some nice answer to these questions, but in fact I think these are very thorny.

To begin, suppose that voters have a well-defined preference ordering on outcomes, but nothing further about their utilities or preferences is assumed. Then it seems tricky to say what the "best" outcome of an election should be in general, and the axiomatic approach was developed to deal with this.

OK, so now we want to allow the voters a more expressive system in hopes of avoiding Arrow's or Gibbard-Satterthwaite; but suppose we keep the above modeling assumption on the voters. Then how would one expect voters to behave under, for instance, range voting? (Each voter gives each candidate a score between, say, 1 and 100.) There doesn't seem to be a correct answer as to how a voter with a given preference relation ought to vote in a range voting system.

So to allow more expressive voting systems, it seems that we should allow more expressive voter models. Furthermore, our notion of "good" outcomes should make sense for these models, just as the axiomatic approach corresponded to the preference relation model.

For instance, perhaps we assume that each voter has a utility associated with each candidate. For simplicity, consider direct-revelation voting rules (just report your utilities). This model runs into immediate problems: Shouldn't "best" be "maximizes sum of utilities"? In this case, we cannot hope to avoid manipulation (a voter wishes to exaggerate the worth of her favorite candidate unboundedly). Perhaps instead best should be "maximizes product of utilities", but again avoiding manipulation seems impossible (a voter would set utility to zero for all but her favorite candidate).

One can attempt to fix these issues by, for instance, re-scaling voter utilities so that they all lie in [0,1] with the favorite candidate having a utility of 1 and least favorite candidate having a utility of 0. Then we might evaluate a rule by how well it maximizes the sum of utilities or so on. However, this seems to make a mockery of the original utility model -- perhaps we really do have one voter with much higher utility for one candidate than everyone else, so how can we say that any voting rule that ignores this fact is "good"? Perhaps the right notion is fairness (in some sense) rather than total utility, but again, this needs to be defined mathematically.

So, I'm not sure if there is research that tackles these issues, but I know that we have to solve the question of how to model voters and evaluate outcomes in order to proceed in addressing your question, and this is nontrivial.

Answer 7

Here is a no-goish theorem regarding the more general question of how to aggregate the preferences of a collection of agents. Assume the agents are von Neumann-Morgenstern rational, so that their preferences are represented by (equivalence classes of) utility functions $u_1, u_2, \dots u_n$. These utility functions take as input a possible state of the world, and so can express arbitrarily sophisticated preferences subject to the von Neumann-Morgenstern axioms. The question is how to aggregate the preferences of these agents (e.g. for the purposes of voting) into a single utility function $U$ in a "fair" way, whatever that means.

A family of ways to do this is to pick normalizations of the utility functions and add them; let me assume that the $u_i$ have already been normalized in some arbitrary way and represent the corresponding aggregation as

$$U = \sum_{i=1}^n c_i u_i, c_i > 0.$$

This is unsatisfying because it doesn't give us a prescription for picking the weights $c_i$. The fundamental issue is that utility functions are not directly comparable with each other, since they are only defined up to positive affine transformations $u \mapsto au + b, a > 0$; that is, the claim that $u_1$ values state $A$ over state $B$ more than $u_2$ values state $B$ over state $A$ is a priori meaningless.

We might decide to normalize the utility functions so that they take values in $[0, 1]$, and moreover so that each agent's least preferred outcome has utility $0$ and each agent's most preferred outcome has utility $1$. But one rather underhanded way to undermine this aggregation procedure is to create many other agents that share your utility function, which effectively increases your relative weight in the aggregate utility function. And on the other hand there are some agents that really shouldn't have the same normalized weight as other agents, e.g. I don't want ants to have equal weight relative to humans.

Anyway, as unsatisfying as this procedure is, Harsanyi's utilitarian theorem asserts that it is the only aggregation procedure satisfying a short list of reasonable axioms. This isn't directly a voting problem in the sense that it's assumed that during aggregation you have access to every agent's utility function, so there's no room in this procedure for deliberately misreporting utilities, for example. But it is an example of Timothy Chow's point that you run into trouble once you allow voters to have preferences that are too sophisticated.

Answer 8

The preference of controversial impossibility theorems over boring characterisation and classification theorems is not necessarily helpful.

A simple randomised procedure compatible with Arrow's theorem would be to choose an individual randomly, and declare his preference order to be the single overall preference order. Such a procedure could still be unfair, if certain individuals would be chosen with a higher probability than others.

Note however that Arrow's theorem is not sufficient for classifying the possible fair randomised procedures (or at least it is not clear to me how that classification could be derived as a corollary), as highlighted by the randomised quick sort procedure outlined in this (my) question. (Yes, this answer is motivated by my own question, and especially the opening line and the following last paragraph are based on opinions instead of facts.)

As these two examples of (fair) randomised procedures demonstrate, there cannot be a truly general voting impossibility theorem. Instead of an impossibility theorem, there are various characterisation and classification theorems (like Harsanyi's utilitarian theorem cited in Qiaochu Yuan's answer). But because of the focus on impossibility theorems, not all of them have been worked out yet.