<p>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.</p>

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

<p>Donald Saari, Decisions and Elections, Cambridge U. Press, 2001.</p>

<p>Donald Saari, Disposing Dictators, Demystifying Voting Paradoxes, Cambridge U. Press, 2008.</p>

<p>Alan Taylor, Social Choice and the Mathematics of Manipulation, Cambridge U. Press, 2005.</p>

CC BY-SA 2.5
2010-11-04T21:33:02.473Z
2010-11-04T21:33:02.473Z
Joseph Malkevitch
<p>There have been many recent developments on the computational aspects of social choice.
The following website gives many pointers to the relevant literature:</p>

<p><a href="http://www.illc.uva.nl/COMSOC/">http://www.illc.uva.nl/COMSOC/</a></p>

CC BY-SA 2.5
2010-11-05T05:42:43.827Z
2010-11-06T19:31:45.630Z
2010-11-06T19:31:45.630Z
h.a
<p>Arrow's theorem is a classical theorem.  Finding an open problem is not easy for social choice theorists (or at least for me), either.</p>

<p>My general advice to students studying economics is: "stay way from the theorem, <em>unless you can relate your contribution to some recent ideas</em> (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 <em>Handbook of Social Choice and Welfare</em>.</p>

<p>Computational issues could be one of such "recent" ideas.  Though the investigation of <em>complexity</em> (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, <em>Economic Theory</em> 10:257-276) that studies the (fundamental?) problem of  <em>computability</em> within Arrow's framework. ;-)</p>

<p>Let me comment on the two problems you suggested.</p>

<ol>
<li><p>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, <em>Games and Economic Behavior</em>, 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 <em>complete</em>!)</p></li>
<li><p>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 <em>within the social welfare functions satisfying IIA</em>, a rule is dictatorial <em>iff</em> 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.</p></li>
</ol>

CC BY-SA 2.5
2010-11-30T06:49:43.820Z
2010-11-30T06:49:43.820Z
H. Reiju Mihara
<p>Your question is very well timed, because the most recent issue of the CACM has an article      that does exactly this: <a href="http://cacm.acm.org/magazines/2010/11/100640-using-complexity-to-protect-elections/fulltext">http://cacm.acm.org/magazines/2010/11/100640-using-complexity-to-protect-elections/fulltext</a></p>

<p>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. </p>

CC BY-SA 2.5
2010-11-05T16:43:09.687Z
I am accepting this one because it is the most upvoted, but all answers have been of interest for me. Thank you all!
Sylvain Peyronnet
CC BY-SA 2.5
2010-11-04T15:29:21.720Z
2010-11-04T15:29:21.720Z
Suresh Venkat
<p>Last few months I started to lecture myself on social choice, arrow's theorem and related results.</p>

<p>After reading about the seminal results, I asked myself about what happens with partial order preferences, the answer is in the paper of Pini <em>et al.</em>: <a href="http://www.math.unipd.it/~mpini/Conference--%20dastampare/01-tark05-acm.pdf">Aggregating partially ordered preferences: impossibility and possibility results</a>. Then, I wondered if it is possible of finding a characterization of admissible social choice functions. And again someone did it (<a href="http://arxiv.org/pdf/0910.2465">Complete Characterization of Functions Satisfying the Conditions of Arrow’s Theorem</a> 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 :(</p>

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

<p>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).</p>

<co.combinatorics><gt.game-theory><boolean-functions><social-sciences>
Social choice, arrow's theorem and open problems ?
Sylvain Peyronnet
# Social choice, arrow's theorem and open problems ?

(Asked by: username_0 on 2010-11-04)

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](http://www.math.unipd.it/~mpini/Conference--%20dastampare/01-tark05-acm.pdf). 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](http://arxiv.org/pdf/0910.2465) 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).

**Tags:** co.combinatorics, gt.game-theory, boolean-functions, social-sciences

---

## 4 answers

### Answer by username_4 on 2010-11-04. Score: 18 | Accepted answer

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.

> **Comments:**
> **username_0**: I am accepting this one because it is the most upvoted, but all answers have been of interest for me. Thank you all!  

---

### Answer by username_1 on 2010-11-04. Score: 12

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 by username_2 on 2010-11-05. Score: 9

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 by username_3 on 2010-11-30. Score: 7

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.


---

