#cstheory

Arrow's theorem is a famous statement about the difficulty of preference aggregation, something that I've written on a lot over the last couple years in reference to national security policy. 

Via Wikipedia: 

Arrow's monograph Social Choice and Individual Values derives from his Ph.D. thesis. In it he sets out a key result (in one final form).

General Impossibility Theorem: It is impossible to formulate a social preference ordering that satisfies all of the following conditions:

Nondictatorship: The preferences of an individual should not become the group ranking without considering the preferences of others.

Individual Sovereignty: each individual should be able to order the choices in any way and indicate ties

Unanimity: If every individual prefers one choice to another, then the group ranking should do the same

Freedom From Irrelevant Alternatives: If a choice is removed, then the others' order should not change

Uniqueness of Group Rank: The method should yield the same result whenever applied to a set of preferences. The group ranking should be transitive.

The folks at Turing's Invisible Hand explain some ways to quantify the impossibility: 

Social Choice Theory is a pretty mature field that deals with the question of how to combine the preferences of different individuals into a single preference or a single choice.  This field may serve as a conceptual foundation in many areas: political science (how to organize elections), law (how to set commercial laws), economics (how to allocate goods), and computer science (networking protocols, interaction between software agents).  Unsurprisingly, there are interesting computational aspects to this field, and indeed a workshop series on computational social choice already exists.  The starting point of this field is Arrow‘s theorem that shows the there are unexpected inherent difficulties in performing this preference aggregation.  There have been many different proofs of Arrow’s impossibility theorem, all of them combinatorial.  In this post I’ll explain a basic observation of Gil Kalai that allows quantifying the level of impossibility using analytical tools (Fourier transform) on Boolean functions commonly used in theoretical computer science.  At first Gil’s introduction of these tools in this context seemed artificial to me, but in this post I hope to show you that  it is the natural thing to do.

I hope you will see that this isn't just a "gee whiz, math and computers" thing. Understanding this in terms of computational complexity helps us get a better handle on the difficulties of creating desired social outcomes -- if we view governance as in part an information-processing task.