תקציר
In this paper we consider the pairwise kidney exchange game. This game naturally appears in situations that some service providers benefit from pairwise allocations on a network, such as the kidney exchanges between hospitals. Ashlagi et al. [1] present a 2-approximation randomized truthful mechanism for this problem. This is the best known result in this setting with multiple players. However, 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. 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 + ε. As a side result, we apply our technique to design a deterministic mechanism such that, if an agent deviates from the mechanism, she does not gain more than 2┌log2 m┐.
שפה מקורית | אנגלית |
---|---|
כותר פרסום המארח | LATIN 2016 |
כותר משנה של פרסום המארח | Theoretical Informatics - 12th Latin American Symposium, Proceedings |
עורכים | Gonzalo Navarro, Evangelos Kranakis, Edgar Chávez |
מוציא לאור | Springer Verlag |
עמודים | 416-428 |
מספר עמודים | 13 |
מסת"ב (מודפס) | 9783662495285 |
מזהי עצם דיגיטלי (DOIs) | |
סטטוס פרסום | פורסם - 2016 |
פורסם באופן חיצוני | כן |
אירוע | 12th Latin American Symposium on Theoretical Informatics, LATIN 2016 - Ensenada, מקסיקו משך הזמן: 11 אפר׳ 2016 → 15 אפר׳ 2016 |
סדרות פרסומים
שם | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
כרך | 9644 |
ISSN (מודפס) | 0302-9743 |
ISSN (אלקטרוני) | 1611-3349 |
כנס
כנס | 12th Latin American Symposium on Theoretical Informatics, LATIN 2016 |
---|---|
מדינה/אזור | מקסיקו |
עיר | Ensenada |
תקופה | 11/04/16 → 15/04/16 |
הערה ביבליוגרפית
Publisher Copyright:© Springer-Verlag Berlin Heidelberg 2016.