{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:04:05Z","timestamp":1750309445474,"version":"3.41.0"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2025,2,6]],"date-time":"2025-02-06T00:00:00Z","timestamp":1738800000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Grant-in-Aid for JSPS Research Fellow","award":["JP22KJ1137"],"award-info":[{"award-number":["JP22KJ1137"]}]},{"name":"Grant-in-Aid for Challenging Research","award":["JP21K19759"],"award-info":[{"award-number":["JP21K19759"]}]},{"name":"JST ERATO","award":["JPMJER2301"],"award-info":[{"award-number":["JPMJER2301"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2025,3,31]]},"abstract":"<jats:p>In this study, we propose a polyhedral clinching auction for indivisible goods, which has so far been studied for divisible goods. As in the divisible setting by Goel et\u00a0al. (2015), our mechanism enjoys incentive compatibility, individual rationality, and Pareto optimality, and works with polymatroidal environments. A notable feature of this mechanism for the indivisible setting is that the entire procedure can be conducted in time polynomial of the number of buyers and goods. Moreover, we show additional efficiency guarantees, recently established by Sato for the divisible setting: the liquid welfare (LW) of our mechanism achieves more than half of the optimal LW, and the social welfare is more than the optimal LW.<\/jats:p>","DOI":"10.1145\/3708506","type":"journal-article","created":{"date-parts":[[2024,12,19]],"date-time":"2024-12-19T11:11:52Z","timestamp":1734606712000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Polyhedral Clinching Auctions for Indivisible Goods"],"prefix":"10.1145","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4784-5110","authenticated-orcid":false,"given":"Hiroshi","family":"Hirai","sequence":"first","affiliation":[{"name":"Graduate School of Mathematics, Nagoya University, Nagoya, Japan"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9575-0514","authenticated-orcid":false,"given":"Ryosuke","family":"Sato","sequence":"additional","affiliation":[{"name":"Faculty of Science and Technology, Keio University, Yokohama, Japan"}]}],"member":"320","published-online":{"date-parts":[[2025,2,6]]},"reference":[{"issue":"5","key":"e_1_3_6_2_2","doi-asserted-by":"crossref","first-page":"1452","DOI":"10.1257\/0002828043052330","article-title":"An efficient ascending-bid auction for multiple objects","volume":"94","author":"Ausubel Lawrence M.","year":"2004","unstructured":"Lawrence M. Ausubel. 2004. An efficient ascending-bid auction for multiple objects. American Economic Review 94, 5 (2004), 1452\u20131475.","journal-title":"American Economic Review"},{"key":"e_1_3_6_3_2","first-page":"554","volume-title":"Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Bhattacharya Sayan","year":"2010","unstructured":"Sayan Bhattacharya, Vincent Conitzer, Kamesh Munagala, and Lirong Xia. 2010. Incentive compatible budget elicitation in multi-unit auctions. In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms. 554\u2013572."},{"issue":"2","key":"e_1_3_6_4_2","doi-asserted-by":"crossref","first-page":"400","DOI":"10.1287\/opre.1100.0888","article-title":"An ascending vickrey auction for selling bases of a matroid","volume":"59","author":"Bikhchandani Sushil","year":"2011","unstructured":"Sushil Bikhchandani, Sven de Vries, James Schummer, and Rakesh V. Vohra. 2011. An ascending vickrey auction for selling bases of a matroid. Operations Research 59, 2 (2011), 400\u2013413.","journal-title":"Operations Research"},{"issue":"12","key":"e_1_3_6_5_2","doi-asserted-by":"crossref","first-page":"5521","DOI":"10.1287\/mnsc.2017.2917","article-title":"Efficient allocation and pricing of multifeatured items","volume":"64","author":"Candogan Ozan","year":"2018","unstructured":"Ozan Candogan and Sa\u0161a Peke\u010d. 2018. Efficient allocation and pricing of multifeatured items. Management Science 64, 12 (2018), 5521\u20135543.","journal-title":"Management Science"},{"issue":"1","key":"e_1_3_6_6_2","first-page":"2:1\u20132:34","article-title":"On multiple keyword sponsored search auctions with budgets","volume":"4","author":"Colini-Baldeschi Riccardo","year":"2015","unstructured":"Riccardo Colini-Baldeschi, Stefano Leonardi, Monika Henzinger, and Martin Starnberger. 2015. On multiple keyword sponsored search auctions with budgets. ACM Transactions on Economics and Computation 4, 1 (2015), 2:1\u20132:34.","journal-title":"ACM Transactions on Economics and Computation"},{"key":"e_1_3_6_7_2","first-page":"287","volume-title":"Proceedings of the 14th ACM Conference on Electronic Commerce","author":"Devanur Nikhil R.","year":"2013","unstructured":"Nikhil R. Devanur, Bach Q. Ha, and Jason D. Hartline. 2013. Prior-free auctions for budgeted agents. In Proceedings of the 14th ACM Conference on Electronic Commerce. 287\u2013304."},{"issue":"2","key":"e_1_3_6_8_2","doi-asserted-by":"crossref","first-page":"486","DOI":"10.1016\/j.geb.2011.08.003","article-title":"Multi-unit auctions with budget limits","volume":"74","author":"Dobzinski Shahar","year":"2012","unstructured":"Shahar Dobzinski, Ron Lavi, and Noam Nisan. 2012. Multi-unit auctions with budget limits. Games and Economic Behavior 74, 2 (2012), 486\u2013503.","journal-title":"Games and Economic Behavior"},{"key":"e_1_3_6_9_2","doi-asserted-by":"crossref","first-page":"392","DOI":"10.1007\/978-3-662-43948-7_33","volume-title":"Proceedings of the 41st International Colloquium Automata, Languages, and Programming","author":"Dobzinski Shahar","year":"2014","unstructured":"Shahar Dobzinski and Renato Paes Leme. 2014. Efficiency guarantees in auctions with budgets. In Proceedings of the 41st International Colloquium Automata, Languages, and Programming. 392\u2013404."},{"key":"e_1_3_6_10_2","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1613\/jair.2950","article-title":"Mechanisms for multi-unit auctions","volume":"37","author":"Dobzinski Shahar","year":"2010","unstructured":"Shahar Dobzinski and Noam Nisan. 2010. Mechanisms for multi-unit auctions. Journal of Artificial Intelligence Research 37 (2010), 85\u201398.","journal-title":"Journal of Artificial Intelligence Research"},{"issue":"1","key":"e_1_3_6_11_2","first-page":"4:1\u20134:17","article-title":"Auctions for heterogeneous items and budget limits","volume":"4","author":"D\u00fctting Paul","year":"2015","unstructured":"Paul D\u00fctting, Monika Henzinger, and Martin Starnberger. 2015. Auctions for heterogeneous items and budget limits. ACM Transactions on Economics and Computation 4, 1 (2015), 4:1\u20134:17.","journal-title":"ACM Transactions on Economics and Computation"},{"issue":"1","key":"e_1_3_6_12_2","doi-asserted-by":"crossref","first-page":"242","DOI":"10.1257\/aer.97.1.242","article-title":"Internet advertising and the generalized second-price auction: Selling billions of dollars worth of keywords","volume":"97","author":"Edelman Benjamin","year":"2007","unstructured":"Benjamin Edelman, Michael Ostrovsky, and Michael Schwarz. 2007. Internet advertising and the generalized second-price auction: Selling billions of dollars worth of keywords. American Economic Review 97, 1 (2007), 242\u2013259.","journal-title":"American Economic Review"},{"key":"e_1_3_6_13_2","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1145\/1993574.1993609","volume-title":"Proceedings of the 12th ACM Conference on Electronic Commerce","author":"Fiat Amos","year":"2011","unstructured":"Amos Fiat, Stefano Leonardi, Jared Saia, and Piotr Sankowski. 2011. Single valued combinatorial auctions with budgets. In Proceedings of the 12th ACM Conference on Electronic Commerce. 223\u2013232."},{"key":"e_1_3_6_14_2","volume-title":"Submodular Functions and Optimization, Second Edition","author":"Fujishige Satoru","year":"2005","unstructured":"Satoru Fujishige. 2005. Submodular Functions and Optimization, Second Edition. Elsevier, Amsterdam."},{"key":"e_1_3_6_15_2","first-page":"142:1\u2013142:13","volume-title":"Proceedings of the 43rd International Colloquium Automata, Languages, and Programming","author":"Goel Gagan","year":"2016","unstructured":"Gagan Goel, Stefano Leonardi, Vahab Mirrokni, Afshin Nikzad, and Renato Paes Leme. 2016. Reservation exchange markets for internet advertising. In Proceedings of the 43rd International Colloquium Automata, Languages, and Programming. 142:1\u2013142:13."},{"key":"e_1_3_6_16_2","first-page":"167","volume-title":"Proceedings of the 15th ACM Conference on Economics and Computation","author":"Goel Gagan","year":"2014","unstructured":"Gagan Goel, Vahab Mirrokni, and Renato Paes Leme. 2014. Clinching auctions beyond hard budget constraints. In Proceedings of the 15th ACM Conference on Economics and Computation. 167\u2013184."},{"issue":"3","key":"e_1_3_6_17_2","first-page":"18:1\u201318:27","article-title":"Polyhedral clinching auctions and the AdWords polytope","volume":"62","author":"Goel Gagan","year":"2015","unstructured":"Gagan Goel, Vahab Mirrokni, and Renato Paes Leme. 2015. Polyhedral clinching auctions and the AdWords polytope. Journal of the ACM 62, 3 (2015), 18:1\u201318:27.","journal-title":"Journal of the ACM"},{"key":"e_1_3_6_18_2","doi-asserted-by":"crossref","first-page":"342","DOI":"10.1016\/j.geb.2015.11.008","article-title":"Clinching auctions with online supply","volume":"123","author":"Goel Gagan","year":"2020","unstructured":"Gagan Goel, Vahab Mirrokni, and Renato Paes Leme. 2020. Clinching auctions with online supply. Games and Economic Behavior 123 (2020), 342\u2013358.","journal-title":"Games and Economic Behavior"},{"issue":"1","key":"e_1_3_6_19_2","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1287\/moor.2021.1124","article-title":"Polyhedral clinching auctions for two-sided markets","volume":"47","author":"Hirai Hiroshi","year":"2022","unstructured":"Hiroshi Hirai and Ryosuke Sato. 2022. Polyhedral clinching auctions for two-sided markets. Mathematics of Operations Research 47, 1 (2022), 259\u2013285.","journal-title":"Mathematics of Operations Research"},{"key":"e_1_3_6_20_2","volume-title":"Auction Theory, Second Edition","author":"Krishna Vijay","year":"2010","unstructured":"Vijay Krishna. 2010. Auction Theory, Second Edition. Academic Press, San Diego."},{"key":"e_1_3_6_21_2","first-page":"1049","volume-title":"Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science","author":"Lee Yin Tat","year":"2015","unstructured":"Yin Tat Lee, Aaron Sidford, and Sam Chiu-Wai Wong. 2015. A faster cutting plane method and its implications for combinatorial and convex optimization. In Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science. 1049\u20131065."},{"issue":"2","key":"e_1_3_6_22_2","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1016\/j.geb.2005.02.006","article-title":"Combinatorial auctions with decreasing marginal utilities","volume":"55","author":"Lehmann Benny","year":"2006","unstructured":"Benny Lehmann, Daniel Lehmann, and Noam Nisan. 2006. Combinatorial auctions with decreasing marginal utilities. Games and Economic Behavior 55, 2 (2006), 270\u2013296.","journal-title":"Games and Economic Behavior"},{"key":"e_1_3_6_23_2","first-page":"397","volume-title":"Proceedings of the 16th ACM Conference on Economics and Computation","author":"Lu Pinyan","year":"2015","unstructured":"Pinyan Lu and Tao Xiao. 2015. Improved efficiency guarantees in auctions with budgets. In Proceedings of the 16th ACM Conference on Economics and Computation. 397\u2013413."},{"issue":"1","key":"e_1_3_6_24_2","doi-asserted-by":"crossref","first-page":"58","DOI":"10.1287\/moor.6.1.58","article-title":"Optimal auction design","volume":"6","author":"Myerson Roger B.","year":"1981","unstructured":"Roger B. Myerson. 1981. Optimal auction design. Mathematics of Operations Research 6, 1 (1981), 58\u201373.","journal-title":"Mathematics of Operations Research"},{"key":"e_1_3_6_25_2","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511800481","volume-title":"Algorithmic Game Theory","author":"Nisan Noam","year":"2007","unstructured":"Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V. Vazirani. 2007. Algorithmic Game Theory. Cambridge University Press, New York."},{"key":"e_1_3_6_26_2","unstructured":"R. Sato. 2023. Polyhedral Clinching Auctions with a Single Sample. arXiv:2302.03458. Retrieved from https:\/\/arxiv.org\/abs\/2302.03458"},{"key":"e_1_3_6_27_2","volume-title":"Combinatorial Optimization","author":"Schrijver Alexander","year":"2003","unstructured":"Alexander Schrijver. 2003. Combinatorial Optimization. Springer-Verlag, Berlin."},{"key":"e_1_3_6_28_2","first-page":"211","volume-title":"Proceedings of the 45th Annual ACM Symposium on Theory of Computing","author":"Syrgkanis Vasilis","year":"2013","unstructured":"Vasilis Syrgkanis and Eva Tardos. 2013. Composable and efficient mechanisms. In Proceedings of the 45th Annual ACM Symposium on Theory of Computing. 211\u2013220."}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3708506","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3708506","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:09:55Z","timestamp":1750295395000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3708506"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,6]]},"references-count":27,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,3,31]]}},"alternative-id":["10.1145\/3708506"],"URL":"https:\/\/doi.org\/10.1145\/3708506","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"type":"print","value":"2167-8375"},{"type":"electronic","value":"2167-8383"}],"subject":[],"published":{"date-parts":[[2025,2,6]]},"assertion":[{"value":"2024-01-21","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-11-11","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-02-06","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}