A bounded-risk mechanism for the kidney exchange game

Hossein Esfandiari, Guy Kortsarz

פרסום מחקרי: פרק בספר / בדוח / בכנספרסום בספר כנסביקורת עמיתים

תקציר

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 אפר׳ 201615 אפר׳ 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/1615/04/16

הערה ביבליוגרפית

Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2016.

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'A bounded-risk mechanism for the kidney exchange game'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי