{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,14]],"date-time":"2025-11-14T21:30:52Z","timestamp":1763155852856,"version":"3.41.0"},"reference-count":14,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2016,1,13]],"date-time":"2016-01-13T00:00:00Z","timestamp":1452643200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Microsoft Research, Herzliya Israel"},{"name":"ERC Starting","award":["335288-OptApprox"],"award-info":[{"award-number":["335288-OptApprox"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2016,2,3]]},"abstract":"<jats:p>\n            We consider the problem of designing mechanisms that interact with strategic agents through\n            <jats:italic>strategic<\/jats:italic>\n            intermediaries (or mediators), and investigate the cost to society due to the mediators\u2019 strategic behavior. Selfish agents with private information are each associated with exactly one strategic mediator, and can interact with the mechanism exclusively through that mediator. Each mediator aims to optimize the combined utility of\n            <jats:italic>his<\/jats:italic>\n            agents, while the mechanism aims to optimize the combined utility of\n            <jats:italic>all<\/jats:italic>\n            agents. We focus on the problem of facility location on a metric induced by a publicly known tree. With nonstrategic mediators, there is a dominant strategy mechanism that is optimal. We show that when both agents and mediators act strategically, there is no dominant strategy mechanism that achieves\n            <jats:italic>any<\/jats:italic>\n            approximation. We, thus, slightly relax the incentive constraints, and define the notion of a\n            <jats:italic>two-sided incentive compatible<\/jats:italic>\n            mechanism. We show that the 3-competitive\n            <jats:italic>deterministic<\/jats:italic>\n            mechanism suggested by Procaccia and Tennenholtz [2013] and Dekel et al. [2010] for lines extends naturally to trees, and is still 3-competitive as well as two-sided incentive compatible. This is essentially the best possible (follows from Dekel et al. [2010] and Procaccia and Tennenholtz [2013]). We then show that by allowing randomization one can construct a 2-competitive\n            <jats:italic>randomized<\/jats:italic>\n            mechanism that is two-sided incentive compatible, and this is also essentially tight. This result also reduces a gap left in the work of Procaccia and Tennenholtz [2013] and Lu et al. [2009] for the problem of designing strategy-proof mechanisms for weighted agents with no mediators on a line. We also investigate a generalization of the preceding setting where there are multiple levels of mediators.\n          <\/jats:p>","DOI":"10.1145\/2841227","type":"journal-article","created":{"date-parts":[[2016,1,14]],"date-time":"2016-01-14T02:18:38Z","timestamp":1452737918000},"page":"1-48","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Mechanism Design with Strategic Mediators"],"prefix":"10.1145","volume":"4","author":[{"given":"Moshe","family":"Babaioff","sequence":"first","affiliation":[{"name":"Microsoft Research, Herzliya, Israel"}]},{"given":"Moran","family":"Feldman","sequence":"additional","affiliation":[{"name":"School of Computer and Communication Sciences, EPFL"}]},{"given":"Moshe","family":"Tennenholtz","sequence":"additional","affiliation":[{"name":"Microsoft Research"}]}],"member":"320","published-online":{"date-parts":[[2016,1,13]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_2_1_1_1","DOI":"10.1287\/moor.1100.0457"},{"doi-asserted-by":"publisher","key":"e_1_2_1_2_1","DOI":"10.1016\/j.geb.2008.11.005"},{"doi-asserted-by":"publisher","key":"e_1_2_1_3_1","DOI":"10.1145\/2688073.2688081"},{"doi-asserted-by":"publisher","key":"e_1_2_1_4_1","DOI":"10.1016\/j.jcss.2010.03.003"},{"doi-asserted-by":"publisher","key":"e_1_2_1_5_1","DOI":"10.1145\/1807342.1807346"},{"doi-asserted-by":"publisher","key":"e_1_2_1_6_1","DOI":"10.1515\/crll.1869.70.185"},{"volume-title":"Bidding clubs in first-price auctions","author":"Leyton-Brown Kevin","unstructured":"Kevin Leyton-Brown , Yoav Shoham , and Moshe Tennenholtz . 2002. Bidding clubs in first-price auctions . In AAAI\/IAAI. AAAI Press\/The MIT Press , 373--378. Kevin Leyton-Brown, Yoav Shoham, and Moshe Tennenholtz. 2002. Bidding clubs in first-price auctions. In AAAI\/IAAI. AAAI Press\/The MIT Press, 373--378.","key":"e_1_2_1_7_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_8_1","DOI":"10.1145\/1807342.1807393"},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.1007\/978-3-642-10841-9_14"},{"doi-asserted-by":"publisher","key":"e_1_2_1_10_1","DOI":"10.1016\/j.artint.2008.10.005"},{"doi-asserted-by":"publisher","key":"e_1_2_1_11_1","DOI":"10.1007\/BF00128122"},{"doi-asserted-by":"publisher","key":"e_1_2_1_12_1","DOI":"10.1145\/2090236.2090254"},{"doi-asserted-by":"publisher","key":"e_1_2_1_13_1","DOI":"10.1145\/2542174.2542175"},{"doi-asserted-by":"publisher","key":"e_1_2_1_14_1","DOI":"10.1006\/jeth.2001.2807"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2841227","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2841227","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:53:47Z","timestamp":1750222427000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2841227"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,1,13]]},"references-count":14,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,2,3]]}},"alternative-id":["10.1145\/2841227"],"URL":"https:\/\/doi.org\/10.1145\/2841227","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"type":"print","value":"2167-8375"},{"type":"electronic","value":"2167-8383"}],"subject":[],"published":{"date-parts":[[2016,1,13]]},"assertion":[{"value":"2015-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-01-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}