Unbalanced random matching markets
Unbalanced random matching markets
复制标题
DOI：
10.1145/2482540.2482590
复制
发表时间：
2013-06
期刊：
影响因子：
--
通讯作者：
I. Ashlagi;Yashodhan Kanoria;Jacob D. Leshno
中科院分区：
文献类型：
--
作者：
I. Ashlagi;Yashodhan Kanoria;Jacob D. Leshno
我们分析男女人数不等的大型随机匹配市场。agent有完整的、均匀随机的、独立的偏好列表，我们考虑在已实现偏好下的稳定匹配。我们发现，做空市场会带来很大的优势。我们描述了男人妻子的平均等级。对于每个代理，将其最喜欢的伙伴分配为1，将其最喜欢的伙伴分配为2，依此类推。如果有n个男性和n+1个女性，那么我们可以证明，在任何稳定匹配中，男性对其妻子的平均排名不大于3 log n，而女性对其丈夫的平均排名至少为n（3 log n）。如果在λ0下有n个男人和（1+λ）n个女人，那么在任何一个稳定匹配中，男人的平均妻子排名是O(1)，而女人的平均丈夫排名是λ (n)。此外，我们发现在每种情况whp下，拥有多个稳定伙伴的代理数量为o(n)。因此，我们的结果表明，在实现稳定匹配的机制中，在不平衡随机匹配市场中操纵的范围有限。这些结果与之前已知的男女人数相等的随机配对市场的结果形成鲜明对比。在这种均衡随机匹配市场中，稳定匹配的晶格很大，晶格的两个极值点——男性最优稳定匹配（MOSM）和女性最优稳定匹配（WOSM）具有截然不同的性质。在MOSM下，男性妻子的平均军衔是log n，而在WOSM下，男性妻子的平均军衔是n/log n，女性丈夫的平均军衔则相反。因此，Gale-Shapley延迟接受算法中的提议方在平衡市场中具有很大的优势，而我们证明了即使在轻微不平衡的市场中，MOSM和WOSM几乎相同。这揭示了平衡的情况是一个刀刃。我们的证明使用了一种算法，该算法通过男性提出的一系列建议从MOSM计算WOSM。女人通过与丈夫离婚来改善这一点，她触发了一个拒绝链，导致更喜欢的男人向她求婚。该算法适用于随机分析，其中我们表明，大多数拒绝链很可能以向一个不合适的女人求婚而告终。模拟表明，我们的结果甚至适用于小市场。
We analyze large random matching markets with unequal numbers of men and women. Agents have complete preference lists that are uniformly random and independent, and we consider stable matchings under the realized preferences. We find that being on the short side of the market confers a large advantage. We characterize the men's average rank of their wives. For each agent, assign a rank of 1 to the agent's most preferred partner, a rank of 2 to the next most preferred partner and so forth. If there are n men and n+1 women then, we show that with high probability, in any stable matching, the men's average rank of their wives is no more than 3 log n, whereas the women's average rank of their husbands is at least n(3 log n). If there are n men and (1+λ)n women for λ0 then, with high probability, in any stable matching the men's average rank of wives is O(1), whereas the women's average rank of husbands is λ (n). Moreover, we find that in each case, whp, the number of agents who have multiple stable partners is o(n). Thus our results imply a limited scope for manipulation in unbalanced random matching markets for mechanisms that implement a stable match. These results are in stark contrast with previously known results for random matching markets with an equal number of men and women. In such balanced random matching markets, the lattice of stable matches is large, with the two extreme points of the lattice, the men optimal stable match (MOSM) and the women optimal stable match (WOSM) possessing contrasting properties. The men's average rank of their wives is just log n under the MOSM, but as large as n/log n under the WOSM, and the opposite holds for the women's average rank of their husbands. Thus, the proposing side in the Gale-Shapley deferred acceptance algorithm is greatly advantaged in a balanced market, whereas we prove that in markets with even a slight imbalance, the MOSM and WOSM are almost identical. This reveals the balanced case to be a knife edge. Our proof uses an algorithm which calculates the WOSM from the MOSM through a sequence of proposals by men. A woman improves if, by divorcing her husband, she triggers a rejection chain that results in a proposal back to her from a more preferred man. The algorithm lends itself to a stochastic analysis, in which we show that most rejection chains are likely to end in a proposal to an unmatched woman. Simulations show that our results hold even for small markets.