The Law of Large Numbers for Large Stable Matchings

A stable matching between two sets of agents (such as students and colleges) has received a great deal of attention in the literature. For an empirical study of matching markets, the main statistics of interest are the matching frequencies, which show the fraction of students of a given type who match with colleges of a given type. We study the concentration-of-measure phenomenon for matching frequencies when the observed matching is generated from a Deferred Acceptance algorithm. We introduce a notion of partial homogeneity of preferences to express correlated priorities of colleges over students, and demonstrate the relation between partial homogeneity and concentration of measure. Our concentration inequality immediately yields the rate of convergence for the law of large numbers for matching frequencies.