论文标题
在网络上真实稳定的单方面匹配
Truthful and Stable One-sided Matching on Networks
论文作者
论文摘要
社交网络上的机理设计最近是一个热门的研究方向，我们在拍卖和匹配方面看到了许多有趣的结果。与传统设置相比，网络设置的新目标是我们需要设计激励措施，以激励游戏的参与者邀请他们的邻居在网络上加入游戏。这是具有挑战性的，因为他们正在争夺游戏中的事物（例如资源或匹配项）。在单方面的匹配中，尤其是房屋交换中，称为顶级交易周期（TTC）的著名独特，稳定和最佳解决方案无法实现新目标。现有的作品试图在TTC上增加约束以获得激励措施，但它仅在树木中起作用，并且不能保证任何稳定性。在本文中，我们向前迈进，并提出了一种称为休假和共享（LS）的机制，该机制不仅在所有网络中实现了目标，而且还为新设置提供了最稳定的解决方案。就最佳性而言，由于无法在任何网络中实现它，因此我们进行模拟将其与TTC的扩展进行比较。
Mechanism design on social networks is a hot research direction recently, and we have seen many interesting results in auctions and matching. Compared to the traditional settings, the new goal of the network settings is that we need to design incentives to incentivize the participants of the game to invite their neighbors on the network to join the game. This is challenging because they are competing for something (e.g., resources or matches) in the game. In one-sided matching, especially house exchange, the well-known unique truthful, stable and optimal solution called Top Trading Cycle (TTC) cannot achieve the new goal. Existing works have tried to add constraints on TTC to obtain the incentive, but it only works in trees and it does not guarantee any stability. In this paper, we move this forward and propose the first mechanism called Leave and Share (LS) which not only achieves the goal in all networks but also gives the most stable solution in the new settings. In terms of optimality, as it is impossible to achieve it in any network, we conduct simulations to compare it with the extensions of TTC.
