Random matching models with di erent states are an important class of dynamic games; for example, money search models, job search models, and some games in biology are special cases. In this paper, we investigate the basic structure of the models: the existence of equilibria, the global structure of the set of equilibria, and the approximation and computation of equilibria. Under conditions which are typically satisfied in monetary models, the equilibrium condition can be considered as a non-linear complementarity problem with some new feature.