On the computability of quasi-transitive binary social choice rules in an infinite society and the halting problem
Tóm tắt
This paper investigates the computability problem of the existence of a vetoer and an oligarchy for quasi-transitive binary social choice rules (Mas-Colell and Sonnenschein in Rev Econ Stud 39:185–192, 1972) in a society with an infinite number of individuals (infinite society) according to the computable calculus (or computable analysis) by Aberth (Computable analysis, McGraw-Hill, New York, 1980; Computable calculus, Academic Press, Dublin, 2001). We will show the following results. The problem whether a quasi-transitive binary social choice rule which satisfies Pareto principle and independence of irrelevant alternatives (IIA) has a vetoer or has no vetoer in an infinite society is a nonsolvable problem, that is, there exists no ideal computer program for a quasi-transitive binary social choice rule which satisfies Pareto principle and IIA that decides whether it has a vetoer or has no vetoer. And it is equivalent to nonsolvability of the halting problem. We also show that if for any quasi-transitive binary social choice rule there exists an oligarchy in an infinite society, whether it is finite or infinite is a nonsolvable problem. A vetoer is an individual such that if he strictly prefers an alternative to another alternative, then the society prefers the former to the latter or is indifferent between them regardless of the preferences of other individuals, and an oligarchy is the minimal set of individuals which has dictatorial power and its each member is a vetoer. It will be shown that an oligarchy is a set of vetoers if it exists.
Tài liệu tham khảo
Aberth O.: Computable Analysis. McGraw-Hill, New York (1980)
Aberth O.: Computable Calculus. Academic Press, Dublin (2001)
Arrow K.J.: Social Choice and Individual Values, 2nd edn. Yale University Press, New Haven (1963)
Hansson B.: The existence of group preference functions. Public Choice 28, 89–98 (1976)
Fishburn P.C.: Arrow’s impossibility theorem: concise proof and infinite voters. J. Econ. Theory 2, 103–106 (1970)
Kirman A.P., Sondermann D.: Arrow’s theorem, many agents and invisible dictators. J. Econ. Theory 5, 267–277 (1972)
Mihara R.: Arrow’s theorem and Turing computability. Econ. Theory 10, 257–276 (1997)
Mas-Colell A., Sonnenschein H.: General possibility theorems for group decisions. Rev. Econ. Stud. 39, 185–192 (1972)
Sen A.: Collective Choice and Social Welfare. North-Holland, Amsterdam (1979)
Suzumura K.: Welfare economics beyond welfarist-consequentialism. Japanese Econ. Rev. 51, 1–32 (2000)
Tanaka Y.: On the computability of binary social choice rules in an infinite society and the halting problem. Appl. Math. Comput. 197, 598–603 (2008)
Taylor A.: Social Choice and the Mathematics of Manipulation. Cambridge University Press, London (2005)