{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,13]],"date-time":"2026-05-13T17:30:11Z","timestamp":1778693411511,"version":"3.51.4"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2015,6,30]],"date-time":"2015-06-30T00:00:00Z","timestamp":1435622400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2015,6,30]]},"abstract":"<jats:p>A central issue in applying auction theory in practice is the problem of dealing with budget-constrained agents. A desirable goal in practice is to design incentive compatible, individually rational, and Pareto optimal auctions while respecting the budget constraints. Achieving this goal is particularly challenging in the presence of nontrivial combinatorial constraints over the set of feasible allocations.<\/jats:p>\n          <jats:p>\n            Toward this goal and motivated by AdWords auctions, we present an auction for\n            <jats:italic>polymatroidal<\/jats:italic>\n            environments satisfying these properties. Our auction employs a novel clinching technique with a clean geometric description and only needs an oracle access to the submodular function defining the polymatroid. As a result, this auction not only simplifies and generalizes all previous results, it applies to several new applications including AdWords Auctions, bandwidth markets, and video on demand. In particular, our characterization of the AdWords auction as polymatroidal constraints might be of independent interest. This allows us to design the first mechanism for Ad Auctions taking into account simultaneously budgets, multiple keywords and multiple slots.\n          <\/jats:p>\n          <jats:p>We show that it is impossible to extend this result to generic polyhedral constraints. This also implies an impossibility result for multiunit auctions with decreasing marginal utilities in the presence of budget constraints.<\/jats:p>","DOI":"10.1145\/2757277","type":"journal-article","created":{"date-parts":[[2015,7,6]],"date-time":"2015-07-06T14:04:16Z","timestamp":1436191456000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":27,"title":["Polyhedral Clinching Auctions and the AdWords Polytope"],"prefix":"10.1145","volume":"62","author":[{"given":"Gagan","family":"Goel","sequence":"first","affiliation":[{"name":"Google Research, New York, NY"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vahab","family":"Mirrokni","sequence":"additional","affiliation":[{"name":"Google Research, New York, NY"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Renato Paes","family":"Leme","sequence":"additional","affiliation":[{"name":"Google Research, New York, NY"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,6,30]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109676"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1526709.1526742"},{"key":"e_1_2_1_3_1","unstructured":"Saeed Alaei Kamal Jain and Azarakhsh Malekian. 2010. Walrasian equilibrium for unit demand buyers with non-quasi-linear utilities. CoRR abs\/1006.4696.  Saeed Alaei Kamal Jain and Azarakhsh Malekian. 2010. Walrasian equilibrium for unit demand buyers with non-quasi-linear utilities. CoRR abs\/1006.4696."},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of FOCS. 482--491","author":"Aaron"},{"key":"e_1_2_1_5_1","article-title":"Position auctions with budgets: Existence and uniqueness","volume":"10","author":"Ashlagi Itai","year":"2010","journal-title":"B.E. J. Theoret. Econ. Adv."},{"key":"e_1_2_1_6_1","article-title":"An efficient ascending-bid auction for multiple objects","author":"Ausubel Lawrence M.","year":"1997","journal-title":"Amer. Econ. Rev. 94."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1111\/1467-937X.00164"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of SODA. 554--572","author":"Bhattacharya Sayan","year":"2010"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806743"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1100.0888"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1064009.1064014"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.88"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993574.1993588"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993574.1993613"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1111\/1467-937X.00033"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31585-5_1"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2492002.2482554"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993574.1993589"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.39"},{"key":"e_1_2_1_20_1","unstructured":"Shahar Dobzinski and Renato Paes Leme. 2013. Efficiency guarantees in auctions with budgets. CoRR abs\/1304.7048.  Shahar Dobzinski and Renato Paes Leme. 2013. Efficiency guarantees in auctions with budgets. CoRR abs\/1304.7048."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2090236.2090243"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2012.11.006"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1257\/aer.97.1.242"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-79309-0_17"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993574.1993609"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2213990"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627817.2627861"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2600057.2602851"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70356-X"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2011.08.001"},{"key":"e_1_2_1_31_1","volume-title":"Orlin","author":"Iwata Satoru","year":"2009"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25510-6_39"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993574.1993587"},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the Ad Auctions Workshop.","author":"Lucier Brendan","year":"2011"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100051677"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.6.1.58"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250910.1250913"},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of SIGMETRICS.","author":"Nguyen Th\u00e0nh","year":"2011"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-72792-7_19"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.75"},{"key":"e_1_2_1_41_1","volume-title":"Pai and Rakesh Vohra","author":"Mallesh","year":"2008"},{"key":"e_1_2_1_42_1","volume-title":"Combinatorial Optimization - Polyhedra and Efficiency","author":"Schrijver A."},{"key":"e_1_2_1_43_1","unstructured":"Hal R. Varian. 2006. Position auctions. Int. J. Indust. Org.  Hal R. Varian. 2006. Position auctions. Int. J. Indust. Org."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2757277","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2757277","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:16:27Z","timestamp":1750227387000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2757277"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,6,30]]},"references-count":43,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,6,30]]}},"alternative-id":["10.1145\/2757277"],"URL":"https:\/\/doi.org\/10.1145\/2757277","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,6,30]]},"assertion":[{"value":"2013-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-06-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}