Social choice and the logic of simple games

摘要

Using Pauly's majority logic, a modal-like language that describes decisions of a collective of agents, this article develops an explicit relationship between logic and social choice theory, particularly judgement aggregation. Majority logic is, within certain limits, able to express properties of decision procedures that are used to reach collective judgements. Those properties are often facts about the validity of logical inference rules at the level of collective decision making. From the perspective of social choice theory, formulae of majority logic can be regarded as axioms about the possibility of correct collective inference. Exploring the link with modal logic, and using so-called simple games as the mathematical structures representing decision procedures, we argue that the axiomatizations of social choice theorists mimic definability results from the perspective of modal logicians. Sets of formulae of majority logic define classes of decision procedures in this sense. Based on simple games, we give a game-theoretic characterization of properties of decision procedures that can be expressed using majority logic. From this, we deduce the closure conditions on classes of decision procedures that are definable using majority logic. This establishes a concrete link between a language in which axioms may be formulated, and the properties of decision procedures that it is able to characterize. Closure conditions also allow us to determine limits to the expressive and axiomatic power of majority logic. Since much of social choice theory is occupied with finding decision procedures that admit valid collective inference, and this is the domain of majority logic, quite a few familiar classes of decision procedures are definable. However, we show that majority logic is too weak to express non-dictatorship-in effect a language-relative impossibility result. We relate these definability results to recent results obtained in the judgement aggregation literature, in particular to some of the impossibility results.