2024/02/28 by Benedict Eastaugh · 1 voice
Computer Science · #Computability, Logic, AI Algorithms #Logic, Reasoning, and Knowledge #Complexity and Algorithms in Graphs
paper · pdf · doi:10.1017/s1755020324000054
Abstract This paper initiates the reverse mathematics of social choice theory, studying Arrow’s impossibility theorem and related results including Fishburn’s possibility theorem and the Kirman–Sondermann theorem within the framework of reverse mathematics. We formalise fundamental notions of social choice theory in second-order arithmetic, yielding a definition of countable society which is tractable in \mathsf RCA0 . We then show that the Kirman–Sondermann analysis of social welfare functions can be carried out in \mathsf RCA0 . This approach yields a proof of Arrow’s theorem in \mathsf RCA0 , and thus in \mathrm PRA , since Arrow’s theorem can be formalised as a Π 01 sentence. Finally we show that Fishburn’s possibility theorem for countable societies is equivalent to \mathsf ACA0 over \mathsf RCA0 .