Social choice, arrow's theorem and open problems ?

Question

Last few months I started to lecture myself on social choice, arrow's theorem and related results.

After reading about the seminal results, I asked myself about what happens with partial order preferences, the answer is in the paper of Pini et al.: Aggregating partially ordered preferences: impossibility and possibility results. Then, I wondered if it is possible of finding a characterization of admissible social choice functions. And again someone did it (Complete Characterization of Functions Satisfying the Conditions of Arrow’s Theorem by Mossel and Tamuz). I won't give a full list, but any of the problems related to social choice I can think of where all solved in the last 5 years :(

So, do you know if there exists a survey on what was done recently in the field and what was not done?

Another question is: are you aware of complexity and social choice related problems (for instance the complexity of finding the largest subset of users that are compatible for at least one social choice function, or this kind of question).

Answer 1

Your question is very well timed, because the most recent issue of the CACM has an article that does exactly this: http://cacm.acm.org/magazines/2010/11/100640-using-complexity-to-protect-elections/fulltext

In brief, there's a lot of work by Conitzer, Tovey and others on the actual hardness, both worst-case and under distributional assumptions, of cracking voting mechanisms that are in principle breakable via Arrow's theorem.

Answer 2

There are many complexity issues that are related to many of the topics that come up in what has come to be called social choice theory. These include the complexity of deciding who is the winner when a particular method is used to amalgamate the ballots of a certain type into a choice for society. There are also complexity issues involved in trying find a way to vote strategically (rather than using one's true preferences) when information may be available about other voter's preferences when a particular method is being used in the hopes of getting a better outcome for a particular person or a group of people. Complexity also comes up in designing "safe" on line voting systems.

These is a huge literature about social choice but some good books to get started for those interested would be:

Donald Saari, Decisions and Elections, Cambridge U. Press, 2001.

Donald Saari, Disposing Dictators, Demystifying Voting Paradoxes, Cambridge U. Press, 2008.

Alan Taylor, Social Choice and the Mathematics of Manipulation, Cambridge U. Press, 2005.

Answer 3

There have been many recent developments on the computational aspects of social choice. The following website gives many pointers to the relevant literature:

http://www.illc.uva.nl/COMSOC/

Answer 4

Arrow's theorem is a classical theorem. Finding an open problem is not easy for social choice theorists (or at least for me), either.

My general advice to students studying economics is: "stay way from the theorem, unless you can relate your contribution to some recent ideas (e.g., axioms that has been proposed recently, solutions that has been studied a bit, and behavioral assumptions in fashion). Try to find a problem unrelated to Arrow's theorem. There are many such problems even within social choice theory." Only after you have a general idea what sort of problem you want to pursue, check the Handbook of Social Choice and Welfare.

Computational issues could be one of such "recent" ideas. Though the investigation of complexity (of the rules or of manipulation or of the solution, etc.) is the main concern for computer scientists (as suggested by others), there do exit papers (such as Mihara, 1997, Arrow's Theorem and Turing Computability, Economic Theory 10:257-276) that studies the (fundamental?) problem of computability within Arrow's framework. ;-)

Let me comment on the two problems you suggested.

1. I'm not sure if social choice theorists neglected to consider partial orders. If they did, they did so probably because "partiality" can be expressed by strict preferences (as we do in Kumabe and Mihara, Preference aggregation theory without acyclicity: The core without majority dissatisfaction, Games and Economic Behavior, in press). (In that case, better forget the weak preference R or define it differently [so it will not become complete]: By defining xRy [x is weakly preferred to y] iff not yPx [not y is preferred to x], we have P is asymmetric iff R is complete!)

2. Some authors are not, but I guess most social choice theorists are careful enough not to claim that any dictatorial social welfare function satisfy IIA. For example, I say (Mihara, 1997) that within the social welfare functions satisfying IIA, a rule is dictatorial iff it satisfies a certain condition. So they knew the problem was open, but were probably not interested in further classifying dictatorial functions. (Maybe Mossel and Tamuz can comment on Armstrong's errata cited by Mihara. It identifies a sequence of dictators or ultrafilters.) This suggests another research strategy (which I cannot recommend): try to find a problem that was uninteresting to social choice theorists.