A bounded-risk mechanism for the kidney exchange game.

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 Ω ( 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 + ϵ . 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 ⌈ log 2 m ⌉ , where m is the number of players. [ABSTRACT FROM AUTHOR]