Incentives in Large Random Two-Sided Markets
Incentives in Large Random Two-Sided Markets
复制标题
大型随机双边市场的激励
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Mohammad Mahdian
中科院分区：
文献类型：
--
作者：
Nicole Immorlica;Mohammad Mahdian
许多中心化的双边市场通过运行稳定的匹配算法来形成参与者之间的匹配。一个众所周知的事实是，没有一种基于稳定匹配算法的匹配机制能够保证真实性作为参与者的优势策略。然而，我们表明，在一个概率设置中，市场一侧的偏好列表仅由一个常数（与市场规模无关）数量的条目组成，每个条目都来自任意分布，拥有多个稳定合作伙伴的参与者数量微乎其微。这证明（并推广）了Roth和Peranson[1999]的一个猜想。作为这个结果的推论，我们表明，在高概率下，当其他参与者都是诚实的时候，诚实策略是随机参与者的最佳对策。本文还分析了延期接受稳定匹配对策的均衡问题。我们证明了具有完全信息的博弈具有一个均衡，在这个均衡中，在期望中，策略的（1−0(1)）部分是真实的。在不完全信息博弈的更现实的设置中，我们将证明，对于均匀随机偏好，真实策略集形成(1+o(1))-近似贝叶斯-纳什均衡。我们的研究结果在许多实际环境中具有启示意义，并受到Roth和Peranson[1999]关于国家住院医师匹配计划的工作的启发。
Many centralized two-sided markets form a matching between participants by running a stable matching algorithm. It is a well-known fact that no matching mechanism based on a stable matching algorithm can guarantee truthfulness as a dominant strategy for participants. However, we show that in a probabilistic setting where the preference lists on one side of the market are composed of only a constant (independent of the size of the market) number of entries, each drawn from an arbitrary distribution, the number of participants that have more than one stable partner is vanishingly small. This proves (and generalizes) a conjecture of Roth and Peranson [1999]. As a corollary of this result, we show that, with high probability, the truthful strategy is the best response for a random player when the other players are truthful. We also analyze equilibria of the deferred acceptance stable matching game. We show that the game with complete information has an equilibrium in which, in expectation, a (1−o(1)) fraction of the strategies are truthful. In the more realistic setting of a game of incomplete information, we will show that the set of truthful stratiegs form a (1+o(1))-approximate Bayesian-Nash equilibrium for uniformly random preferences. Our results have implications in many practical settings and are inspired by the work of Roth and Peranson [1999] on the National Residency Matching Program.