论文标题
基于公用事业的沟通要求，在大型市场中稳定匹配
Utility-Based Communication Requirements for Stable Matching in Large Markets
论文作者
论文摘要
沟通复杂性文献的结果表明，稳定的匹配需要交流：一个人在不访问市场代理商私下私有持有的所有顺序优先信息的情况下，无法找到或验证稳定的匹配。惯例说，这些结果表明，稳定的匹配机制对于输入偏好中的少数标记的不准确性也不强大。在实践中，这些结果表明，如果希望保证结果稳定，则必须经过时间密集型的过程，以准确地对每个潜在的匹配候选者进行排名。因此，在大型市场中，稳定匹配的沟通要求可能不切实际。 考虑到这一结果，一个自然的问题是，市场上的一些高阶结构是否可以表明哪些大型市场具有更陡峭的沟通要求。在本文中，我们在代理具有基于公用事业的偏好概念的制度中进行了这样的分析。我们考虑一个动态模型，其中代理只能访问其实用程序的近似值，该效用满足了通用乘法误差的限制。我们从理论计算机科学文献中应用了有限度量空间的低衰减嵌入的理论科学文献，以了解大型市场中稳定匹配的结构属性的沟通要求。我们的结果表明，对于一个广泛的市场家庭，错误限制的速度可能不会超过$ n^2 \ log（n）$，同时在限制下对稳定匹配机制的行为保持确定性保证。我们还表明，只要在市场的潜在拓扑复杂性中，最大的差异增长就可以做出更强的概率保证。
Results from the communication complexity literature have demonstrated that stable matching requires communication: one cannot find or verify a stable match without having access to essentially all of the ordinal preference information held privately by the agents in the market. Stated differently, these results show that stable matching mechanisms are not robust to even a small number of labeled inaccuracies in the input preferences. In practice, these results indicate that agents must go through the time-intensive process of accurately ranking each and every potential match candidate if they wish for the resulting match to be guaranteedly stable. Thus, in large markets, communication requirements for stable matching may be impractically high. A natural question to ask, given this result, is whether some higher-order structure in the market can indicate which large markets have steeper communication requirements. In this paper, we perform such an analysis in a regime where agents have a utility-based notion of preference. We consider a dynamic model where agents only have access to an approximation of their utility that satisfies a universal multiplicative error bound. We apply guarantees from the theoretical computer science literature on low-distortion embeddings of finite metric spaces to understand the communication requirements of stable matching in large markets in terms of their structural properties. Our results show that for a broad family of markets, the error bound may not grow faster than $n^2\log(n)$ while maintaining a deterministic guarantee on the behavior of stable matching mechanisms in the limit. We also show that a stronger probabilistic guarantee may be made so long as the bound grows at most logarithmically in the underlying topological complexity of the market.
