In this paper, we consider the pairwise kidney exchange game. Ashlagi et al. present a 2-approximation randomized truthful mechanism for this problem. We note that the variance of the utility of an agent in this mechanism may be as large as Ω(n~2), which is not desirable in a real application. Here, 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 + ε. Later, we derandomize our mechanism and provide a deterministic mechanism such that, if an agent deviates from the mechanism, she does not gain more than 2[log_2 m].
展开▼
