An adaptive sponsored search mechanism δ-gain truthful in valuation, time, and budget

Rica Gonen, Elan Pavlov

نتاج البحث: فصل من :كتاب / تقرير / مؤتمرمنشور من مؤتمرمراجعة النظراء


This paper presents an online sponsored search auction that motivates advertisers to report their true budget, arrival time, departure time, and value per click. The auction is based on a modified Multi-Armed Bandit (MAB) mechanism that allows for advertisers who arrive and depart in an online fashion, have a value per click, and are budget constrained. In tackling the problem of truthful budget, arrival and departure times, it turns out that it is not possible to achieve truthfulness in the classical sense (which we show in a companion paper). As such, we define a new concept called δ-gain. δ-gain bounds the utility a player can gain by lying as opposed to his utility when telling the truth. Building on the 6-gain concept we define another new concept called relative e-gain, which bounds the relative ratio of the gain a player can achieve by lying with respect to his true utility. We argue that for many practical applications if the δ-gain and or the relative ε-gain are small, then players will not invest time and effort in making strategic choices but will truthtell as a default strategy. These concepts capture the essence of dominant strategy mechanisms as they lead the advertiser to choose truthtelling over other strategies. In order to achieve δ-gain truthful mechanism this paper also presents a new payment scheme, Time series Truthful Payment Scheme (TTPS), for an online budget-constrained auction mechanism. The payment scheme is a generalization of the VCG principles for an online scheduling environment with budgeted players. Using the concepts of δ-gain truthful we present the only known budgetconstrained sponsored search auction with truthful guarantees on budget, arrivals, departures, and valuations. Previous works that deal with advertiser budgets only deal with the non-strategic case.

اللغة الأصليةالإنجليزيّة
عنوان منشور المضيفInternet and Network Economics - Third International Workshop, WINE 2007, Proceedings
ناشرSpringer Verlag
عدد الصفحات6
رقم المعيار الدولي للكتب (المطبوع)9783540771043
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 2007
منشور خارجيًانعم
الحدث3rd International Workshop on Internet and Network Economics, WINE 2007 - San Diego, CA, الولايات المتّحدة
المدة: ١٢ ديسمبر ٢٠٠٧١٤ ديسمبر ٢٠٠٧

سلسلة المنشورات

الاسمLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
مستوى الصوت4858 LNCS
رقم المعيار الدولي للدوريات (المطبوع)0302-9743
رقم المعيار الدولي للدوريات (الإلكتروني)1611-3349


!!Conference3rd International Workshop on Internet and Network Economics, WINE 2007
الدولة/الإقليمالولايات المتّحدة
المدينةSan Diego, CA


أدرس بدقة موضوعات البحث “An adaptive sponsored search mechanism δ-gain truthful in valuation, time, and budget'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا