The Structure of the Lattices of Pure Strategy Nash Equilibria of Binary Games of Strategic Complements

Abstract

It has long been established in the literature that the set of pure strategy Nash equilibria of any binary game of strategic complements among a set N of players can be seen as a lattice on the set of all subsets of N under the partial order defined by the set inclusion relation (subset of). If the game happens to be strict in the sense that players are never indifferent among outcomes, then the resulting lattice of equilibria satisfies a straightforward sparseness condition. In this paper, we show that, in fact, this class of games expresses all such lattices. In particular, we prove that any lattice under set inclusion on the power set of N satisfying this sparseness condition is the set of pure strategy Nash equilibria of some binary game of strategic complements with no indifference. This fact then suggests an interesting way of studying some subclasses of games of strategic complements: By attempting to characterize the subcollections of lattices that each of these classes is able to express. In the second part of the paper we study subclasses of binary games of strategic complements with no indifference, defined by restrictions that capture particular social influence structures: 1) simple games, 2) nested games, 3) hierarchical games 4) clan-like games, and 5) graphical games of thresholds.