{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,20]],"date-time":"2025-11-20T13:16:54Z","timestamp":1763644614094,"version":"3.41.0"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2025,9,30]]},"abstract":"<jats:p>Consider a single auctioneer who wants to sell multiple units of distinct indivisible items to bidders with private valuations. The set of feasible allocations is constrained to integer base points, which are the integer points of an integer base polyhedron. Each bidder\u2019s valuation is the integer restriction of a sum of nondecreasing, concave single-parameter functions. This seemingly abstract setting is of theoretical relevance and has various interesting applications.<\/jats:p>\n          <jats:p>In this context, we develop an ascending auction that implements a social welfare-maximizing allocation, charges Vickrey\u2013Clarke\u2013Groves prices, relies only on a single price, is ex-post incentive-compatible, and satisfies unconditional winner privacy.<\/jats:p>\n          <jats:p>The auction has a polynomial running time in the number of bidders, items, and units; in the case of linear separable valuations it runs even in strongly polynomial time, thereby improving on the literature.<\/jats:p>\n          <jats:p>Moreover, by relaxing unconditional winner privacy, the auction can be made fully polynomial in the number of bidders, items, units, and integer breakpoints of bidders\u2019 valuations.<\/jats:p>\n          <jats:p>\n            If we assume that bidders are\n            <jats:italic toggle=\"yes\">unit-demand<\/jats:italic>\n            , then our auction is dominant-strategy incentive-compatible and (weakly) group strategy-proof, much like deferred acceptance auctions.\n          <\/jats:p>","DOI":"10.1145\/3727625","type":"journal-article","created":{"date-parts":[[2025,4,1]],"date-time":"2025-04-01T13:46:54Z","timestamp":1743515214000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["An Ascending Polynomial Running Time Vickrey Auction for Selling Bases of an Integer Polymatroid"],"prefix":"10.1145","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9763-2631","authenticated-orcid":false,"given":"Stephen","family":"Raach","sequence":"first","affiliation":[{"name":"University of Trier","place":["Trier, Germany"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2440-4937","authenticated-orcid":false,"given":"Sven","family":"de Vries","sequence":"additional","affiliation":[{"name":"University of Trier","place":["Trier, Germany"]}]}],"member":"320","published-online":{"date-parts":[[2025,6,16]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1257\/0002828043052330"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1257\/aer.96.3.602"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1100.0888"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01726210"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0014-2921(97)00122-0"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1093\/qmath\/31.1.65"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1002\/nav.22210"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jet.2005.07.010"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1086\/261411"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2011.08.003"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.3386\/w23034"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2016.0835"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1956-045-5"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(82)90048-4"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/3033274.3085142"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/2757277"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00199-005-0032-z"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(91)90300-K"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.2307\/1914085"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1006\/jeth.1999.2580"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0120924"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0066195"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2021.1124"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502096"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.2307\/1913392"},{"key":"e_1_3_3_27_2","article-title":"Note on VCG vs. price raising for matching markets","author":"Kern Walter","year":"2016","unstructured":"Walter Kern, Bodo Manthey, and Marc Uetz. 2016. Note on VCG vs. price raising for matching markets. arXiv:1604.04157. Retrieved from https:\/\/arxiv.org\/abs\/1604.04157","journal-title":"arXiv:1604.04157"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1137\/0605024"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.68"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/585265.585266"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1257\/aer.20160425"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-68874-4_10"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1086\/704074"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.5555\/945827"},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-72792-7_20"},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-007-0189-2"},{"key":"e_1_3_3_37_2","series-title":"Oxfird graduate textes in mathematics","volume-title":"Matroid Theory (Second Edition)","author":"Oxley James G.","year":"2006","unstructured":"James G. Oxley. 2006. Matroid Theory (Second Edition). Oxfird graduate textes in mathematics, Vol. 21. Oxford University Press, USA."},{"key":"e_1_3_3_38_2","first-page":"75","volume-title":"Proceedings of the 17th National Conference on Artificial Intelligence and 12th Conference on Innovative Applications of Artificial Intelligenc","author":"Parkes David C.","year":"2000","unstructured":"David C. Parkes and Lyle H. Ungar. 2000. Iterative combinatorial auctions: Theory and practice. In Proceedings of the 17th National Conference on Artificial Intelligence and 12th Conference on Innovative Applications of Artificial Intelligenc. AAAI Press, 75\u201381."},{"key":"e_1_3_3_39_2","article-title":"A simplified analysis of the ascending auction to sell a matroid base","author":"Peis Britta","year":"2024","unstructured":"Britta Peis and Niklas Rieken. 2024. A simplified analysis of the ascending auction to sell a matroid base. arXiv:2404.12121. Retrieved from https:\/\/arxiv.org\/abs\/2404.12121","journal-title":"arXiv:2404.12121"},{"key":"e_1_3_3_40_2","volume-title":"Implementing efficient outcomes in combinatorial allocation problems","author":"Raach Stephen","year":"2023","unstructured":"Stephen Raach. 2023. Implementing efficient outcomes in combinatorial allocation problems. PhD thesis. Trier University."},{"key":"e_1_3_3_41_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977912.2"},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jet.2005.04.004"},{"key":"e_1_3_3_43_2","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency (Volume C)","author":"Schrijver Alexander","year":"2003","unstructured":"Alexander Schrijver. 2003. Combinatorial Optimization: Polyhedra and Efficiency (Volume C). Springer Science & Business Media."},{"key":"e_1_3_3_44_2","doi-asserted-by":"publisher","DOI":"10.1111\/j.1540-6261.1961.tb02789.x"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3727625","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T04:48:50Z","timestamp":1750135730000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3727625"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,16]]},"references-count":43,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,9,30]]}},"alternative-id":["10.1145\/3727625"],"URL":"https:\/\/doi.org\/10.1145\/3727625","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"type":"print","value":"2167-8375"},{"type":"electronic","value":"2167-8383"}],"subject":[],"published":{"date-parts":[[2025,6,16]]},"assertion":[{"value":"2023-10-09","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-03-11","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-06-16","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}