For those with an interest in quantum information, the 10th Workshop on Quantum Information Processing (QIP) will be held in Brisbane January 30 – February 3 next year. This has been a terrific workshop in the past (I certainly try to attend every year), and we’re optimistic this one will be a great workshop, too.
All the details are at the workshop website.
What’s the best way for a group of people to make collective decisions? Democracy may be, as Churchill said, the worst system that’s better than anything else, but in practice there’s a lot of variation possible in democractic voting systems. How should we set up voting systems that result in effective collective decisions?
Designing a good voting system seems like a simple task, but it’s surprisingly complicated. A famous result known as Arrow’s theorem, proved by the economist Kenneth Arrow in 1950, vividly demonstrates just how difficult it is. Arrow picked out three properties that (arguably) you would like any good voting system to have – and then mathematically proved that no voting system with all three properties can possibly exist! What is especially remarkable about Arrow’s achievement is that there is no obvious a priori reason to suppose that these three requirements are incompatible. Arrow was a joint recipient of the 1972 Nobel Memorial Prize for economics, in part because of this work.
These notes explain what Arrow’s theorem says, why it’s true (i.e., I give a proof), and discuss briefly what it means for collective cognition. I’ve tried to keep the notes easy to read, favouring a relaxed and discursive discussion over the terse presentation favoured in most mathematical works. I have also tried to assume minimal mathematical background, no more than some facility with basic mathematical notation and mathematical argument. The main drawback of this approach is that the notes have become rather lengthy, clocking in at nearly [tex]3000[/tex] words. Hopefully, however, they’ll be a rewarding read.
My notes are based on a very nice paper by John Geanakoplos (Cowles Foundation discussion paper No.1123RRRR, available at http://cowles.econ.yale.edu, and reprinted in Economic Theory (2005), 26: 211-215), which gives three proofs of Arrow’s theorem. The proof I give is Geanakoplos’ first (and simplest) proof. Note that there are other (related) results in the literature which go by the name Arrow’s theorem. Understanding the version presented here should enable you to understand the variants with a minimum of fuss. Arrow’s original paper appeared as “A Difficulty in the Concept of Social Welfare” in The Journal of Political Economy, Volume 58, page 328 (1950).
To explain what Arrow’s theorem says, we need to define more precisely what we mean by a voting system. We imagine a population of [tex]n[/tex] “voters”, to whom we assign convenient labels , like [tex]1, \ldots, n[/tex]. This population might be, for example, all the mentally competent people over the age of [tex]18[/tex] in some country (e.g., Australia).
These voters are going to vote amongst [tex]m[/tex] alternative options, which we’ll label with capital letters, [tex]A, B, C, \ldots, Z[/tex], to keep distinct from the voters. These voting options might be the political parties running for control of the Federal Government, for example.
What each voter does is produce an ordered ranking of the options, with ties allowed. For example, voter number [tex]3[/tex] might rank [tex]B[/tex] as number [tex]1[/tex], [tex]A[/tex] and [tex]C[/tex] as a tie for number [tex]2[/tex], [tex]D[/tex] as number [tex]3[/tex], and so on.
(You might wonder whether [tex]D[/tex] shouldn’t really be ranked number [tex]4[/tex], in view of the tie between [tex]B[/tex] and [tex]C[/tex] for the ranking of [tex]2[/tex]. Below we’ll make an assumption about the voting system that means that only the relative ranking matters, not the exact value of the number assigned, and so we’re justified in ignoring this issue.)
A helpful shorthand is to write [tex]S >_v T[/tex] to indicate that voter [tex]v[/tex] ranked [tex]S[/tex] strictly ahead of [tex]T[/tex]. For example, maybe voter [tex]v[/tex] ranked [tex]S[/tex] as [tex]2[/tex] and [tex]T[/tex] as [tex]4[/tex]. It’s worth keeping in mind that this notation for ordering is the reverse of the conventional numerical order – politicians usually campaign to be “number [tex]1[/tex]” rather than “number [tex]10[/tex]”! Similarly, we’ll write [tex]S \geq_v T[/tex] to indicate that voter [tex]v[/tex] ranked [tex]S[/tex] at least as highly as [tex]T[/tex]; this allows that maybe [tex]S[/tex] and [tex]T[/tex] had the same rank. By the way, we’ve been using [tex]S[/tex] and [tex]T[/tex] here simply to indicate generic voting options; we’ll do this throughout, occasionally using [tex]U[/tex] as well.
As an example, imagine there are [tex]5[/tex] voters choosing among [tex]3[/tex] alternatives, [tex]A, B, C[/tex]. The overall voting profile might look something like this:
A voting system is a function which takes the profile as input, and produces a single social ranking of the options as its output. For example, we might add up the numerical value of the votes associated to each voting option, and then order the options accordingly. So, for example, option [tex]A[/tex] above has a total vote [tex]1+3+2+1+3=10[/tex], option [tex]B[/tex] a total [tex]1+1+1+1+2=6[/tex] and option [tex]C[/tex] a total [tex]2+2+1+1+1=7[/tex]. As a result, in this voting system the social ranking has [tex]A[/tex] as [tex]3[/tex], [tex]B[/tex] as [tex]1[/tex], and [tex]C[/tex] as [tex]2[/tex].
Once a voting system has been fixed, we write [tex]S > T[/tex] to indicate that [tex]S[/tex] has a higher social rank than [tex]T[/tex]. Similarly, we write [tex]S \geq T[/tex] to indicate that [tex]S[/tex]’s social ranking is at least as high as [tex]T[/tex]’s.
What properties should a good voting system have?
Obviously, this is a potentially controversial question! Arrow’s theorem is based on several reasonable properties that, arguably, we should expect to be satisfied in any good voting system.
The first property is that the voting system should respect unaninmity, in the sense that if [tex]S >_v T[/tex] for all voters, then we should have [tex]S > T[/tex]. Restating this verbally instead of symbolically, if every voter prefers [tex]S[/tex] to [tex]T[/tex], then the social ranking should place [tex]S[/tex] ahead of [tex]T[/tex]. This is pretty obviously a highly desirable property for any voting system to have – imagine if the electoral commission announced that candidate [tex]A[/tex] had won, despite the fact that every single voter ranked [tex]B[/tex] ahead of [tex]A[/tex]!
The second property is that the voting system should respect the independence of irrelevant alternatives, meaning that the relative social ranking of [tex]S[/tex] and [tex]T[/tex] (higher, lower, or the same) depends only on the relative ranking of [tex]S[/tex] and [tex]T[/tex] by individual voters, and isn’t influenced by the position of other options (e.g., [tex]U[/tex]).
It’s rather less obvious that any good voting system will respect the independence of irrelevant alternatives. For example, the simple voting system I described above (where we summed the votes) turns out not to have this property, yet it’s not so obviously a bad voting system.
However, for the purposes of this discussion we’re going to assume that this property of respecting the independece of irrelevant alternatives is regarded as highly desirable. Can we design a voting system which respects both unanimity and the independence of irrelevant alternatives?
It turns out that if there are just two voting options, [tex]A[/tex] and [tex]B[/tex], then it’s possible to design a voting system with this property. We could, for example, just sum up the the respective votes of the two voting options, and declare the winner to be whichever option has the lower total.
What happens if there are three voting options, [tex]A, B[/tex] and [tex]C[/tex]? What Arrow’s theorem shows in this case is that in any voting system which respects unanimity and the independence of irrelevant alternatives there must automatically be a voter, [tex]d[/tex], who can act as a dictator for the voting system, in the sense that if [tex]S >_d T[/tex], then [tex]S > T[/tex], no matter how the other voters rank their options!
Stated another way, what Arrow’s theorem shows is that the requirements of respecting unanimity and the independence of irrelevant alternatives are incompatible with a third desirable requirement, namely that the voting system not be a dictatorship.
In full generality, what Arrow’s theorem shows is as follows:
Arrow’s theorem: Suppose we have a voting system to rank [tex]3[/tex] or more voting options. Suppose that system respects unanimity and the independence of independent alternatives. Then there must be a dictator for the voting system.
This theorem ought to shock you. How can the assumptions of unanimity and independence of irrelevant alternatives possibly imply the existence of a dictator?
I’ll now give a short proof of Arrow’s theorem, to give you some feeling for why the theorem is true. However, much of interest can be said about Arrow’s theorem even if you don’t understand the proof, so if you’re so inclined you should feel free to skim or skip the following proof. Of course, those who want to understand Arrow’s theorem deeply should spend some time trying to prove it themselves, before reading the proof in detail.
Proof of Arrow’s theorem: The first step of the proof is to argue that if every voter ranks [tex]S[/tex] either strictly first or strictly last, then [tex]S[/tex]’s social ranking must be either strictly first or strictly last. To see this, we use a proof by contradiction, supposing that in fact [tex]S[/tex]’s social ranking is neither strictly first nor strictly last. That is, we suppose that there exist [tex]T[/tex] and [tex]U[/tex] such that [tex]T \geq S \geq U[/tex]. Suppose we rearrange each voter’s rankings so that [tex]U >_v T[/tex], but without changing the relative ranking of [tex]S[/tex] and [tex]T[/tex], or of [tex]S[/tex] and [tex]U[/tex], so the rearrangement doesn’t affect the fact that [tex]T \geq S[/tex] and [tex]S \geq U[/tex]. (Understanding why such a rearrangement can always be done requires a little thought, and maybe some working out on a separate sheet of paper, which you should do.) Unanimity then requires that [tex]U > T[/tex], which is inconsistent with the fact that [tex]T \geq S \geq U[/tex]. This is the desired contradiction.
Suppose now that we start out with a profile in which [tex]S[/tex] is ranked strictly first by every voter, and thus by unanimity must be ranked strictly first in the social ranking. Suppose we move through the voting population, and for each voter in turn change their ranking for [tex]S[/tex] from strictly first to strictly last. When this has been done for all the voters, unanimity implies that [tex]S[/tex] must be ranked strictly last, and so at some point we see that there must be a voter (who will turn out to be the dictator, [tex]d[/tex]), whose vote change causes [tex]S[/tex] to move from first to last in the social ranking.
Consider the voting profile immediately before [tex]d[/tex] changes their vote. We will say that any profile which has the same rankings for [tex]S[/tex] as this profile is an [tex]S[/tex]-profile. Similarly, an [tex]S'[/tex]-profile is one which has the same rankings for [tex]S[/tex] as the profile just after [tex]d[/tex] changes their vote. It follows from the independence of irrelevant alternatives that the overall ranking of [tex]S[/tex] must be first in any [tex]S[/tex]-profile, and last in any [tex]S'[/tex]-profile.
Suppose now that [tex]T[/tex] and [tex]U[/tex] are voting options that are not equal to [tex]S[/tex]. Suppose [tex]d[/tex] ranks [tex]T[/tex] higher than [tex]U[/tex], i.e., [tex]T >_d U[/tex]. We will show that we must have [tex]T > U[/tex], no matter how the other voters rank [tex]T[/tex] and [tex]U[/tex]. That is, [tex]d[/tex]’s vote dictates that [tex]T[/tex] be ranked above [tex]U[/tex] in the social ranking. To see this, first we rearrange the profile so that it becomes an [tex]S[/tex]-profile, without changing the relative ordering of [tex]T[/tex] and [tex]U[/tex] anywhere, and so not affecting whether [tex]T > U[/tex] or not. We can do this simply by changing each voter’s ranking for [tex]S[/tex] in an appropriate way, placing it either at the top or the bottom of their ranking. Second, we change [tex]d[/tex]’s rankings so that [tex]T >_d S >_d U[/tex]. This can be done without changing the relative ranking of [tex]T[/tex] and [tex]U[/tex], and so does not affect whether [tex]T > U[/tex]. We call the resulting voting profile after these two rearrangements the final profile. Observe that in the final profile we have [tex]S > U[/tex], since if [tex]d[/tex] changes [tex]S[/tex] to be ranked strictly first then we have an [tex]S[/tex]-profile. Similarly, in the final profile we have [tex]T > S[/tex], since if [tex]d[/tex] changes [tex]S[/tex] to be strictly last, then we have an [tex]S'[/tex]-profile. As a result, we have [tex]T > S > U[/tex] in the final profile, and thus [tex]T > U[/tex]. But we constructed the final profile so that [tex]T > U[/tex] holds only if [tex]T > U[/tex] also in the actual voting profile, and so we must have had [tex]T > U[/tex] in the actual voting profile, as we desired to show.
The final step of the proof is to argue that [tex]d[/tex] can also dictate the order of [tex]S[/tex] and [tex]T[/tex], for an arbitrary [tex]T \neq S[/tex]. To see this, pick an element [tex]U[/tex] which is neither [tex]S[/tex] nor [tex]T[/tex], and consider an [tex]S[/tex]-profile in which [tex]U[/tex] is placed strictly last everywhere that [tex]S[/tex] is first, and vice versa. The results of the first and second paragraph of this proof imply that [tex]d[/tex] can change the rank of [tex]U[/tex] from last to first simply by changing their vote. We now apply the same argument as in the paragraph before this, but with [tex]U[/tex] taking the place of [tex]S[/tex], to argue that [tex]d[/tex] can dictate the relative ordering of [tex]S[/tex] and [tex]T[/tex]. QED
Arrow’s theorem is a striking result in the theory of collective decision making. It shows the great advantages that can come by formalizing ideas in a simple mathematical model – the fact that the model can lead to striking unforseen conclusions that entirely change our perception of the phenomenon. More prosaically, by thinking closely about our values and our desired social outcomes, we can try to formalize models of those properties, and then study which models of collective decision making best respect those properties (if, indeed, any such models exists).
What of the implications of Arrow’s theorem for voting? It is, of course, true that the restrictions in Arrow’s theorem can be relaxed, and there is a large literature studying other models of voting and the extent to which they can be made fair. I’m not an expert on this literature, and so won’t comment other than to point out that economists have, of course, not been silent on the matter in the 50 plus years since Arrow’s paper!
My own interest in the subject is due to a more general hobby interest in the problem of collective cognition. In particular, I’m interested in the question of how we can design institutions which result in good collective decision making. It seems that the subject of institutional design is still in its infancy, and I find it remarkable how small a fraction of “institution space” humans have explored. One of the most interesting things about the web, in my opinion, is that it has greatly cut the cost of developing new institutions, and as a result we’re seeing new institutional models, and new types of collective cognition, develop at an incredible rate.
Steve Flammia from the University of New Mexico has been visiting, and has been giving us a great series of tutorial talks on topological quantum computing. Steve has prepared a webpage for his tutorials (to be expanded as the tutorials go on), which you may wish to look at if you’re interested in learning the subject.
I’m going to take another hiatus from blogging, until at least August 1, 2006. I was hoping to come back to my blog properly, but realize that I have too many other things going on. I do hope to blog again one day, and have some ideas for large project into which the blog would be integrated. (I rather like the way Kevin Kelley is using a blog to test out ideas for a book, and could potentially see myself doing the same thing.)
For now, I’ll leave you to ponder a provocative recent comment posted by John Sidles. I haven’t yet read the paper in question, but the authors, Conway and Kochen, are top-notch mathematicians, and I’m looking forward to reading it at some point.
Boy, is it quiet, both here and on Bacon’s Quantum Pontiff. Just to stir things up, what do people think of the preprint on the arxiv server this morning:
The Free Will Theorem” http://www.arxiv.org/abs/quant-ph/0604079
Such titles are often associated with fringe physics — except that these particular nutjobs are the mathematicians John Conway and Simon Kochen!
These guys may be nutjobs, but they are high-power nutjobs, and I enjoyed their preprint very much.
In engineering, we tend to think of every quantum problem as an exercise in model order reduction (MOR). But our MOR colleagues (and there are a lot of them — there are more academic articles by far on MOR than on open quantum systems!) always complain that simulation algorithms for open quantum systems are stochastic. “Can’t you eliminate the stochasticity, and make your open quantum system model deterministic?” they complain.
The Conway/Kochen Free Will Theorem answers that question pretty crisply, by showing that open quantum systems have properties that *no* (locallyrealistic) deterministic simulation can exhibit. And, they prove it in a fun way.
Also, it’s just not right to ignore an article that begins “Do we really have free will, or, as a few determined folk maintain, is it all an illusion? We dont know, but will prove in this paper that if indeed there exist any experimenters with a modicum of free will, then elementary
particles must have their own share of this valuable commodity.”All the above is just to stimulate some comment!
This seems a little redundant, given my recent 6 month break from blogging, but I’m gone on holidays for three weeks starting in about 36 hours, first for two weeks in New Zealand, and then for one more week’s back in Brisbane, which will mostly be spent attending the Ideas Festival. Should be fun, but I won’t be blogging during that time.
This is a plug for a free public lecture (with free drinks and nibblies after) about junk DNA and the role it plays in biology, by Professor John Mattick of the University of Queensland. It’s to be held 6:30 pm, Monday March 13 in the Judith Wright Center, Fortitude Valley, Brisbane.
(The lecture is the first of a monthly series to be known as BrisScience. My partner, Jen Dodd, is running the series.)
The topic of the talk is really interesting. One of the biggest problem in modern biology is how we go from DNA to fully fledged living beings. It’s pretty well understood how we go from DNA to the proteins which form the building blocks for living beings. But that’s a far cry from a full understanding: knowing how to put together a steel girder doesn’t imply that you can build the Eiffel tower or the Empire State building. Figuring out the link between DNA and the large-scale structure (the architectural design, if you like) seems to be very poorly understood.
The speaker, John Mattick, has some really interesting (and controversial) ideas about how this happens. He thinks the so-called junk DNA in the human genome (pieces of the DNA which don’t code for proteins) carries the information about the design. As an outsider it’s hard for me to judge how successful the ideas are, but they’re certainly getting some attention: his work was named by Science magazine in its list of the ten most significant breakthroughs of 2004, and he had an article about it in Scientific American a couple of years back.
It’s probably surprising if you don’t already know it, but in the standard “quantum circuit” model quantum computers are actually quite similar to ordinary computers. A quantum computation is built up out of quantum gates that perform quantum logic operations on quantum bits. All of this proceeds pretty much by analogy with classical computers, where gates perform logical operations on bits. There are some technical differences, but the broad picture is pretty similar.
Mark Dowling, Mile Gu, Andrew Doherty and I have recently developed a rather different geometric approach to quantum computation. (Here’s the link to the abstract, and here’s the link to the full text at Science. Jonathan Oppenheim has also written a nice perspective piece (sorry, I don’t have the full text).)
Our result is pretty simple: we show that finding the best (read smallest) quantum circuit to solve a particular problem is equivalent to finding the shortest paths between two points in a particular curved geometry. Intuitively, this problem is like an orienteer or hiker trying to find the shortest path between two points in a hilly landscape, although the space we are working in is harder to visualize. There’s some technical caveats to the result, but that’s the general gist.
What use is this? At the moment it’s difficult to say – unfortunately, we don’t yet have any killer applications of the result. But our result does mean that problems in quantum computation can be viewed in terms of equivalent problems in the field known as Riemannian geometry. This opens up the possibility of using some of the deep ideas of Riemannian geometry to solve problems in quantum computing. And who knows: maybe ideas from quantum computing will have a useful stimulating effect, injecting new ideas into the study of geometry!
Scott Aaronson is apparently Shtetl-Optimized.
What’s the difference between neon and ammonia?
In its most common isotope, a single neon molecule (one atom, in fact) contains 10 neutrons, 10 electrons, and 10 protons. A single ammonia molecule also contains 10 neutrons, 10 electrons, and 10 protons. It’s the same stuff! I think this is very cool.
Update: Well, I can’t count. Ammonia only has 7 neutrons. I know this kind of phenomenon is possible, because I set it as a problem once in a mini-course I gave on metals and superconductors, and people came back with several solutions. Unfortunately, I don’t remember what they were.
Update II: Potassium Bromide (K Br) and Calcium Selenide (Ca Se) appear to do the trick, assuming no more silly mistakes. Can anyone find a simpler example?
Update III: Helium and Deuterium both have 2 protons, 2 neutrons, and 2 electrons. It’d still be nice to have examples involving two more familiar substances.
Update IV: Commenter Kurt points out a better example: Nitrous Oxide (laughing gas) and Carbon Dioxide, both with 22 electrons, protons, and neutrons. Any better? I think salt and nickel 58 (the most common isotope) also provide an example.
Another quantum wiki – Qwiki. (Who comes up with these names?)
Go forth and contribute!