The distribution of envy in matching markets
研究了随机匹配市场中在延迟接受算法下嫉妒的分布，计算了无人嫉妒和嫉妒他人的提议者期望数量，并与随机独裁机制对比，发现两者无人嫉妒的提议者数量相同且占比渐近为零。
We study the distribution of envy in random matching markets under the Deferred Acceptance (DA) algorithm. Using tools from applied probability, we compute the expected number of proposing agents whom nobody envies and those who envy nobody. We obtain an exact finite-market expression for the former, based on a connection with the coupon collector problem, and asymptotic bounds for the latter. To put these quantities into perspective, we compare them to their counterparts under Random Serial Dictatorship (RSD): while RSD assigns a constant fraction of agents to their top choice, both DA and RSD leave exactly H n proposing agents unenvied in expectation. Our results show that these clearly unimprovable proposing agents constitute a vanishing fraction of the market. • We study the distribution of envy in random matching markets. • We derive exact expressions under Deferred Acceptance. • The expected number of unenvied students equals the n th harmonic number. • Students receiving top choices follow an approximately geometric rank distribution. • DA and Random Serial Dictatorship produce identical numbers of unenvied students. • Both unenvied and envy-free student fractions vanish asymptotically.