{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T01:22:48Z","timestamp":1787361768103,"version":"build-2736575974"},"reference-count":38,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","funder":[{"name":"Janos Bolyai Research Fellowship"},{"DOI":"10.13039\/501100005683","name":"Kyoto University","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100005683","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP17K00028"],"award-info":[{"award-number":["JP17K00028"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP18-H05291"],"award-info":[{"award-number":["JP18-H05291"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["20H05795"],"award-info":[{"award-number":["20H05795"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["21H03397"],"award-info":[{"award-number":["21H03397"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP18H05291"],"award-info":[{"award-number":["JP18H05291"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP19H05485"],"award-info":[{"award-number":["JP19H05485"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP20K11692"],"award-info":[{"award-number":["JP20K11692"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003825","name":"Magyar Tudom\u00e1nyos Akad\u00e9mia","doi-asserted-by":"publisher","award":["LP2021-1\/2021"],"award-info":[{"award-number":["LP2021-1\/2021"]}],"id":[{"id":"10.13039\/501100003825","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100011019","name":"Nemzeti Kutat\u00e1si Fejleszt\u00e9si \u00e9s Innov\u00e1ci\u00f3s Hivatal","doi-asserted-by":"publisher","award":["FK128673"],"award-info":[{"award-number":["FK128673"]}],"id":[{"id":"10.13039\/501100011019","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100011019","name":"Nemzeti Kutat\u00e1si Fejleszt\u00e9si \u00e9s Innov\u00e1ci\u00f3s Hivatal","doi-asserted-by":"publisher","award":["UNKP-20-5"],"award-info":[{"award-number":["UNKP-20-5"]}],"id":[{"id":"10.13039\/501100011019","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100011019","name":"Nemzeti Kutat\u00e1si Fejleszt\u00e9si \u00e9s Innov\u00e1ci\u00f3s Hivatal","doi-asserted-by":"publisher","award":["TKP2020-NKA-06"],"award-info":[{"award-number":["TKP2020-NKA-06"]}],"id":[{"id":"10.13039\/501100011019","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>In this paper, we study the problem of maximizing social welfare in combinatorial markets through pricing schemes. We consider the existence of prices that are capable of achieving optimal social welfare without a central tie-breaking coordinator. In the case of two buyers with matroid rank valuations, we give polynomial-time algorithms that always find such prices when one of the matroids is a partition matroid or both matroids are strongly base orderable. This result partially answers a question raised by D\u00fctting and V\u00e9gh [Private communication, 2017]. We further formalize a weighted variant of the conjecture of D\u00fctting and V\u00e9gh, and show that the weighted variant can be reduced to the unweighted one based on the weight-splitting theorem for weighted matroid intersection by Frank. We also show that a similar reduction technique works for M${}^\\natural$-concave functions or, equivalently, for gross substitutes functions.<\/jats:p>","DOI":"10.1137\/20m1386335","type":"journal-article","created":{"date-parts":[[2021,11,8]],"date-time":"2021-11-08T11:28:10Z","timestamp":1636370890000},"page":"2662-2678","source":"Crossref","is-referenced-by-count":3,"title":["Market Pricing for Matroid Rank Valuations"],"prefix":"10.1137","volume":"35","author":[{"given":"Krist\u00f3f","family":"B\u00e9rczi","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Naonori","family":"Kakimura","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yusuke","family":"Kobayashi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2021,11,8]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-64946-3_15"},{"key":"atypb2","doi-asserted-by":"crossref","unstructured":"L. Blumrosen and T. Holenstein,\n                      Posted prices vs. negotiations: an asymptotic analysis\n                      , in EC'08: Proceedings of the 9th ACM Conference on Electronic Commerce, 2008, 49.","DOI":"10.1145\/1386790.1386801"},{"key":"atypb3","first-page":"311","author":"Chawla S.","year":"2010","journal-title":"New York"},{"key":"atypb4","first-page":"149","author":"Chawla S.","year":"2010","journal-title":"New York"},{"key":"atypb5","first-page":"1962","author":"Chawla S.","year":"2019","journal-title":"Philadelphia"},{"key":"atypb6","doi-asserted-by":"crossref","unstructured":"E. H. Clarke,\n                      Multipart pricing of public goods\n                      , Public Choice, (1971), pp. 17-33.","DOI":"10.1007\/BF01726210"},{"key":"atypb7","first-page":"383","author":"Cohen-Addad V.","year":"2016","journal-title":"New York"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s2-14.1.55"},{"key":"atypb9","unstructured":"P. D\u00fctting, M. Feldman, T. Kesselheim, and B. Lucier,\n                      Prophet Inequalities Made Easy: Stochastic Optimization by Pricing Non-Stochastic Inputs\n                      , preprint,https:\/\/arxiv.org\/abs\/1612.03161, 2016."},{"key":"atypb10","first-page":"540","author":"D\u00fctting P.","year":"2017","journal-title":"Proceedings of the IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), IEEE"},{"key":"atypb11","unstructured":"P. D\u00fctting and L. A. V\u00e9gh. Private communication, 2017."},{"key":"atypb12","first-page":"7","author":"Eden A.","year":"2019","journal-title":"Germany"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1007\/BF01584082"},{"key":"atypb14","first-page":"140","author":"Ezra T.","year":"2018","journal-title":"Springer"},{"key":"atypb15","first-page":"123","author":"Feldman M.","year":"2014","journal-title":"Philadelphia"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1137\/13094339X"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(81)90032-8"},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"A. Frank,\n                      Generalized polymatroids\n                      , in Finite and Infinite Sets, Vols. $1$, $2$, Colloq. Math. Soc. J\u00e1nos Bolyai 37, North-Holland, Amsterdam, 1984, pp. 285-294.","DOI":"10.1016\/B978-0-444-86893-0.50021-8"},{"key":"atypb19","unstructured":"A. Frank,\n                      Connections in Combinatorial Optimization\n                      , Oxford University Press, Oxford, 2011."},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1287\/moor.28.3.463.16393"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.2307\/1914085"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1006\/jeth.1999.2531"},{"key":"atypb23","first-page":"440","author":"Hsu J.","year":"2016","journal-title":"New York"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.2307\/1913392"},{"key":"atypb25","unstructured":"S. Krogdahl,\n                      A Combinatorial Base for Some Optimal Matroid Intersection Algorithms\n                      , Tech. Report STAN-CS-74-468, Computer Science Department, Stanford University, Stanford, CA, 1974."},{"key":"atypb26","unstructured":"S. Krogdahl,\n                      A Combinatorial Proof for a Weighted Matroid Intersection Algorithm\n                      , Tech. Report Computer Science Report 17, Institute of Mathematical and Physical Sciences, University of Tromso, Tromso, Norway, 1976."},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(77)90118-2"},{"key":"atypb28","doi-asserted-by":"crossref","unstructured":"K. Murota,\n                      Discrete Convex Analysis\n                      , SIAM Monogr. Discrete Math. Appl., SIAM, Philadelphia, 2003,https:\/\/doi.org\/10.1137\/1.9780898718508.","DOI":"10.1137\/1.9780898718508"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.22574\/jmid.2016.12.005"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1287\/moor.24.1.95"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1016\/j.jet.2004.10.007"},{"key":"atypb32","doi-asserted-by":"crossref","unstructured":"H. Nishimura and S. Kuroda,\n                      A Lost Mathematician, Takeo Nakasawa: The Forgotten Father of Matroid Theory\n                      , Birkh\u00e4user Verlag, Basel, 2009.","DOI":"10.1007\/978-3-7643-8573-6"},{"key":"atypb33","doi-asserted-by":"crossref","unstructured":"J. Oxley,\n                      Matroid Theory\n                      , Oxford University Press, Oxford, 2011.","DOI":"10.1093\/acprof:oso\/9780198566946.001.0001"},{"key":"atypb34","unstructured":"A. Schrijver,\n                      Combinatorial Optimization: Polyhedra and Efficiency\n                      , Algorithms Combin. 24, Springer-Verlag, Berlin, 2003."},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.15807\/jorsj.58.61"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1111\/j.1540-6261.1961.tb02789.x"},{"key":"atypb37","unstructured":"L. Walras,\n                      \u00c9l\u00e9ments d'\u00e9conomie politique pure, ou, Th\u00e9orie de la richesse sociale\n                      , F. Rouge, 1896."},{"key":"atypb38","first-page":"147","author":"Whitney H.","year":"1992","journal-title":"Springer"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/20M1386335","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:06:42Z","timestamp":1787317602000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/20M1386335"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":38,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/20M1386335"],"URL":"https:\/\/doi.org\/10.1137\/20m1386335","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}