On the computability of binary social choice rules in an infinite society and the halting problem

详细信息    查看全文

• 作者：Yasuhito Tanaka
• 关键词：Arrow impossibility theorem ; Infinite society ; Nonsolvable problem ; Halting problem
• 刊名：Applied Mathematics and Computation
• 出版年：2008
• 出版时间：1 April 2008
• 年：2008
• 卷：197
• 期：2
• 页码：598-603
• 全文大小：116 K

文摘

This paper investigates the computability problem of the Arrow impossibility theorem [K.J. Arrow, Social Choice and Individual Values, second ed., Yale University Press, 1963] of social choice theory in a society with an infinite number of individuals (infinite society) according to the computable calculus (or computable analysis) by Aberth [O. Aberth, Computable Analysis, McGraw-Hill, 1980, O. Aberth, Computable Calculus, Academic Press, 2001]. We will show the following results. The problem whether a transitive binary social choice rule satisfying Pareto principle and independence of irrelevant alternatives (IIA) has a dictator or has no dictator in an infinite society is a nonsolvable problem, that is, there exists no ideal computer program for a transitive binary social choice rule satisfying Pareto principle and IIA that decides whether the binary social choice rule has a dictator or has no dictator. And it is equivalent to nonsolvability of the halting problem. A binary social choice rule is a function from profiles of individual preferences to social preferences, and a dictator is an individual such that if he strictly prefers an alternative to another alternative, then the society must also strictly prefer the former to the latter.