标题： 基于效用的大型市场中稳定匹配的通信需求 显示英文标题

标题： 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.