Incentive Compatible Mulit-Unit Combinatorial Auctions: A Primal Dual Approach

Niv Buchbinder, Rica Gonen

פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים


We study multi-unit combinatorial auctions with multi-minded buyers. We provide two deterministic, efficient maximizing, incentive compatible mechanisms that improve upon the known algorithms for the problem (Bartal et al., Proceedings of the 9th Conference on Theoretical Aspects of Rationality and Knowledge TARK IX, pp. 72–87, 2003). The first mechanism is an online mechanism for a setting in which buyers arrive one-by-one in an online fashion. We then design an offline mechanism with better performance guarantees based on the online mechanism. We complement the results by lower bounds that show that the performance of our mechanisms is close to optimal. The results are based on an online primal-dual approach that was used extensively recently and reveals the underlying structure of the problem.

שפה מקוריתאנגלית
עמודים (מ-עד)167-190
מספר עמודים24
כתב עתAlgorithmica
מספר גיליון1
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 1 מאי 2015

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

Publisher Copyright:
© 2013, Springer Science+Business Media New York.

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Incentive Compatible Mulit-Unit Combinatorial Auctions: A Primal Dual Approach'. יחד הם יוצרים טביעת אצבע ייחודית.

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