Paul Goldberg is correct to note that I picked on one thread in the literature on Computational Social Choice. By coincidence, Paul himself had just posted a piece on computational social choice on his blog. The other thread is the Bartholdi, Tovey & Trick piece on the hardness of manipulation. The result here is that some voting rules have the property that finding a beneficial deviation from sincere reporting of preferences is NP-hard. At first glance this seems to be a promising weakening of strategy-proofness. Since I’m in a Judge Jeffries mood I’ll argue the contrary. First, this is a worst-case result. It is not that every instance will be `hard’. Only that there will be some instances that will tax ones computational resources. Second, even in these cases, it is only when the instances are large that NP-hardness bites.
Eran, argued that should a voting rule become law, “then the law should be explicit enough to say what happen in every case.” Agreed, but NP-hardness does not mean the rule is not well defined. Only that it might take a long time to compute the outcome. In any case, we do have plenty of examples of laws and contractual arrangements that are`incomplete’ in the sense they do not specify the outcome in every contingency.
Michael Trick was kind enough to absolve Hugo S. of any responsibility for the placement of the relevant papers. I did not intend to suggest otherwise. Only, that reading some of the papers in computational social choice reminded me of the event.
2 comments
March 14, 2010 at 4:05 pm
Eran
many laws don’t specify the outcome in every contingency, but I think for election laws this is essential. It is very strange to participate in an election where you can’t know how to determine the winner from the outcome of the vote. it’s like voting when you don’t know the voting rule at all.
Now NP complete doesn’t mean exactly `can’t know’ (in fact it doesn’t even exactly says it takes long time — maybe the problem is actually feasible in real world sizes of inputs) but i view it is a good conceptual approximation of `can’t know’
March 17, 2010 at 2:11 am
Ariel Procaccia
I agree with the criticism in the first paragraph, however there is a significant line of work in computational social choice (which was initiated in 2006 and by now contains some 15 papers) that indeed challenges the worst-case complexity barrier against manipulation, and instead looks at different flavors of the typical/average case.