Echenique (2003)

Echenique, F. (2003), The Equilibrium Set of a Two Player Game with Complementarities is a Sublattice, Economic Theory, 22: 903-905.  Link 

Summary  I prove that the equilibrium set in a two-player game with complementarities, and totally ordered strategy spaces, is a sublattice of the joint strategy space.

It is widely known that in games with strategic complementarities (GSC), i.e., best reply correspondings are monotone increasing for all players, the set of pure-strategy Nash equilibria forms a non-empty complete lattice. This result implies the existence of smallest and largest Nash equilibria.

The current paper looks further into the structure of the equilibrium set of GSC, and shows that under certain restrictions the equilibrium set becomes not just a complete lattice but also a sublattice, as is written down in the Summary above.

The practical importance of this result, according to the author, is:

If the equilibrium set of a game is a sublattice, then we can find new equilibria from knowing that two profiles are equilibria, and by taking the componentwise join and meet of players’ strategies.

Note that we cannot obtain such strong property by a complete lattice structure alone. In this sense, a sublattice is indeed critical. The proof is extremely simple, which makes use of the observation that (a) when there are only 2 players and (b) their strategy spaces are completely ordered, (c) the other player's strategy must be completely ordered. The property (c) does not hold either (a) or (b) is not satisfied. Once (c) is verified, the rest of the proof is just to follow the definition of GSC.

My random thought: A sublattice property also arises in one-to-one two-sided matching markets (but neither in one-to-many nor many-to-many markets). I'm wondering if the idea of this paper can be somehow connected to the sublattice property of the set of stable matchings.

A final remark: A nicely written but a bit uninformative note.

Complementarity and supermodularity

I found a nice summary of key concepts in game theory, complementarity and supermodularity, which are especially important for auction and matching theory.


"Supermodularity and supermodular games" byXavier Vives
in the new palgrave dictionary of economics:


The below is quoted from Xavier's survey.

The basic idea of complementarity is that the marginal value of an action increases with the level of other actions available. The mathematical concept of supermodularity formalizes the idea of complementarity. The theory of monotone comparative statics and supermodular games provides the toolbox to deal with complementarities.

This theory, in contrast to classical convex analysis, is based on order and monotonicity properties on lattices. Monotone comparative statics analysis provides conditions under which optimal solutions to optimization problems change monotonically with a parameter.

The theory of supermodular games exploits order properties to ensure that the best response of a player to the actions of rivals increases with their level. The power of the approach is that it clarifies the drivers of comparative statics results and the need of regularity conditions; it allows very general strategy spaces, including indivisibilities and functional spaces such as those arising in dynamic or Bayesian games; it establishes the existence of equilibrium in pure strategies; it allows a global analysis of the equilibrium set when there are multiple equilibria, which has an order structure with largest and smallest elements; and finally, it finds that those extremal equilibria have strong stability properties and there is an algorithm to compute them.