Journal article icon

Journal article

An improved 2-agent kidney exchange mechanism

Abstract:

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., 2010 [2]) and, furthermore, our mechanism beats for the first time the lower bound on the app...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed

Actions


Access Document


Publisher copy:
10.1016/j.tcs.2015.04.013

Authors


Caragiannis, I More by this author
More by this author
Department:
Oxford, MPLS, Computer Science
Procaccia, AD More by this author
Publisher:
Elsevier B.V. Publisher's website
Journal:
Theoretical Computer Science Journal website
Volume:
589
Pages:
53-60
Publication date:
2015-04-20
Acceptance date:
2015-04-10
DOI:
ISSN:
0304-3975
Pubs id:
pubs:578432
URN:
uri:9decd942-dffa-4883-82ed-6508c717ab65
UUID:
uuid:9decd942-dffa-4883-82ed-6508c717ab65
Local pid:
pubs:578432
Keywords:

Terms of use


Metrics



If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP