An Improved 2-Agent Kidney Exchange Mechanism

Ioannis Caragiannis, Aris Filos-Ratsikas, Ariel D. Procaccia

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

We study a mechanism design version of matching computation in graphs that models the game played by hospitals participating in pairwise kidney exchange programs. We present a new randomized matching mechanism for two agents which is truthful in expectation and has an approximation ratio of 3/2 to the maximum cardinality matching. This is an improvement over a recent upper bound of 2 [Ashlagi et al., EC 2010] and, furthermore, our mechanism beats for the first time the lower bound on the approximation ratio of deterministic truthful mechanisms. We complement our positive result with new lower bounds. Among other statements, we prove that the weaker incentive compatibility property of truthfulness in expectation in our mechanism is necessary; universally truthful mechanisms that have an inclusion-maximality property have an approximation ratio of at least 2.
Original languageEnglish
Title of host publicationInternet and Network Economics - 7th International Workshop, WINE 2011, Singapore, December 11-14, 2011, Proceedings
EditorsNing Chen, Edith Elkind, Elias Koutsoupias
Place of PublicationBerlin, Heidelberg
PublisherSpringer Berlin Heidelberg
Number of pages12
ISBN (Electronic)978-3-642-25510-6
ISBN (Print)978-3-642-25509-0
Publication statusPublished - 30 Nov 2011
EventThe 7th International Workshop on Internet & Network Economics - , Singapore
Duration: 11 Dec 201114 Dec 2011
Conference number: 7

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Berlin, Heidelberg
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


WorkshopThe 7th International Workshop on Internet & Network Economics
Abbreviated titleWINE 2011


Dive into the research topics of 'An Improved 2-Agent Kidney Exchange Mechanism'. Together they form a unique fingerprint.

Cite this