A Truthful Cardinal Mechanism for One-Sided Matching
A Truthful Cardinal Mechanism for One-Sided Matching
复制标题
一种真实的单边匹配基数机制
DOI：
10.1137/1.9781611975994.129
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Hartline, Jason D.
中科院分区：
文献类型：
--
作者：
Abebe, Rediet;Cole, Richard;Gkatzelis, Vasilis;Hartline, Jason D.
我们回顾了一个研究得很好的问题，即为单向匹配市场设计机制，其中一组代理需要与一组非异质项目匹配。每个代理对于每个项目j都有一个值νi，j，并且这些值是私人信息，如果这样做导致了理想的结果，代理可能会错误报告。要确保代理人没有误报的动机，需要仔细设计匹配机制，而文献中提出的机制通过只得出代理人的顺序偏好，即他们对物品从最喜欢到最不喜欢的排名来缓解这个问题。然而，这些机制的效率保证只是建立在忽视基本价值的薄弱措施上。在本文中，我们通过引入一种机制来实现更强的性能保证，该机制真实地得出ν的全部基数偏好，即所有的Agents i，j值。我们使用要求更高的纳什协商解作为基准来评估该机制的性能，并证明了该机制的性能显著优于所有的有序机制(即使是非真实的)。为了证明我们的近似界，我们还研究了匹配市场背景下纳什讨价还价解的总体单调性，给出了独立的上界和下界。
We revisit the well-studied problem of designing mechanisms for one-sided matching markets, where a set ofnagents needs to be matched to a set ofnheterogeneous items. Each agentihas a valueνi,jfor each itemj, and these values are private information that the agents may misreport if doing so leads to a preferred outcome. Ensuring that the agents have no incentive to misreport requires a careful design of the matching mechanism, and mechanisms proposed in the literature mitigate this issue by eliciting only theordinalpreferences of the agents, i.e., their ranking of the items from most to least preferred. However, the efficiency guarantees of these mechanisms are based only on weak measures that are oblivious to the underlying values. In this paper we achieve stronger performance guarantees by introducing a mechanism that truthfully elicits the fullcardinalpreferences of the agents, i.e., all of theνi,jvalues. We evaluate the performance of this mechanism using the much more demanding Nash bargaining solution as a benchmark, and we prove that our mechanism significantly outperforms all ordinal mechanisms (even non-truthful ones). To prove our approximation bounds, we also study the population monotonicity of the Nash bargaining solution in the context of matching markets, providing both upper and lower bounds which are of independent interest.
登录
查看更多内容
匹配市场中的计算均衡
DOI：
10.1145/3033274.3085150
发表时间：
2017
期刊：
Proceedings of the 2017 ACM Conference on Economics and Computation
影响因子：
--
作者：
S. Alaei;Pooya Jalaly;É. Tardos
通讯作者：
É. Tardos
与可变数量的代理人讨价还价的公理理论
影响因子：
2.5
作者：
W. Thomson;T. Lensberg
通讯作者：
T. Lensberg
固定数量商品或代理的多项式时间内的市场均衡
DOI：
--
发表时间：
2008
期刊：
2008 49th Annual IEEE Symposium on Foundations of Computer Science
影响因子：
--
作者：
Nikhil R. Devanur;R. Kannan
通讯作者：
R. Kannan
DOI：
10.1007/978-3-319-71924-5_18
发表时间：
2017
期刊：
SIGecom Exch.
影响因子：
--
作者：
Nicole Immorlica;Brendan Lucier;Glen Weyl;Joshua Mollner
通讯作者：
Joshua Mollner
DOI：
--
发表时间：
2017
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
J. Garg;M. Hoefer;K. Mehlhorn
通讯作者：
K. Mehlhorn