This paper studies one-sided matching with initial endowments and the social connections between participants are specifically considered (their social network). Different from the traditional setting, the matching starts with a group of initial participants, and the others need their invitation to join the matching game. Thus, the incentive compatibility (IC) notion here considers both reporting preferences and inviting others via their social connections. This is challenging because inviters and invitees might compete in the game. Besides IC, stability and optimality are two properties extensively studied in matching, but they both are incompatible with the new IC. In the new setting, compatible stability has been discussed, but no discussion about compatible optimality yet. We complete this and prove the theoretical boundaries regarding both stability and optimality in the new setting. We then propose a mechanism called Connected Trading Cycles to satisfy all the desirable properties for the first time. Unlike the previous solutions that add restrictions on participants' matching choices to achieve IC, we allow participants to choose anyone in the game, which in principle improves everyone's satisfiability in the matching. Finally, we give the first characterization of IC in the network setting to facilitate IC mechanism design.
翻译:本文研究带有初始财产的单边匹配,并特别考虑参与者之间的社交联系(其社交网络)。不同于传统框架,匹配从一组初始参与者开始,而其他人需要邀请才能加入匹配游戏。因此,激励兼容性(IC)概念在此处考虑了报告偏好和通过社交联系邀请他人的因素。这是具有挑战性的,因为邀请人和被邀请人可能在游戏中竞争。除IC外,稳定性和最优性是匹配中广泛研究的两个属性,但它们都与新IC不兼容。在新框架中,已经讨论了兼容的稳定性,但还没有关于兼容的最优性的讨论。我们完成了这一工作,并首次证明了关于稳定和最优性的理论边界。然后,我们提出了一种名为“联通交易周期”的机制,以满足所有理想性质。与以前的解决方案不同,以增加参与者的匹配选择限制来实现IC相比,我们允许参与者选择游戏中的任何人,这原则上可以提高所有人的满意度。最后,我们提供了网络设置中IC的第一个特征描述,以促进IC机制设计。