COMSOC-2008 progress

Ulle and I recently finished making the program for the 2nd International Workshop on Computational Social Choice (COMSOC-2008), a task that is a bit like solving a sudoku. Then I took a look at some CS conferences that I have been involved with recently, to see how much social choice theory has appeared there. (Not much in CS theory conferences, see below for a summary; but there's more in AI and multiple-agents conferences. Indeed, a few of the COMSOC papers appeared at conferences like AAAI.)

I looked at conferences that attract a lot of computational game theory. So, what is the difference between game theory and social choice theory? Game theory studies the outcomes of interactions amongst multiple agents. Social choice theory is about aggregating multiple opinions/world views/preferences into an overall one. Elections are the most obvious examples of such a process. (For elections to be interesting to study, you have to solicit more than just a single preferred candidate from each voter. If voters provide rank-ordered lists, life gets interesting. It gets more interesting still if the decision is more than just a single winning candidate, e.g. if the decision is a set of winners, or a rank-ordered list.) For computer scientists, game theory is our opportunity to play at being economists. With social choice theory, we get to diversify into politics and philosophy also. (As an aside, at the 2000 BCTCS conference (held here at Liverpool), Les Valiant gave an invited talk in which he proposed an answer to the question: "What academic discipline would have attracted today's computer scientists if computer science had not yet been invented?" I thought he was going to say mathematics, but his answer was philosophy. Which makes a lot of sense, when you think about it.)

EC 2007: 42 papers, nothing obviously about social choice. Mostly game theory and mechanism design.

EC 2008: 38 papers, one of which is "A Sufficient Condition for Voting Rules to be Frequently manipulable" by Xia and Conitzer.

WINE 2007: 31 regular papers and 30 short papers, one of which is "PageRank as a Weak Tournament Solution" by Felix Brandt and Felix Fischer.

Then I took a look at STOC 2008, and was reminded that it is home to a wonderful paper: "The Chow Parameters Problem", by Ryan O'Donnell and Rocco Servedio. This is the paper I was trying to write when I wrote this precursor. Quoting their paper: "In the realm of social choice and voting theory the Chow Parameters represent the Banzhaf power indices of the n voters -- a measure of each one's influence over the outcome." Besides the big technical contribution of this paper, I think it's the first one to explain the importance of Chow parameters both to learning theory as well as voting theory.