Acyclic Sets of Linear Orders (joint with Vic Reiner)

Social Choice and Welfare, vol.30 n.2 (February 2008), 245-264.

We show that Abello's acyclic sets of linear orders [Abello(1991)] can be described as the permutations visited by commuting equivalence classes of maximal reduced decompositions. This allows us to strengthen Abello's structural result: we show that acyclic sets arising from this construction are distributive sublattices of the weak Bruhat order. Fishburn's alternating scheme is shown to be a special case. Any acyclic set that arises in this way can be represented by an arrangement of pseudolines, and we use this representation to derive a simple closed form for the cardinality of the alternating scheme. The higher Bruhat orders prove to be a natural mathematical framework for this approach to the acyclic sets problem.

Revealed Preference in Game Theory

I characterize joint choice behavior generated by the pure strategy Nash equilibrium solution concept by an extension of the Congruence Axiom of [Richter(1966)] to multiple agents. At the same time, I relax the ''complete domain'' assumption of [Yanovskaya(1980)] and [Sprumont(2000)] to ''closed domain.'' Without any restrictions on the domain of the choice correspondence, determining pure strategy Nash rationalizability is computationally very complex. Specifically, it is NP-complete even if there are only two players. In contrast, the analogous problem with a single decision maker can be determined in polynomial time.

New version incorporating descriptive complexity results: The Complexity of Nash Rationalizability


Disagreement and Evidence Production in Strategic Information Transmission (joint with Péter Esö)

Forthcoming in International Journal of Game Theory

We expand the Crawford-Sobel (1982) model of information transmission to allow for the costly provision of “hard evidence” in addition to free “soft signals” (i.e., conventional cheap talk). We prove the existence of an interval-partition equilibrium, where each cheap-talk message is sent by an interval of Sender-types, while hard signals are sent by types belonging to a finite union of intervals. We also show that the availability of costly hard signals may reverse one of the important implications of the classical cheap talk model, namely, that diverging preferences always lead to less communication.

Online appendix

Falsifiability, Complexity, and Choice Theories

At least since the 1930s, questions of falsifiability have been studied in the economics literature. Revealed preference theory serves as a methodological foundation for consumer theory, whose empirical content is demarcated by revealed preference conditions. During the past decade, an extensive literature on the testability of collective choice theories has developed. (Carvajal et al, 2004; Sprumont, 2000) We show that choice theories are falsifiable in a strong sense, as defined by the notion of finite and irrevocable testability (FIT-ness), which was introduced by Herbert Simon and Guy Groen (Simon and Groen, 1973). Another approach to examining the empirical content of a theory is known as Ramsey eliminability. We use complexity theory to refine the notion of Ramsey eliminability for finite structures, and thereby introduce degrees of testability in a natural way. Using the theories of individual preference maximization and Nash equilibrium, we show the usefulness of our new notion. In particular, the theory of individual preference maximization is more testable than the theory of Nash equilibrium.