Low-Risk Mechanism for the Kidney-Exchange Game

Abstract. The following game naturally appears in the situations that some service providers benefit from pairwise allocations on a network, such as the kidney exchanges between hospitals. A graph G and a set of m agents {1, 2,...,m} are given. The vertex set is decomposed into a disjoint union Vi so that Vi are the vertices of agent i. The agents first reveal their vertices, and then the mechanism finds a matching on the disclosed vertices. The social welfare function is the size of this matching. Indeed, agent i is interested in maximizing the number of vertices of Vi that are matched. Therefore, agent i may hide a subset of her vertices V ′i ⊆ Vi and reveal Vi \ V ′i, and after the run of the mechanism, privately add a matching on her unmatched vertices, V ′i, into the solution. Hiding the vertices may harm the social welfare, and thus, the mechanism wants to avoid. Ashlagi et al. at EC’10 [1] preset a 2-approximation randomized truthful mechanism for this problem. This is the best known result in this setting with multi-players. However, we note that the variance of the utility of some agents in this mechanism may be as large as Ω(n2), which is not acceptable by real agents. 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 + . Interestingly, we could apply our technique to design a deterministic mech-anism so that, if an agent deviates from the mechanism, she does not gain more than 2dlog2me. We call such a mechanism almost truthful. Indeed, in a practical scenario, an almost truthful mechanism is likely to imply a truthful mechanism. We believe that our approach can be used to design low risk or almost truthful mechanisms for other problems.