Abstract. Our objective in this note is to comment briefly on the newly emerging literature on computer-aided proofs in Social Choice Theory. We shall specifically comment on [16] (henceforth TL) and [4] (henceforth GE). In the Appendix we provide statements and brief descriptions of the results discussed in this note. . Primary (91B14,68T15); Secondary (03B35). Keywords. Automated Reasoning, Social Choice Theory, Review. Both of the papers on computer-aided proofs in Social Choice Theory that we have reviewed, TL [16] and GE [4] , adopt the same approach. They prove impossibility results by reducing a problem of an arbitrary size to a "small" base case which is then tackled computationally. TL looks at various versions of the classical Arrovian aggregation problem. It uses conventional induction methods to show that the existence of non-trivial solutions in the general case implies the existence of non-trivial solutions in the base case. It then shows that non-trivial solutions do not exist in the base case thereby establishing an impossibility result. A naive approach to the base case verification is computationally intractable. 1 The idea in the paper is to encode the properties of an Arrovian Social Welfare Function as a Constraint Satisfaction Problem (CSP), which can then be solved using standard algorithmic techniques from computer science. Instead of checking every possible rule for consistency with the axioms, there is an algorithm that iteratively generates rules. If at any point the construction in progress meets a contradiction with any of the axioms applicable in the present stage, the present step and its future course is abandoned. Then a step is backtracked and the algorithm explores other ⋆ We thank three referees for their insightful comments. 1 The smallest interesting case is one with two voters and three alternatives. The number of Arrovian aggregators is 36 6 in this case. A naive approach would be to list each possibility and verify the Independence of Irrelevant Alternative axiom -this is clearly intractable computationally.
The results obtained by computer-aided theorem proving have already found attention in the social choice community REF .
Automated Reasoning in Social Choice Theory - Some Remarks
Mathematics in Computer Science
Computer Science Mathematics