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

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!

• Also, any "good system" must be able to handle the case where each elector does in fact have a total preference order (with equally spaced preferences, say) and answers whatever question they are asked in accordance with that. Commented Jul 15, 2014 at 12:03
• Also, one possible "reasonable condition" is that if we ask the system to produce an optimal set $C_n$ with $|C_n|=n$, and then repeat for $n+1$, then we should have $C_n\subset C_{n+1}$. With that condition, we get a total order out at the end. Commented Jul 15, 2014 at 12:05
• @Neil: but what the voters are asked to do might depend on $n$. Commented Jul 15, 2014 at 12:06
• Yes, G-S shows that there is no good voting system when you allow voters to state partial orders or preorders instead of total orders. You are adding possibilities to a set over which there is no good voting system, and this can't create a good voting system. The incoherent social choices guaranteed by G-S still exist in the enlarged set. Commented Jul 15, 2014 at 12:12
• @Neil (in response to your "Also, any..." comment): you're still not thinking generally enough! A total order on the set of candidates doesn't answer every conceivable question. E.g. maybe I prefer the yellow party to the brown party, so I'd put the yellow candidates at the top of any total order I was asked to construct; on the other hand, I think it's unhealthy for the committee to be all-yellow, so I want to express the preference that at least one elected member is brown. You can't encode that in a total order, can you? Commented Jul 15, 2014 at 12:14

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.

• That's an interesting set of thoughts, Tim, and I've learned from it. However, you're changing my question into a different (also interesting) question. I asked what I wanted to ask! Conceivably, there's something voters could do that bears no resemblance to any kind of order (partial or total) but would result in a fair way of picking a cardinality-$n$ subset of the candidates. I'm looking for theorems that say this is impossible, avoiding the assumption that imposing a total order is the most sophisticated thing a voter might do. (E.g. see my brown/yellow comment above.) Commented Jul 16, 2014 at 1:14
• Tom, I have not actually changed your question, just the way of thinking about your question. Nothing I said relies on total orders or partial orders. For any thing that you want the voters to do, just think of it as capturing every desire that that voter has and nothing more. Let me turn your comment back on yourself and suggest that you're not thinking generally enough. Is the empty ballot, where every voter submits nothing at all, included among the "anything" that the voters could do? It should be, if you're truly thinking generally. Commented Jul 16, 2014 at 15:01
• Aren't there counterexamples to Arrow's theorem when we have an 'infinite ballot', though?: en.wikipedia.org/wiki/… Commented Jul 16, 2014 at 16:00
• @SamHopkins: My understanding is that the counterexamples you mention involve an infinite population, not an infinite ballot. Commented Jul 17, 2014 at 1:02
• Tim: yes, the empty ballot is certainly included among the "anything" that the voters could do. Commented Jul 17, 2014 at 11:51

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.

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.

• en.wikipedia.org/wiki/Approval_voting has a table of system desiderata and the extent to which approval voting meets them under various assumptions about voter preferences, also a discussion of vulnerabilities to strategic voting. Commented Jul 16, 2014 at 6:13
• I'm glad to learn the phrase "approval voting"; I'd mentioned marking out of 10 in my question, and this is marking out of 1. But again, this isn't an answer to my question. (I can only apologize that it seems to have been unclear, but I don't see how to make it any clearer.) First, I wasn't looking for any "solution": I was looking for a general impossibility theorem. Second, you're talking about selecting a single winner, and although that's an interesting special case, I was asking about electing a cardinality-$n$ subset of the set of candidates, where perhaps $n > 1$. Commented Jul 16, 2014 at 12:45
• @Tom Leinster I’m not sure if the approval voting (or rather its generalized variant – range voting) does not answer your question. First, you were not looking for a solution but for an impossibility theorem. It seems to me that an existence of a solution can be interpreted as the impossibility of the impossibility theorem. Second, if you repeat a procedure $n$ times then you can get a cardinality-$n$ subset and not just a single winner. Commented Jul 16, 2014 at 15:06
• @TimothyChow: "After all, if the preference is not expressed, why postulate that it exists at all?" This whole subject area starts with the issue that voters have strong preferences beyond what they can express by ticking a single candidate, and this is perceived to be a serious problem in practice. If you assume that away, then there is not much left to talk about. Certainly, you cannot formulate anything like the Gibbard-Satterthwaite axioms without assuming that voters have a preference preorder on the possible outcomes. Commented Jul 16, 2014 at 15:53
• @Tom Leinster One solution to this problem is to apply a modified version of the range voting system. Candidates are not individuals but cardinality-$n$ subsets. One subset is a winner. We get an unordered $n$-element set. Commented Jul 17, 2014 at 6:59

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.

