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.
翻译:社交网络上的机制设计是最近一个热门的研究方向,我们在拍卖和匹配中看到了许多有趣的结果。与传统环境相比,网络设置的新目标是我们需要设计激励游戏参与者的激励措施,邀请网络上的邻居加入游戏。这具有挑战性,因为他们正在竞争游戏中的某些东西(如资源或匹配),在单面匹配中,特别是房屋交换中,众所周知的独特真实、稳定和最佳的解决方案,即所谓的顶层交易周期(TTC)无法实现新目标。现有的工程试图增加对TC的制约,以获得奖励,但仅在树上运作,无法保证任何稳定性。在本文中,我们向前推进,提出第一个机制,即休假和共享(LS),不仅在所有网络中实现目标,而且在新环境中提供最稳定的解决方案。在最佳性方面,由于在任何网络中都不可能实现,我们进行模拟,以将其与TTC的扩展相比较。