Brief announcement: An incentive-compatible multi-armed bandit mechanism

Rica Gonen, Elan Pavlov

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

תקציר

This paper presents a truthful sponsored search auction based on an incentive-compatible multi-armed bandit mechanism. The mechanism described combines several desirable traits. The mechanism gives advertisers the incentive to report their true bid, learns the click-through rate for advertisements, allows for slots with different quality, and loses the minimum welfare during the sampling process. The underlying generalization of the multi-armed bandit mechanism addresses the interplay between exploration and exploitation in an online setting that is truthful in high probability while allowing for slots of different quality. As the mechanism progresses the algorithm more closely approximates the hidden variables (click-though rates) in order to allocate advertising slots to the best advertisements. The resulting mechanism obtains the optimal welfare apart from a tightly bounded loss of welfare caused by the bandit sampling process. Of independent interest, in the field of economics it has long been recognized that preference elicitation is difficult to achieve, mainly as people are unaware of how much happiness a particular good will bring to them. In this paper we alleviate this problem somewhat by introducing a valuation-discovery process to the mechanism which results in a preference-elicitation mechanism for advertisers and search engines.

שפה מקוריתאנגלית
כותר פרסום המארחPODC'07
כותר משנה של פרסום המארחProceedings of the 26th Annual ACM Symposium on Principles of Distributed Computing
עמודים362-363
מספר עמודים2
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2007
פורסם באופן חיצוניכן
אירועPODC'07: 26th Annual ACM Symposium on Principles of Distributed Computing - Portland, OR, ארצות הברית
משך הזמן: 12 אוג׳ 200715 אוג׳ 2007

סדרות פרסומים

שםProceedings of the Annual ACM Symposium on Principles of Distributed Computing

כנס

כנסPODC'07: 26th Annual ACM Symposium on Principles of Distributed Computing
מדינה/אזורארצות הברית
עירPortland, OR
תקופה12/08/0715/08/07

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Brief announcement: An incentive-compatible multi-armed bandit mechanism'. יחד הם יוצרים טביעת אצבע ייחודית.

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