Legend has it that when Hugo Sonnenschein was editor of Econometrica, he declared an embargo on papers in social choice. To borrow from Ecclesiastes: `of the making of impossibility theorems there is no end, and much reading of them is a weariness of the soul’. Why the community soured on impossibility theorems on principle escapes me. The world is the way it is and not the way we want it to be. But, I digress. Returning to Sonnenschein’s action, the sweep of it fair takes one breath away. Were a Sonnenschein at the helm of Econometrica now, what might be on the chopping block? Decision Theory? But, I digress, again.
What prompted these ruminations, was computational social choice. The subject begins, I suppose, with a paper by Bartholdi, Tovey, and Trick (Voting Schemes for which It Can Be Difficult to Tell Who Won the Election) in which it is shown that the Dodgson rule is NP-hard. An interesting mathematical observation, but does it matter? Only if the Dodgson rule is a compelling one. However, it has a number of properties that make it unappealing. Second, when would the complexity constraint bite? When there are a large number of voters? In these cases, the number of candidates is usually very small.
The Bartholdi, Tovey & Trick paper has inspired attempts to approximate the Dodgson rule by interpreting the rule as an optimization problem. Again, approximation can only be a concern if the complexity constraint bites. Further, approximation ratios are a cardinal notion while the inputs to a voting problem are ordinal in nature. More importantly, why is `closeness’ to a particular rule a compelling criterion for selecting a rule? After all, there is no guarantee that `closeness’ in the optimization sense means that the approximate rule has similar properties to the target rule.
Anyway, ruminations. Let a thousand flowers bloom.
5 comments
March 12, 2010 at 4:50 pm
Paul Goldberg
Bartholdi, Tovey and Trick wrote another paper at that time: “The Computational Difficulty of Manipulating an Election”, SCW 1989, which is the starting-point for another large chunk of the computational social choice literature (I would guess, a larger chunk than the work on elections for which it is hard to tell who wins).
March 13, 2010 at 6:23 am
Michael Trick
My memory from that time is that all three papers (the one in the post, the one in Paul’s comment, and one on manipulating by doing things like adding an deleting voters) were rejected, often quite quickly, by mainstream economics journals before finding friendly homes in journals like Social Choice and Welfare. But was not Sonnenschein’s fault: his term at Econometrica ended in 1984.
March 13, 2010 at 12:22 pm
Eran
I think the computer science intuition of looking at the worst case is very appealing for election rules, even if as you say the complexity constraint usually does not bite. If the rule should become the law, then the law should be explicit enough to say what happen in every case. It’s part of the concept of election that voters know what will be the outcome for every cirumstances
March 13, 2010 at 2:51 pm
Non-archival conferences? « Algorithmic Game Theory
[...] Finally, there is the all important question how much weight and prestige is attached to the conference publication, in hiring, promotion, or grant decisions (as is uniquely done in CS). This again widely differs between institutions, as well as the issue in question. For example, from my limited experience, more weight is given to conference publications in hiring decisions than in tenure decisions, and more weight is give to conference publications by top ranked departments than by lower ranked ones. Is this prestige a function of the “archival” status of the conference? I doubt it. The bottom line is that at first approximation any conference will gain or lose prestige according to whether appearing in it is indeed an indication of scientific quality. In the case of COMSOC, as for any other young conference, this still remains to be seen. [...]
March 14, 2010 at 3:51 pm
Ariel Procaccia
These are very interesting issues. I’d like to briefly offer my view as a coauthor on the two papers that (to the best of my understanding) the post is implicitly referring to (in SODA’09 and EC’10).
1. I absolutely agree with Eran’s comment.
2. Regarding the statement “approximation ratios are a cardinal notion while the inputs to a voting problem are ordinal in nature”, while this is true, the *output* of the voting problem is cardinal (i.e., the Dodgson score of a candidate), and this is the target that is being approximated. One can argue that the Dodgson ranking, in a sense, should be approximated (that is, that the approximation should not elect a candidate that is low in the Dodgson ranking), but this is a different issue, which we address in the SODA’09 paper.
3. Regarding the statement “there is no guarantee that `closeness’ in the optimization sense means that the approximate rule has similar properties to the target rule”, I also agree, and indeed in the EC’10 paper we provide Dodgson approximations that in fact satisfy desirable social choice properties that Dodgson itself fails (monotonicity and homogeneity). One can argue that in this case it is unclear why one shouldn’t use Maximin or Copeland, but this is a different issue (which we believe we can address).