This new edition of Introduction to Lattices and Order presents a radical reorganization and updating, though its primary aim is unchanged. The explosive development of theoretical computer science in recent years has, in particular, influenced the book's evolution: a fresh treatment of fixpoints testifies to this and Galois connections now feature prominently. An early presentation of concept analysis gives both a concrete foundation for the subsequent theory of complete lattices and a glimpse of a methodology for data analysis that is (...) of commercial value in social science. Classroom experience has led to numerous pedagogical improvements and many new exercises have been added. As before, exposure to elementary abstract algebra and the notation of set theory are the only prerequisites, making the book suitable for advanced undergraduates and beginning graduate students. It will also be a valuable resource for anyone who meets ordered structures. (shrink)

We introduce a logic specifically designed to support reasoning about social choice functions. The logic includes operators to capture strategic ability, and operators to capture agent preferences. We establish a correspondence between formulae in the logic and properties of social choice functions, and show that the logic is expressively complete with respect to social choice functions, i.e., that every social choice function can be characterised as a formula of the logic. We prove that the logic is decidable, and give a (...) complete axiomatization. To demonstrate the value of the logic, we show in particular how it can be applied to the problem of determining whether a social choice function is strategy-proof. (shrink)

We introduce a logic specifically designed to support reasoning about social choice functions. The logic includes operators to capture strategic ability, and operators to capture agent preferences. We establish a correspondence between formulae in the logic and properties of social choice functions, and show that the logic is expressively complete with respect to social choice functions, i.e., that every social choice function can be characterised as a formula of the logic. We prove that the logic is decidable, and give a (...) complete axiomatization. To demonstrate the value of the logic, we show in particular how it can be applied to the problem of determining whether a social choice function is strategy-proof. (shrink)

This introductory text explores the theory of social choice. Written as a primer suitable for advanced undergraduates and graduates, this text will act as an important starting point for students grappling with the complexities of social choice theory. Rigorous yet accessible, this primer avoids the use of technical language and provides an up-to-date discussion of this rapidly developing field. This is the first in a series of texts published in association with the LSE.

The book presents the main results of descriptive complexity theory, that is, the connections between axiomatizability of classes of finite structures and their complexity with respect to time and space bounds. The logics that are important in this context include fixed-point logics, transitive closure logics, and also certain infinitary languages; their model theory is studied in full detail. Other topics include DATALOG languages, quantifiers and oracles, 0-1 laws, and optimization and approximation problems. The book is written in such a way (...) that the respective parts on model theory and descriptive complexity theory may be read independently. This second edition is a thoroughly revised and enlarged version of the original text. (shrink)

Axiomatic characterization results in social choice theory are usually compared either regarding the normative plausibility or regarding the logical strength of the axioms involved. Here, instead, we propose to compare axiomatizations according to the language used for expressing the axioms. In order to carry out such a comparison, we suggest a formalist approach to axiomatization results which uses a restricted formal logical language to express axioms. Axiomatic characterization results in social choice theory then turn into definability results of formal logic. (...) The advantages of this approach include the possibility of non-axiomatizability results, a distinction between absolute and relative axiomatizations, and the possibility to ask how rich a language needs to be to express certain axioms. We argue for formal minimalism, i.e., for favoring axiomatizations in the weakest language possible. (shrink)

Following Lauwers and Van Liedekerke (1995), this paper explores in a model-theoretic framework the relation between Arrovian aggregation rules and ultraproducts, in order to investigate a source of impossibility results for the case of an infinite number of individuals and an aggregation rule based on a free ultrafilter of decisive coalitions.

Dependence is a common phenomenon, wherever one looks: ecological systems, astronomy, human history, stock markets - but what is the logic of dependence? This book is the first to carry out a systematic logical study of this important concept, giving on the way a precise mathematical treatment of Hintikka’s independence friendly logic. Dependence logic adds the concept of dependence to first order logic. Here the syntax and semantics of dependence logic are studied, dependence logic is given an alternative game theoretic (...) semantics, and results about its complexity are proven. This is a graduate textbook suitable for a special course in logic in mathematics, philosophy and computer science departments, and contains over 200 exercises, many of which have a full solution at the end of the book. It is also accessible to readers, with a basic knowledge of logic, interested in new phenomena in logic. (shrink)

Wulf Gaertner provides a comprehensive account of an important and complex issue within social choice theory: how to establish a social welfare function while restricting the spectrum of individual preferences in a sensible way. Gaertner's starting point is K. J. Arrow's famous 'Impossibility Theorem', which showed that no welfare function could exist if an unrestricted domain of preferences is to be satisfied together with some other appealing conditions. A number of leading economists have tried to provide avenues out of this (...) 'impossibility' by restricting the variety of preferences: here, Gaertner provides a clear and detailed account, using standardized mathematical notation, of well over forty theorems associated with domain conditions. Domain Conditions in Social Choice Theory will be an essential addition to the library of social choice theory for scholars and their advanced graduate students. (shrink)