[{"conference":{"end_date":"2015-09-12","location":"Amsterdam, Netherlands","start_date":"2015-09-09","name":"WINE: International Conference on Web and Internet Economics"},"language":[{"iso":"eng"}],"oa_version":"Preprint","month":"12","publication":"11th International Conference on Web and Internet Economics","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.1604.05562","open_access":"1"}],"status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_identifier":{"isbn":["9783662489949"],"eisbn":["9783662489956"],"issn":["0302-9743"]},"oa":1,"type":"conference","date_published":"2015-12-09T00:00:00Z","publisher":"Springer Nature","quality_controlled":"1","page":"104–117","article_processing_charge":"No","date_created":"2022-08-08T13:33:56Z","publication_status":"published","intvolume":"      9470","alternative_title":["LNCS"],"title":"Ad exchange: Envy-free auctions with mediators","scopus_import":"1","_id":"11773","author":[{"full_name":"Ben-Zwi, Oren","last_name":"Ben-Zwi","first_name":"Oren"},{"orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","first_name":"Monika H","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"full_name":"Loitzenbauer, Veronika","first_name":"Veronika","last_name":"Loitzenbauer"}],"volume":9470,"extern":"1","day":"09","arxiv":1,"doi":"10.1007/978-3-662-48995-6_8","abstract":[{"text":"Ad exchanges are an emerging platform for trading advertisement slots on the web with billions of dollars revenue per year. Every time a user visits a web page, the publisher of that web page can ask an ad exchange to auction off the ad slots on this page to determine which advertisements are shown at which price. Due to the high volume of traffic, ad networks typically act as mediators for individual advertisers at ad exchanges. If multiple advertisers in an ad network are interested in the ad slots of the same auction, the ad network might use a “local” auction to resell the obtained ad slots among its advertisers.\r\n\r\nIn this work we want to deepen the theoretical understanding of these new markets by analyzing them from the viewpoint of combinatorial auctions. Prior work studied mostly single-item auctions, while we allow the advertisers to express richer preferences over multiple items. We develop a game-theoretic model for the entanglement of the central auction at the ad exchange with the local auctions at the ad networks. We consider the incentives of all three involved parties and suggest a three-party competitive equilibrium, an extension of the Walrasian equilibrium that ensures envy-freeness for all participants. We show the existence of a three-party competitive equilibrium and a polynomial-time algorithm to find one for gross-substitute bidder valuations.","lang":"eng"}],"year":"2015","citation":{"ama":"Ben-Zwi O, Henzinger MH, Loitzenbauer V. Ad exchange: Envy-free auctions with mediators. In: <i>11th International Conference on Web and Internet Economics</i>. Vol 9470. Springer Nature; 2015:104–117. doi:<a href=\"https://doi.org/10.1007/978-3-662-48995-6_8\">10.1007/978-3-662-48995-6_8</a>","apa":"Ben-Zwi, O., Henzinger, M. H., &#38; Loitzenbauer, V. (2015). Ad exchange: Envy-free auctions with mediators. In <i>11th International Conference on Web and Internet Economics</i> (Vol. 9470, pp. 104–117). Amsterdam, Netherlands: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-662-48995-6_8\">https://doi.org/10.1007/978-3-662-48995-6_8</a>","ieee":"O. Ben-Zwi, M. H. Henzinger, and V. Loitzenbauer, “Ad exchange: Envy-free auctions with mediators,” in <i>11th International Conference on Web and Internet Economics</i>, Amsterdam, Netherlands, 2015, vol. 9470, pp. 104–117.","chicago":"Ben-Zwi, Oren, Monika H Henzinger, and Veronika Loitzenbauer. “Ad Exchange: Envy-Free Auctions with Mediators.” In <i>11th International Conference on Web and Internet Economics</i>, 9470:104–117. Springer Nature, 2015. <a href=\"https://doi.org/10.1007/978-3-662-48995-6_8\">https://doi.org/10.1007/978-3-662-48995-6_8</a>.","short":"O. Ben-Zwi, M.H. Henzinger, V. Loitzenbauer, in:, 11th International Conference on Web and Internet Economics, Springer Nature, 2015, pp. 104–117.","mla":"Ben-Zwi, Oren, et al. “Ad Exchange: Envy-Free Auctions with Mediators.” <i>11th International Conference on Web and Internet Economics</i>, vol. 9470, Springer Nature, 2015, pp. 104–117, doi:<a href=\"https://doi.org/10.1007/978-3-662-48995-6_8\">10.1007/978-3-662-48995-6_8</a>.","ista":"Ben-Zwi O, Henzinger MH, Loitzenbauer V. 2015. Ad exchange: Envy-free auctions with mediators. 11th International Conference on Web and Internet Economics. WINE: International Conference on Web and Internet Economics, LNCS, vol. 9470, 104–117."},"date_updated":"2023-02-10T09:06:23Z","external_id":{"arxiv":["1604.05562"]}},{"quality_controlled":"1","page":"230–243","publisher":"Springer Nature","scopus_import":"1","_id":"11774","author":[{"first_name":"Yun Kuen","last_name":"Cheung","full_name":"Cheung, Yun Kuen"},{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","first_name":"Monika H","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530"},{"first_name":"Martin","last_name":"Hoefer","full_name":"Hoefer, Martin"},{"full_name":"Starnberger, Martin","last_name":"Starnberger","first_name":"Martin"}],"date_created":"2022-08-08T13:54:32Z","article_processing_charge":"No","publication_status":"published","intvolume":"      9470","alternative_title":["LNCS"],"title":"Combinatorial auctions with conflict-based externalities","volume":9470,"extern":"1","year":"2015","citation":{"ista":"Cheung YK, Henzinger MH, Hoefer M, Starnberger M. 2015. Combinatorial auctions with conflict-based externalities. 11th International Conference on Web and Internet Economics. WINE: International Conference on Web and Internet Economics, LNCS, vol. 9470, 230–243.","short":"Y.K. Cheung, M.H. Henzinger, M. Hoefer, M. Starnberger, in:, 11th International Conference on Web and Internet Economics, Springer Nature, 2015, pp. 230–243.","mla":"Cheung, Yun Kuen, et al. “Combinatorial Auctions with Conflict-Based Externalities.” <i>11th International Conference on Web and Internet Economics</i>, vol. 9470, Springer Nature, 2015, pp. 230–243, doi:<a href=\"https://doi.org/10.1007/978-3-662-48995-6_17\">10.1007/978-3-662-48995-6_17</a>.","chicago":"Cheung, Yun Kuen, Monika H Henzinger, Martin Hoefer, and Martin Starnberger. “Combinatorial Auctions with Conflict-Based Externalities.” In <i>11th International Conference on Web and Internet Economics</i>, 9470:230–243. Springer Nature, 2015. <a href=\"https://doi.org/10.1007/978-3-662-48995-6_17\">https://doi.org/10.1007/978-3-662-48995-6_17</a>.","ieee":"Y. K. Cheung, M. H. Henzinger, M. Hoefer, and M. Starnberger, “Combinatorial auctions with conflict-based externalities,” in <i>11th International Conference on Web and Internet Economics</i>, Amsterdam, Netherlands, 2015, vol. 9470, pp. 230–243.","ama":"Cheung YK, Henzinger MH, Hoefer M, Starnberger M. Combinatorial auctions with conflict-based externalities. In: <i>11th International Conference on Web and Internet Economics</i>. Vol 9470. Springer Nature; 2015:230–243. doi:<a href=\"https://doi.org/10.1007/978-3-662-48995-6_17\">10.1007/978-3-662-48995-6_17</a>","apa":"Cheung, Y. K., Henzinger, M. H., Hoefer, M., &#38; Starnberger, M. (2015). Combinatorial auctions with conflict-based externalities. In <i>11th International Conference on Web and Internet Economics</i> (Vol. 9470, pp. 230–243). Amsterdam, Netherlands: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-662-48995-6_17\">https://doi.org/10.1007/978-3-662-48995-6_17</a>"},"date_updated":"2023-02-10T09:08:30Z","external_id":{"arxiv":["1509.09147"]},"day":"09","doi":"10.1007/978-3-662-48995-6_17","arxiv":1,"abstract":[{"text":"Combinatorial auctions (CA) are a well-studied area in algorithmic mechanism design. However, contrary to the standard model, empirical studies suggest that a bidder’s valuation often does not depend solely on the goods assigned to him. For instance, in adwords auctions an advertiser might not want his ads to be displayed next to his competitors’ ads. In this paper, we propose and analyze several natural graph-theoretic models that incorporate such negative externalities, in which bidders form a directed conflict graph with maximum out-degree Δ. We design algorithms and truthful mechanisms for social welfare maximization that attain approximation ratios depending on Δ.\r\n\r\nFor CA, our results are twofold: (1) A lottery that eliminates conflicts by discarding bidders/items independent of the bids. It allows to apply any truthful 𝛼-approximation mechanism for conflict-free valuations and yields an 𝒪(𝛼Δ)-approximation mechanism. (2) For fractionally sub-additive valuations, we design a rounding algorithm via a novel combination of a semi-definite program and a linear program, resulting in a cone program; the approximation ratio is 𝒪((ΔloglogΔ)/logΔ). The ratios are almost optimal given existing hardness results.\r\n\r\nFor adwords auctions, we present several algorithms for the most relevant scenario when the number of items is small. In particular, we design a truthful mechanism with approximation ratio 𝑜(Δ) when the number of items is only logarithmic in the number of bidders.","lang":"eng"}],"language":[{"iso":"eng"}],"conference":{"end_date":"2015-12-12","location":"Amsterdam, Netherlands","start_date":"2015-12-09","name":"WINE: International Conference on Web and Internet Economics"},"publication":"11th International Conference on Web and Internet Economics","oa_version":"Preprint","month":"12","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.1509.09147"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","type":"conference","date_published":"2015-12-09T00:00:00Z","publication_identifier":{"issn":["0302-9743"],"eisbn":["9783662489956"],"isbn":["9783662489949"]},"oa":1}]