Distributed signaling games

Moran Feldman, Moshe Tennenholtz, Omri Weinstein

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


The study of the algorithmic and computational complexity of designing efficient signaling schemes for mechanisms aiming to optimize social welfare or revenue is a recurring theme in recent computer science literature. In reality, however, information is typically not held by a central authority, but is distributed among multiple sources (third-party "mediators"), a fact that dramatically changes the strategic and combinatorial nature of the signaling problem. In this paper we introduce distributed signaling games, while using display advertising as a canonical example for introducing this foundational framework. A distributed signaling game may be a pure coordination game (i.e., a distributed optimization task), or a non-cooperative game. In the context of pure coordination games, we show a wide gap between the computational complexity of the centralized and distributed signaling problems, proving that distributed coordination on revenue-optimal signaling is a much harder problem than its "centralized" counterpart. In the context of non-cooperative games, the outcome generated by the mediators' signals may have different value to each. The reason for that is typically the desire of the auctioneer to align the incentives of the mediators with his own by a compensation relative to the marginal benefit from their signals. We design a mechanism for this problem via a novel application of Shapley's value, and show that it possesses a few interesting economical properties.

اللغة الأصليةالإنجليزيّة
عنوان منشور المضيف24th Annual European Symposium on Algorithms, ESA 2016
المحررونChristos Zaroliagis, Piotr Sankowski
ناشرSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
رقم المعيار الدولي للكتب (الإلكتروني)9783959770156
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 1 أغسطس 2016
الحدث24th Annual European Symposium on Algorithms, ESA 2016 - Aarhus, الدنمارك
المدة: ٢٢ أغسطس ٢٠١٦٢٤ أغسطس ٢٠١٦

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

الاسمLeibniz International Proceedings in Informatics, LIPIcs
مستوى الصوت57
رقم المعيار الدولي للدوريات (المطبوع)1868-8969


!!Conference24th Annual European Symposium on Algorithms, ESA 2016

ملاحظة ببليوغرافية

Publisher Copyright:
© Moran Feldman, Moshe Tennenholtz, and Omri Weinstein.


أدرس بدقة موضوعات البحث “Distributed signaling games'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا