{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:17:47Z","timestamp":1750306667162,"version":"3.41.0"},"reference-count":53,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2015,12,2]],"date-time":"2015-12-02T00:00:00Z","timestamp":1449014400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001821","name":"Vienna Science and Technology Fund","doi-asserted-by":"publisher","award":["WWTF grant ICT10-002"],"award-info":[{"award-number":["WWTF grant ICT10-002"]}],"id":[{"id":"10.13039\/501100001821","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000782","name":"European Science Foundation","doi-asserted-by":"publisher","award":["European Young Investigators Award"],"award-info":[{"award-number":["European Young Investigators Award"]}],"id":[{"id":"10.13039\/501100000782","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2016,1,5]]},"abstract":"<jats:p>\n            Auctions are widely used on the Web. Applications range from sponsored search to platforms such as eBay. In these and in many other applications the auctions in use are single-\/multi-item auctions with unit demand. The main drawback of standard mechanisms for this type of auctions, such as VCG and GSP, is the\n            <jats:italic>limited expressiveness<\/jats:italic>\n            that they offer to the bidders. The General Auction Mechanism (GAM) of Aggarwal et al. [2009] takes a first step toward addressing the problem of limited expressiveness by computing a bidder optimal, envy-free outcome for linear utility functions with identical slopes and a single discontinuity per bidder-item pair. We show that in many practical situations this does not suffice to adequately model the preferences of the bidders, and we overcome this problem by presenting the first mechanism for\n            <jats:italic>piecewise linear<\/jats:italic>\n            utility functions with\n            <jats:italic>nonidentical slopes<\/jats:italic>\n            and\n            <jats:italic>multiple discontinuities<\/jats:italic>\n            . Our mechanism runs in polynomial time. Like GAM it is incentive compatible for inputs that fulfill a certain nondegeneracy assumption, but our requirement is more general than the requirement of GAM. For discontinuous utility functions that are nondegenerate as well as for continuous utility functions the outcome of our mechanism is a\n            <jats:italic>competitive equilibrium<\/jats:italic>\n            . We also show how our mechanism can be used to compute approximately bidder optimal, envy-free outcomes for a general class of continuous utility functions via piecewise linear approximation. Finally, we prove hardness results for even more expressive settings.\n          <\/jats:p>","DOI":"10.1145\/2716312","type":"journal-article","created":{"date-parts":[[2015,12,4]],"date-time":"2015-12-04T13:43:07Z","timestamp":1449236587000},"page":"1-34","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["An Expressive Mechanism for Auctions on the Web"],"prefix":"10.1145","volume":"4","author":[{"given":"Paul","family":"D\u00fctting","sequence":"first","affiliation":[{"name":"London School of Economics and Political Science, London, United Kingdom"}]},{"given":"Monika","family":"Henzinger","sequence":"additional","affiliation":[{"name":"University of Vienna, Vienna, Austria"}]},{"given":"Ingmar","family":"Weber","sequence":"additional","affiliation":[{"name":"Qatar Computing Research Institute, Doha, Qatar"}]}],"member":"320","published-online":{"date-parts":[[2015,12,2]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1526709.1526742"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1998549.1998556"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0176-2680(89)90050-5"},{"volume-title":"Equilibrium and Dynamics. Essays in Honour of David Gale","author":"Alkan M.","key":"e_1_2_1_4_1","unstructured":"M. Alkan . 1992. Equilibrium in a matching market with General Preferences . In Equilibrium and Dynamics. Essays in Honour of David Gale , M. Majumdar (Ed.). The MacMillan Press Ltd , London , 1--16. M. Alkan. 1992. Equilibrium in a matching market with General Preferences. In Equilibrium and Dynamics. Essays in Honour of David Gale, M. Majumdar (Ed.). The MacMillan Press Ltd, London, 1--16."},{"key":"e_1_2_1_5_1","unstructured":"I. Ashlagi M. Braverman and A. Hassidim. 2009. Ascending unit demand auctions with budget limits. Working paper (2009).  I. Ashlagi M. Braverman and A. Hassidim. 2009. Ascending unit demand auctions with budget limits. Working paper (2009)."},{"key":"e_1_2_1_6_1","article-title":"Position auctions with budgets: Existence and uniqueness","volume":"10","author":"Ashlagi I.","year":"2010","unstructured":"I. Ashlagi , M. Braverman , A. Hassidim , R. Lavi , and M. Tennenholtz . 2010 . Position auctions with budgets: Existence and uniqueness . The B.E. Journal of Theoretical Economics (Advances) 10 , 1, Article 20 (2010). I. Ashlagi, M. Braverman, A. Hassidim, R. Lavi, and M. Tennenholtz. 2010. Position auctions with budgets: Existence and uniqueness. The B.E. Journal of Theoretical Economics (Advances) 10, 1, Article 20 (2010).","journal-title":"Journal of Theoretical Economics (Advances)"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92185-1_73"},{"volume-title":"Proceedings of the 23rd AAAI. 17--23","author":"Benisch M.","key":"e_1_2_1_8_1","unstructured":"M. Benisch , N. Sadeh , and T. Sandholm . 2008. A theory of expressiveness in mechanisms . In Proceedings of the 23rd AAAI. 17--23 . M. Benisch, N. Sadeh, and T. Sandholm. 2008. A theory of expressiveness in mechanisms. In Proceedings of the 23rd AAAI. 17--23."},{"volume-title":"Proceedings of the 21st IJCAI. 46--52","author":"Benisch M.","key":"e_1_2_1_9_1","unstructured":"M. Benisch , N. Sadeh , and T. Sandholm . 2009. Methodology for designing reasonably expressive mechanisms with application to ad auctions . In Proceedings of the 21st IJCAI. 46--52 . M. Benisch, N. Sadeh, and T. Sandholm. 2009. Methodology for designing reasonably expressive mechanisms with application to ad auctions. In Proceedings of the 21st IJCAI. 46--52."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1064009.1064014"},{"volume-title":"Proceedings of the 23rd AAAI. 30--37","author":"Boutilier C.","key":"e_1_2_1_11_1","unstructured":"C. Boutilier , D. C. Parkes , T. Sandholm , and W. E. Walsh . 2008. Expressive banner ad auctions and model-based online optimization for clearing . In Proceedings of the 23rd AAAI. 30--37 . C. Boutilier, D. C. Parkes, T. Sandholm, and W. E. Walsh. 2008. Expressive banner ad auctions and model-based online optimization for clearing. In Proceedings of the 23rd AAAI. 30--37."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1980534.1980539"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.69"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01726210"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31585-5_1"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2008.02.015"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2010.11.007"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/800157.805047"},{"key":"e_1_2_1_19_1","unstructured":"C. Daskalakis and C. H. Papadimitriou. 2005. Three-player games are hard. Electronic Colloquium on Computational Complexity (2005) 1--10.  C. Daskalakis and C. H. Papadimitriou. 2005. Three-player games are hard. Electronic Colloquium on Computational Complexity (2005) 1--10."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.2307\/1912658"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1086\/261411"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(87)90059-X"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2008.07.011"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2011.08.003"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993574.1993632"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-35311-6_4"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.01.030"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2012.11.006"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1257\/aer.97.1.242"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/321694.321699"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(85)90074-5"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10841-9_20"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772729"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/0899-8256(89)90006-7"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1526709.1526740"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.2307\/1914085"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-10.37.26"},{"key":"e_1_2_1_38_1","first-page":"814","article-title":"How (not) to sell nuclear weapons","volume":"86","author":"Jehiel P.","year":"1996","unstructured":"P. Jehiel , B. Moldovanu , and E. Stacchetti . 1996 . How (not) to sell nuclear weapons . American Economic Review 86 , 4 (1996), 814 -- 829 . P. Jehiel, B. Moldovanu, and E. Stacchetti. 1996. How (not) to sell nuclear weapons. American Economic Review 86, 4 (1996), 814--829.","journal-title":"American Economic Review"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10841-9_53"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800020109"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1086\/261158"},{"key":"e_1_2_1_42_1","volume-title":"Proceedings of the 3rd CONPAR","author":"Limongelli C.","year":"1994","unstructured":"C. Limongelli and R. Pirastu . 1994. Exact solution of linear systems over rational numbers by parallel p-adic arithmetic . In Proceedings of the 3rd CONPAR ( 1994 ), 313--323. C. Limongelli and R. Pirastu. 1994. Exact solution of linear systems over rational numbers by parallel p-adic arithmetic. In Proceedings of the 3rd CONPAR (1994), 313--323."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2008.12.003"},{"key":"e_1_2_1_44_1","doi-asserted-by":"crossref","unstructured":"N. Nisan T. Roughgarden \u00c9. Tardos and V. Vazirani. 2007. Algorithmic Game Theory. Cambridge University Press New York.   N. Nisan T. Roughgarden \u00c9. Tardos and V. Vazirani. 2007. Algorithmic Game Theory. Cambridge University Press New York.","DOI":"10.1017\/CBO9780511800481"},{"volume-title":"Proceedings of the 1st Workshop on Ad Auctions.","author":"Parkes D. C.","key":"e_1_2_1_45_1","unstructured":"D. C. Parkes and T. Sandholm . 2005. Optimize-and-dispatch architecture for expressive ad auctions . In Proceedings of the 1st Workshop on Ad Auctions. D. C. Parkes and T. Sandholm. 2005. Optimize-and-dispatch architecture for expressive ad auctions. In Proceedings of the 1st Workshop on Ad Auctions."},{"key":"e_1_2_1_46_1","first-page":"45","article-title":"Expressive commerce and its application to sourcing: How we conducted &dollar;35 billion of generalized combinatorial auctions","volume":"28","author":"Sandholm T.","year":"2007","unstructured":"T. Sandholm . 2007 . Expressive commerce and its application to sourcing: How we conducted &dollar;35 billion of generalized combinatorial auctions . AI Magazine 28 , 3 (2007), 45 -- 58 . T. Sandholm. 2007. Expressive commerce and its application to sourcing: How we conducted &dollar;35 billion of generalized combinatorial auctions. AI Magazine 28, 3 (2007), 45--58.","journal-title":"AI Magazine"},{"volume-title":"Theory of Linear and Integer Programming","author":"Schrijver A.","key":"e_1_2_1_47_1","unstructured":"A. Schrijver . 1998. Theory of Linear and Integer Programming . John Wiley & Sons , New York . A. Schrijver. 1998. Theory of Linear and Integer Programming. John Wiley & Sons, New York."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01753437"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230010206"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ijindorg.2006.10.002"},{"volume-title":"Proceedings of the 6th ICTS. 156--166","author":"Vazirani V.","key":"e_1_2_1_51_1","unstructured":"V. Vazirani and M. Yannakakis . 2010. PPAD-completeness of fisher markets under piecewise-linear, concave utility functions . In Proceedings of the 6th ICTS. 156--166 . V. Vazirani and M. Yannakakis. 2010. PPAD-completeness of fisher markets under piecewise-linear, concave utility functions. In Proceedings of the 6th ICTS. 156--166."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1540-6261.1961.tb02789.x"},{"volume-title":"Proceedings of the 24th AAAI. 887--894","author":"Walsh W. E.","key":"e_1_2_1_53_1","unstructured":"W. E. Walsh , C. Boutilier , T. Sandholm , R. Shields , G. L. Nemhauser , and D. C. Parkes . 2010. Automated channel abstraction for advertising auctions . In Proceedings of the 24th AAAI. 887--894 . W. E. Walsh, C. Boutilier, T. Sandholm, R. Shields, G. L. Nemhauser, and D. C. Parkes. 2010. Automated channel abstraction for advertising auctions. In Proceedings of the 24th AAAI. 887--894."}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2716312","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2716312","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:00:43Z","timestamp":1750230043000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2716312"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,12,2]]},"references-count":53,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,1,5]]}},"alternative-id":["10.1145\/2716312"],"URL":"https:\/\/doi.org\/10.1145\/2716312","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"type":"print","value":"2167-8375"},{"type":"electronic","value":"2167-8383"}],"subject":[],"published":{"date-parts":[[2015,12,2]]},"assertion":[{"value":"2011-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-12-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}