Dagstuhl 10101

I am at Dagstuhl seminar 10101 (schedule) on computational social choice; it ends tomorrow. Much of the chatter in the evenings has been about the AAAI conference, due to author feedback to reviews being made available a couple of days ago; to a lesser extent ACM-EC accepted papers, also announced a couple of days ago. I will not try to do a complete overview; let me try a more vignette-like approach.

A nice talk by Jérome Lang was in the context of conducting a collection of yes/no votes where there is preferential dependencies between attributes, meaning that a voter's support for one issue may depend on the outcome of the vote on one or more of the other issues. The example used was voting to build a swimming pool and voting to build a tennis court, where some voters would like one or the other, but not both (too expensive). Each voter is represented by a preference relation on the 4 possible outcomes (for n yes/no issues, he uses a more concise representation, "CB-nets"). The question is, how hard is it for the "chair" (who chooses which order the issues are voted on) to control the outcome. Commonly NP-hard, which is taken to be good news, although it is noted that it raises the question of easier manipulation in typical or average cases. That issue is analogous to the hardness of a voter choosing a strategic vote (a ranking of the candidates that is not his true ranking) so as to get a better outcome. While that is NP-hard for some voting schemes, it may often be easy in practical settings. Indeed, Edith Hemaspaandra's talk was about polynomial-time manipulability when there is single-peaked preferences over the candidates.

The rump session (not covered in the above schedule) was 11 talks each of 5 minutes, really aimed at stating problems where no results have been obtained. I gave an introduction to the "chairman's paradox" (to ask about related computational issues) -- it was identified by Farquharson in 1969 and goes as follows. Say you have a committee of 3 voters {1,2,3} who have to choose one of 3 outcomes {A,B,C}. Let voter 1 be the "chair" and voters 2 and 3 be the ordinary members. The special role of the chair is that if all 3 outcomes get one vote each, then the one supported by the chair is the winner. The paradox is that if the voters' preference lists are generated at random, and your solution concept is pure Nash equilibrium, then the chair gets what he wants less often than the other members. For example, consider the (Condorcet cycle) preferences where 1 has preferences ABC (in descending order), 2 has preferences BCA and 3 has preferences CAB. Then, voter 2 will vote for C since that results in C rather than A winning (2 and 3 supporting C). Voters 1 and 3 continue to support A and C respectively, having no incentive to switch. That is the only pure Nash equilibrium that results from iterative removal of weakly dominated strategies, and notice that 1 (the chair) gets his worst outcome C. I will note that the last time I had to chair a committee of this nature, I felt disadvantaged, although not quite for this reason. The session contained an interesting talk by Kóczy on a method for ranking economics journals (someone has to do it I suppose; see this article on the ranking obsession factor). Finally I should surely mention Felix Brandt's entertaining talk on the "kicker theorem".

Edith Elkind's talk on plurality voting with abstentions was related to the above in using pure Nash equilibrium as the solution concept with a bunch of voters and alternatives (not just 3). An interesting open problem she raised is: Suppose you have sets of voters and alternatives, and for each voter/alternative pair there's a numerical utility of that outcome to that voter. Assume that in the event of a tie, the voter's utility is the average (furthermore, let's assume that all numbers and averages are distinct). Suppose voters cast their votes in some prescribed order, and consider the solution concept of subgame perfect equilibrium. What is the complexity of computing their votes? (On a less formal note, Aviv Zohar told me about a "taxicab game" he had played rather poorly, in which a sequence of (say) 10 people board a minibus with 11 seats, and you aim to end up next to the vacant seat, or failing that, maybe some seats/neighbours are better than others. OK, it needs to be specified more precisely.)

Here is another recent blog post on computational social choice, just to prove I have been paying attention.