Brief announcement: New mechanisms for pairwise kidney exchange

Hossein Efsandiari, Guy Kortsarz

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

Abstract

In this paper, we consider the pairwise kidney exchange game. Ashlagi et al. [1] 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 Ω(n2), 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[log2 m].

Original languageEnglish (US)
Title of host publicationAlgorithmic Game Theory - 8th International Symposium, SAGT 2015
EditorsMartin Hoefer, Martin Hoefer
PublisherSpringer Verlag
Pages303-304
Number of pages2
ISBN (Print)9783662484326
DOIs
StatePublished - 2015
Event8th International Symposium on Algorithmic Game Theory, SAGT 2015 - Saarbrucken, Germany
Duration: Sep 28 2015Sep 30 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9347
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other8th International Symposium on Algorithmic Game Theory, SAGT 2015
CountryGermany
CitySaarbrucken
Period9/28/159/30/15

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Brief announcement: New mechanisms for pairwise kidney exchange'. Together they form a unique fingerprint.

Cite this