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.