A bounded-risk mechanism for the kidney exchange game

作者：Esfandiari Hossein^*; Kortsarz Guy

来源：Discrete Applied Mathematics, 2018, 243: 46-53.

DOI：10.1016/j.dam.2017.12.029

• Kidney exchange game
• Graph matching
• Mechanism design
• Low risk mechanism
• Almost truthful

In this paper, we introduce and study the notion of low risk mechanisms. Intuitively, we say a mechanism is a low risk mechanism if the randomization of the mechanism does not affect the utility of agents by a lot. Specifically, we desire to design mechanisms in which the variances of the utility of agents are small. Inspired by this work, later, Procaccia et al. (0000) study the approximation-variance tradeoffs in mechanism design.
In particular, here we present a low risk mechanism for the pairwise kidney exchange game. This game naturally appears in situations that some service providers benefit from pairwise allocations on a network, such as the kidney exchanges between hospitals. Ashlagi et al. (2013) present a 2-approximation randomized truthful mechanism for this problem. This is the best-known result in this setting with multiple players. However, we note that the variance of the utility of an agent in this mechanism may be as large as Omega(n(2)), where n is the number of vertices. Indeed, this is not desirable in a real application. In this paper, we resolve this issue by providing a 2-approximation randomized truthful mechanism in which the variance of the utility of each agent is at most 2 + epsilon.
As a side result, we apply our technique to design a deterministic mechanism such that, if an agent deviates from the mechanism, she does not gain more than 2 left perpendicular log(2)m right perpendicular, where m is the number of players.

• 出版日期2018-7-10
• 单位rutgers