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.