A Generalization of Arrow's Impossibility Theorem Through Combinatorial Topology

Résumé 0

We present a generalization of Arrow's impossibility theorem and prove it using a combinatorial topology framework. Instead of assuming the unrestricted domain, we introduce a domain restriction called the class of polarization and diversity over triples. The domains in this class are defined by requiring profiles in which society is strongly, but not completely, polarized over how to rank triples of alternatives, as well as some profiles that violate the value-restriction condition. To prove this result, we use the combinatorial topology approach started by Rajsbaum and Ravent\'os-Pujol in the ACM Symposium on Principles of Distributed Computing (PODC) 2022, which in turn is based on the algebraic topology framework started by Baryshnikov in 1993. While Rajsbaum and Ravent\'os-Pujol employed this approach to study Arrow's impossibility theorem and domain restrictions for the case of two voters and three alternatives, we extend it for the general case of any finite number of alternatives and voters. Although allowing for arbitrary (finite) alternatives and voters results in simplicial complexes of high dimension, our findings demonstrate that these complexes can be effectively analyzed by examining their $2$$\unicode{x2013}$skeleton, even within the context of domain restrictions at the level of the $2$$\unicode{x2013}$skeleton.