• Thanks for that, Neil. Three thoughts: (i) I agree with you that what the voters are asked to do should probably be encoded as a species. (ii) Requiring symmetry in $C$ can lead to tie-breaking trouble (hence impossibility theorems of a rather trivial kind). I don't know what to say about that. (iii) As I hope I've now managed to communicate, your last paragraph does reduce the generality of the question I was asking. Commented Jul 15, 2014 at 12:55
• @TomLeinster: under (iii), I do not know what you mean. Can you spell it out as an actual mathematical statement? Commented Jul 15, 2014 at 13:39
• On reflection, I think I now understand where you were planning to go with the observations in your last (now second-to-last) paragraph. I'd misunderstood your intention before. So please ignore my point (iii). Commented Jul 15, 2014 at 14:43
• Thanks, Neil, that's really helpful. (And anyone coming late to this thread: please ignore earlier references to specific paragraphs of Neil's answer, which has now been completely rewritten.) Commented Jul 21, 2014 at 11:14

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.

• You can address both problems (I) and (II) if two separate polities --- say Texas and California --- both adopt this system, with Texas voters making their payments to Californians and California voters making their payments to Texans. Then none of the democracy fees are wasted (which addresses problem II) and the people who put less monetary value on getting their preferred election outcomes will receive, on average, cash payments that they value more highly than they value those outcomes (at least assuming that the average payments are the same in both polities). Commented Jul 21, 2014 at 2:14
• Hi Steven. Your proposal solves problem (II) (at least, as long as there is no trade or other economic interactions between Texas and California, which is sort of implausible). But I don't see how it solves problem (I). The problem is that rich voters have much more voting power than poor voters, so they will control the outcome. So the rule will be a plutocracy rather than a democracy. You claim "the people who put less monetary value on getting their preferred election outcomes will receive, on average, cash payments that they value more highly than they value those outcomes." .... Commented Jul 10, 2016 at 6:52
• ...but this analysis is not correct. In practice, the actual amount of money extracted through the "democracy fee" (technically called the "Clarke tax") is generally rather small (because there are usually only a few pivotal voters, or none at all). When spread out over e.g. the population of California, the amount of money per voter would be infinitesimal. If I am a low-income voter, then the 0.001 cents per year which I would receive in democracy fee transfer payments from Texas will hardly compensate me for the fact that I have been totally disenfranchised by the social choice rule. Commented Jul 10, 2016 at 6:55

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.

• The version of utilitarianism where you rescale each person's utility to range over [0,1] is called relative utilitarianism, and is the subject of several academic papers. I agree with your concern that there are some social choice problems where one person just has much more intense preferences than another. So we should not apply the [0,1] utility rescaling to a particular problem. For the [0,1] rescaling to be normatively appealing, 0 must stand for the "worst possible life" and 1 for the "best possible life", for each person. Commented Jul 10, 2016 at 6:28
• Also, you are correct that, in "range voting" (which is basically the voting rule analog of relative utilitarianism), each voter's optimal strategy is to assign a value of "0" or "1" to almost all of the alternatives, in almost all situations. The precise statement is a theorem in the paper Preference Intensity Representation: Strategic Overstating in Large Elections by Matias Núñez and Jean-François Laslier. Commented Jul 10, 2016 at 6:46

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.

• Hi Qiaochu. I'm not really sure why you say Harsanyi's Social Aggregation Theorem is a "no-go" theorem. That suggests that it is an "impossibility theorem" (i.e. "There is no social choice rule satisfying $X$"). Instead, I think of it as an axiomatic characterization theorem ("There is exactly one social choice rule satisfying $X$"). Of course, you might not like the social choice rule in question, but that doesn't make it a "no go" result. However, you are completely correct that interpersonal utility comparisons are a still-unsolved problem. Commented Jul 10, 2016 at 6:36
• As for manipulating the rule by creating "clones" of yourself: basically any social choice rule is vulnerable to this sort of manipulation. Normally we assume that it is impossible for agents to "clone" themselves. As for humans vs. ants: this raises a deep philosophical question: which entities should have "moral weight" in your utilitarian calculus, and how much weight? Most people think only humans should have "moral weight". Some philosophers (like Peter Singer) think animals should also have moral weight, but that's a minority view. Commented Jul 10, 2016 at 6:41

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.