Equilibria of Deferred Acceptance with Complete Lists

Abstract

We study the structure of the set of (Nash) equilibria of a deferred acceptance game with complete lists: for a given marriage market with complete lists, men propose to women truthfully while women can accept or reject proposals strategically throughout the deferred-acceptance algorithm. Zhou (1991) studied this game and showed that a matching that is stable with respect to the true preferences can be supported by some preference profile (possibly a non-equilibrium one) if and only if it can be supported by an equilibrium as well. In particular, this result implies the existence of equilibria since the men-optimal stable matching is supported by true preferences and hence an equilibrium outcome. We answer an open question Zhou posed by showing that there need not exist an equilibrium matching that weakly dominates all other equilibrium matchings from the women's point of view (Theorem 1). We complement Zhou's and our findings by showing that the set of equilibrium matchings also need not be "connected'" (Example 2).