Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question
4  
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. –  Neil Strickland Jul 15 at 12:03
3  
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. –  Neil Strickland Jul 15 at 12:05
1  
@Neil: but what the voters are asked to do might depend on $n$. –  Tom Leinster Jul 15 at 12:06
4  
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. –  Douglas Zare Jul 15 at 12:12
2  
@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? –  Tom Leinster Jul 15 at 12:14

6 Answers 6

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.

share|improve this answer
4  
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.) –  Tom Leinster Jul 16 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. –  Timothy Chow Jul 16 at 15:01
    
Aren't there counterexamples to Arrow's theorem when we have an 'infinite ballot', though?: en.wikipedia.org/wiki/… –  Sam Hopkins Jul 16 at 16:00
1  
@SamHopkins: My understanding is that the counterexamples you mention involve an infinite population, not an infinite ballot. –  Timothy Chow Jul 17 at 1:02
    
Tim: yes, the empty ballot is certainly included among the "anything" that the voters could do. –  Tom Leinster Jul 17 at 11:51

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.

share|improve this answer
1  
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. –  Tom Leinster Jul 15 at 12:55
    
@TomLeinster: under (iii), I do not know what you mean. Can you spell it out as an actual mathematical statement? –  Neil Strickland Jul 15 at 13:39
1  
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). –  Tom Leinster Jul 15 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.) –  Tom Leinster Jul 21 at 11:14

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.

share|improve this answer
    
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. –  Gerry Myerson Jul 16 at 6:13
    
Note that this is compatible with Timothy Chow's answer: approval voting avoids strategic voting by reducing the information content of each voter's input (relative to the situation envisaged by Arrow), whereas the OP seemed to want to increase the information content. It seems clear that some voters will be unhappy that they have to group awesome candidates together with barely acceptable ones, and one could probably produce formal criteria to reflect that kind of unhappiness, but I do not know whether that has been done. –  Neil Strickland Jul 16 at 9:22
2  
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$. –  Tom Leinster Jul 16 at 12:45
1  
@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. –  Waldemar Jul 16 at 15:06
1  
@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. –  Neil Strickland Jul 16 at 15:53

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.

share|improve this answer

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.

share|improve this answer
    
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). –  Steven Landsburg Jul 21 at 2:14

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.