{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:25:08Z","timestamp":1750220708834,"version":"3.41.0"},"reference-count":20,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2020,5,3]],"date-time":"2020-05-03T00:00:00Z","timestamp":1588464000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme","award":["740435"],"award-info":[{"award-number":["740435"]}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"crossref","award":["1357\/16"],"award-info":[{"award-number":["1357\/16"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Simons Society Junior fellowship"},{"name":"NSF CAREER","award":["CCF-1844887"],"award-info":[{"award-number":["CCF-1844887"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2020,5,31]]},"abstract":"<jats:p>A recurring theme in recent computer science literature is that proper design of signaling schemes is a crucial aspect of effective mechanisms aiming to optimize social welfare or revenue. One of the research endeavors of this line of work is understanding the algorithmic and computational complexity of designing efficient signaling schemes. In reality, however, information is typically not held by a central authority but is distributed among multiple sources (third-party \u201cmediators\u201d), a fact that dramatically changes the strategic and combinatorial nature of the signaling problem.<\/jats:p>\n          <jats:p>\n            In this article, we introduce\n            <jats:italic>distributed signaling games<\/jats:italic>\n            , 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 \u201ccentralized\u201d counterpart.\n          <\/jats:p>\n          <jats:p>\n            In the context of non-cooperative games, the outcome generated by the mediators\u2019 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\u2019s value and show that it possesses some interesting properties; in particular, it always admits a pure Nash equilibrium, and it never decreases the revenue of the auctioneer (relative to his\n            <jats:italic>a priori<\/jats:italic>\n            revenue when there are no mediators).\n          <\/jats:p>","DOI":"10.1145\/3381529","type":"journal-article","created":{"date-parts":[[2020,5,4]],"date-time":"2020-05-04T22:58:33Z","timestamp":1588633113000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Distributed Signaling Games"],"prefix":"10.1145","volume":"8","author":[{"given":"Moran","family":"Feldman","sequence":"first","affiliation":[{"name":"Microsoft Research, Israel, and University of Haifa"}]},{"given":"Moshe","family":"Tennenholtz","sequence":"additional","affiliation":[{"name":"Microsoft Research, Israel, and Technion-IIT"}]},{"given":"Omri","family":"Weinstein","sequence":"additional","affiliation":[{"name":"Microsoft Research, Israel, and Columbia University"}]}],"member":"320","published-online":{"date-parts":[[2020,5,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1176343654"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the Neural Information Processing Systems Conference (NeurIPS\u201918)","author":"Ben-Porat Omer","year":"2018","unstructured":"Omer Ben-Porat and Moshe Tennenholtz . 2018 . A game-theoretic approach to recommendation systems with strategic content providers . In Proceedings of the Neural Information Processing Systems Conference (NeurIPS\u201918) . Curran Associates, Inc., 1110--1120. Omer Ben-Porat and Moshe Tennenholtz. 2018. A game-theoretic approach to recommendation systems with strategic content providers. In Proceedings of the Neural Information Processing Systems Conference (NeurIPS\u201918). Curran Associates, Inc., 1110--1120."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2229012.2229033"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2668033"},{"key":"e_1_2_1_5_1","volume-title":"Shaddin Dughmi, and Shang-Hua Teng.","author":"Cheng Yu","year":"2014","unstructured":"Yu Cheng , Ho Yee Cheung , Shaddin Dughmi, and Shang-Hua Teng. 2014 . Signaling in Quasipolynomial time. (2014). arxiv:1410.3033 http:\/\/arxiv.org\/abs\/1410.3033. Yu Cheng, Ho Yee Cheung, Shaddin Dughmi, and Shang-Hua Teng. 2014. Signaling in Quasipolynomial time. (2014). arxiv:1410.3033 http:\/\/arxiv.org\/abs\/1410.3033."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.45"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.99"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594564"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77105-0_32"},{"volume-title":"Reasoning About Knowledge","author":"Fagin Ronald","key":"e_1_2_1_10_1","unstructured":"Ronald Fagin , Joseph Y. Halpern , Yoram Moses , and Moshe Vardi . 1995. Reasoning About Knowledge . MIT Press , Cambridge, MA . Ronald Fagin, Joseph Y. Halpern, Yoram Moses, and Moshe Vardi. 1995. Reasoning About Knowledge. MIT Press, Cambridge, MA."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77105-0_63"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI\u201913). AAAI Press\/International Joint Conferences on Artificial Intelligence","author":"Guo Mingyu","year":"2013","unstructured":"Mingyu Guo and Argyrios Deligkas . 2013 . Revenue maximization via hiding item attributes . In Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI\u201913). AAAI Press\/International Joint Conferences on Artificial Intelligence , Menlo Park, CA, 157--163. Mingyu Guo and Argyrios Deligkas. 2013. Revenue maximization via hiding item attributes. In Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI\u201913). AAAI Press\/International Joint Conferences on Artificial Intelligence, Menlo Park, CA, 157--163."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02392825"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1120.1137"},{"volume-title":"Economic Theory of Teams","author":"Marschak Jacob","key":"e_1_2_1_15_1","unstructured":"Jacob Marschak and Roy Radner . 1972. Economic Theory of Teams . Yale University Press, New Haven , CT. Jacob Marschak and Roy Radner. 1972. Economic Theory of Teams. Yale University Press, New Haven, CT."},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the IEEE Symposium on Security and Privacy (SP\u201912)","author":"Jonathan","year":"2012","unstructured":"Jonathan R. Mayer and John C. Mitchell. 2012. Third-party web tracking: Policy and technology . In Proceedings of the IEEE Symposium on Security and Privacy (SP\u201912) . IEEE Computer Society, Los Alamitos, CA, 413--427. DOI:https:\/\/doi.org\/10.1109\/SP. 2012 .47 10.1109\/SP.2012.47 Jonathan R. Mayer and John C. Mitchell. 2012. Third-party web tracking: Policy and technology. In Proceedings of the IEEE Symposium on Security and Privacy (SP\u201912). IEEE Computer Society, Los Alamitos, CA, 413--427. DOI:https:\/\/doi.org\/10.1109\/SP.2012.47"},{"volume-title":"Solution-Based Congestion Games","author":"Monderer Dov","key":"e_1_2_1_17_1","unstructured":"Dov Monderer . 2006. Solution-Based Congestion Games . Springer Japan , Tokyo , 397--409. Dov Monderer. 2006. Solution-Based Congestion Games. Springer Japan, Tokyo, 397--409."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1538902.1538907"},{"key":"e_1_2_1_19_1","first-page":"307","article-title":"A value for n-person games","volume":"2","author":"Shapley Lloyd S.","year":"1953","unstructured":"Lloyd S. Shapley . 1953 . A value for n-person games . Contrib. Theory Games 2 (1953), 307 -- 317 . Lloyd S. Shapley. 1953. A value for n-person games. Contrib. Theory Games 2 (1953), 307--317.","journal-title":"Contrib. Theory Games"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2501040.2501980"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3381529","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3381529","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:33:07Z","timestamp":1750199587000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3381529"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,5,3]]},"references-count":20,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,5,31]]}},"alternative-id":["10.1145\/3381529"],"URL":"https:\/\/doi.org\/10.1145\/3381529","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"type":"print","value":"2167-8375"},{"type":"electronic","value":"2167-8383"}],"subject":[],"published":{"date-parts":[[2020,5,3]]},"assertion":[{"value":"2018-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-05-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}