{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,18]],"date-time":"2026-02-18T01:19:46Z","timestamp":1771377586357,"version":"3.50.1"},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2018,9,28]],"date-time":"2018-09-28T00:00:00Z","timestamp":1538092800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2018,9,28]],"date-time":"2018-09-28T00:00:00Z","timestamp":1538092800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF0964033"],"award-info":[{"award-number":["CCF0964033"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF1408635"],"award-info":[{"award-number":["CCF1408635"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000925","name":"John Templeton Foundation","doi-asserted-by":"publisher","award":["3966"],"award-info":[{"award-number":["3966"]}],"id":[{"id":"10.13039\/100000925","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2020,1]]},"DOI":"10.1007\/s10107-018-1334-9","type":"journal-article","created":{"date-parts":[[2018,9,28]],"date-time":"2018-09-28T04:00:51Z","timestamp":1538107251000},"page":"343-384","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Computing Walrasian equilibria: fast algorithms and structural properties"],"prefix":"10.1007","volume":"179","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9799-5766","authenticated-orcid":false,"given":"Renato","family":"Paes Leme","sequence":"first","affiliation":[]},{"given":"Sam Chiu-wai","family":"Wong","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,9,28]]},"reference":[{"key":"1334_CR1","doi-asserted-by":"publisher","unstructured":"Ausubel, L., Milgrom, P.: Ascending auctions with package bidding. Front. Theor. Econ. 1(1) (2002). \nhttps:\/\/doi.org\/10.2202\/1534-5963.1019","DOI":"10.2202\/1534-5963.1019"},{"key":"1334_CR2","doi-asserted-by":"publisher","first-page":"602","DOI":"10.1257\/aer.96.3.602","volume":"96","author":"LM Ausubel","year":"2006","unstructured":"Ausubel, L.M.: An efficient dynamic auction for heterogeneous commodities. Am. Econ. Rev. 96, 602\u2013629 (2006)","journal-title":"Am. Econ. Rev."},{"issue":"6","key":"1334_CR3","doi-asserted-by":"publisher","first-page":"1039","DOI":"10.1287\/opre.29.6.1039","volume":"29","author":"RG Bland","year":"1981","unstructured":"Bland, R.G., Goldfarb, D., Todd, M.J.: The ellipsoid method: a survey. Oper. Res. 29(6), 1039\u20131091 (1981)","journal-title":"Oper. Res."},{"issue":"2","key":"1334_CR4","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1006\/jeth.1996.2269","volume":"74","author":"S Bikhchandani","year":"1997","unstructured":"Bikhchandani, S., Mamer, J.W.: Competitive equilibrium in an exchange economy with indivisibilities. J. Econ. Theory 74(2), 385\u2013413 (1997)","journal-title":"J. Econ. Theory"},{"issue":"4","key":"1334_CR5","doi-asserted-by":"publisher","first-page":"1372","DOI":"10.1137\/050641181","volume":"39","author":"L Blumrosen","year":"2009","unstructured":"Blumrosen, L., Nisan, N.: On the computational power of demand queries. SIAM J. Comput. 39(4), 1372\u20131391 (2009)","journal-title":"SIAM J. Comput."},{"key":"1334_CR6","unstructured":"Cheung, Y.K., Cole, R., Devanur, N.R.: Tatonnement beyond gross substitutes?: Gradient descent to the rescue. In: Symposium on Theory of Computing Conference, STOC\u201913, Palo Alto, CA, USA, June 1\u20134, 2013, pp. 191\u2013200 (2013)"},{"key":"1334_CR7","doi-asserted-by":"crossref","unstructured":"Cohen-Addad, V., Eden, A., Feldman, M., Fiat, A.: The invisible hand of dynamic market pricing. \narXiv:1511.05646\n\n (2015)","DOI":"10.1145\/2940716.2940730"},{"issue":"3","key":"1334_CR8","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/S0165-4896(00)00071-8","volume":"41","author":"V Danilov","year":"2001","unstructured":"Danilov, V., Koshevoy, G., Murota, K.: Discrete convexity and equilibria in economies with indivisible goods and money. Math. Soc. Sci. 41(3), 251\u2013273 (2001)","journal-title":"Math. Soc. Sci."},{"issue":"4","key":"1334_CR9","doi-asserted-by":"publisher","first-page":"464","DOI":"10.1006\/aama.1995.1022","volume":"16","author":"AWM Dress","year":"1995","unstructured":"Dress, A.W.M., Terhalle, W.: Rewarding maps: on greedy optimization of set functions. Adv. Appl. Math. 16(4), 464\u2013483 (1995)","journal-title":"Adv. Appl. Math."},{"issue":"5","key":"1334_CR10","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/0893-9659(95)00070-7","volume":"8","author":"AWM Dress","year":"1995","unstructured":"Dress, A.W.M., Terhalle, W.: Well-layered mapsa class of greedily optimizable set functions. Appl. Math. Lett. 8(5), 77\u201380 (1995)","journal-title":"Appl. Math. Lett."},{"issue":"1","key":"1334_CR11","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/j.jet.2005.07.010","volume":"132","author":"S de Vries","year":"2007","unstructured":"de Vries, S., Schummer, J., Vohra, R.V.: On ascending Vickrey auctions for heterogeneous objects. J. Econ. Theory 132(1), 95\u2013118 (2007)","journal-title":"J. Econ. Theory"},{"issue":"2","key":"1334_CR12","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1016\/0893-9659(90)90009-Z","volume":"3","author":"AWM Dress","year":"1990","unstructured":"Dress, A.W.M., Wenzel, W.: Valuated matroids: a new look at the greedy algorithm. Appl. Math. Lett. 3(2), 33\u201335 (1990)","journal-title":"Appl. Math. Lett."},{"issue":"2","key":"1334_CR13","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1016\/0001-8708(92)90028-J","volume":"93","author":"AWM Dress","year":"1992","unstructured":"Dress, A.W.M., Wenzel, W.: Valuated matroids. Adv. Math. 93(2), 214\u2013250 (1992)","journal-title":"Adv. Math."},{"issue":"3","key":"1334_CR14","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1287\/moor.28.3.463.16393","volume":"28","author":"S Fujishige","year":"2003","unstructured":"Fujishige, S., Yang, Z.: A note on Kelso and Crawford\u2019s gross substitutes condition. Math. Oper. Res. 28(3), 463\u2013469 (2003)","journal-title":"Math. Oper. Res."},{"issue":"1","key":"1334_CR15","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1006\/jeth.1999.2531","volume":"87","author":"F Gul","year":"1999","unstructured":"Gul, F., Stacchetti, E.: Walrasian equilibrium with gross substitutes. J. Econ. Theory 87(1), 95\u2013124 (1999)","journal-title":"J. Econ. Theory"},{"key":"1334_CR16","unstructured":"Hatfield, J.W., Kominers, S.D.: Hidden substitutes. In: Proceedings of the Sixteenth ACM Conference on Economics and Computation, EC \u201915, Portland, OR, USA, June 15\u201319, 2015, p.\u00a037 (2015)"},{"key":"1334_CR17","unstructured":"Hatfield, J.W., Kominers, S.D., Nichifor, A., Ostrovsky, M., Westkamp, A.: Full substitutability in trading networks. In: Proceedings of the Sixteenth ACM Conference on Economics and Computation, EC \u201915, Portland, OR, USA, June 15\u201319, 2015, pp. 39\u201340 (2015)"},{"issue":"4","key":"1334_CR18","doi-asserted-by":"publisher","first-page":"913","DOI":"10.1257\/0002828054825466","volume":"95","author":"JW Hatfield","year":"2005","unstructured":"Hatfield, J.W., Milgrom, P.R.: Matching with contracts. Am. Econ. Rev. 95(4), 913\u2013935 (2005)","journal-title":"Am. Econ. Rev."},{"key":"1334_CR19","doi-asserted-by":"crossref","unstructured":"Hsu, J., Morgenstern, J., Rogers, R., Roth, A., Vohra, R.: Do prices coordinate markets? In: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing. ACM, pp. 440\u2013453 (2016)","DOI":"10.1145\/2897518.2897559"},{"issue":"2","key":"1334_CR20","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/s13160-015-0175-7","volume":"32","author":"YT Ikebe","year":"2015","unstructured":"Ikebe, Y.T., Sekiguchi, Y., Shioura, A., Tamura, A.: Stability and competitive equilibria in multi-unit trading networks with discrete concave utility functions. Jpn. J. Ind. Appl. Math. 32(2), 373\u2013410 (2015)","journal-title":"Jpn. J. Ind. Appl. Math."},{"issue":"6","key":"1334_CR21","doi-asserted-by":"publisher","first-page":"1483","DOI":"10.2307\/1913392","volume":"50","author":"AS Kelso Jr","year":"1982","unstructured":"Kelso Jr., A.S., Crawford, V.P.: Job matching, coalition formation, and gross substitutes. Econometrica 50(6), 1483\u20131504 (1982)","journal-title":"Econometrica"},{"issue":"1","key":"1334_CR22","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0041-5553(80)90061-0","volume":"20","author":"LG Khachiyan","year":"1980","unstructured":"Khachiyan, L.G.: Polynomial algorithms in linear programming. USSR Comput. Math. Math. Phys. 20(1), 53\u201372 (1980)","journal-title":"USSR Comput. Math. Math. Phys."},{"key":"1334_CR23","doi-asserted-by":"crossref","unstructured":"Klivans, A.R., Spielman, D.: Randomness efficient identity testing of multivariate polynomials. In: Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, pp. 216\u2013223. ACM (2001)","DOI":"10.1145\/380752.380801"},{"issue":"5","key":"1334_CR24","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/0041-5553(80)90098-1","volume":"20","author":"MK Kozlov","year":"1980","unstructured":"Kozlov, M.K., Tarasov, S.P., Khachiyan, L.G.: The polynomial solvability of convex quadratic programming. USSR Comput. Math. Math. Phys. 20(5), 223\u2013228 (1980)","journal-title":"USSR Comput. Math. Math. Phys."},{"key":"1334_CR25","unstructured":"Kojima, F., Tamura, A., Yokoo, M.: Designing matching mechanisms under constraints: an approach from discrete convex analysis. Mpra paper, University Library of Munich, Germany (2014)"},{"key":"1334_CR26","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1016\/j.geb.2017.10.016","volume":"106","author":"RP Leme","year":"2017","unstructured":"Leme, R.P.: Gross substitutability: an algorithmic survey. Games Econ. Behav. 106, 294\u2013316 (2017)","journal-title":"Games Econ. Behav."},{"key":"1334_CR27","doi-asserted-by":"crossref","unstructured":"Lee, Y.T., Sidford, A., Wong, S.C.: A faster cutting plane method and its implications for combinatorial and convex optimization. In: 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2015) (2015)","DOI":"10.1109\/FOCS.2015.68"},{"key":"1334_CR28","doi-asserted-by":"crossref","unstructured":"Lee, Y.T., Sidford, A., Wong, S.C.: A faster cutting plane method and its implications for combinatorial and convex optimization. \narXiv:1508.04874\n\n (2015)","DOI":"10.1109\/FOCS.2015.68"},{"issue":"1","key":"1334_CR29","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1287\/moor.24.1.95","volume":"24","author":"K Murota","year":"1999","unstructured":"Murota, K., Shioura, A.: M-convex function on generalized polymatroid. Math. Oper. Res. 24(1), 95\u2013105 (1999)","journal-title":"Math. Oper. Res."},{"key":"1334_CR30","doi-asserted-by":"publisher","first-page":"468","DOI":"10.1007\/978-3-642-45030-3_44","volume-title":"Algorithms and Computation","author":"Kazuo Murota","year":"2013","unstructured":"Murota, K., Shioura, A., Yang, Z.: Computing a walrasian equilibrium in iterative auctions with multiple differentiated items. In: International Symposium on Algorithms and Computation, pp. 468\u2013478. Springer, Berlin (2013)"},{"issue":"3","key":"1334_CR31","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1007\/BF03167422","volume":"20","author":"K Murota","year":"2003","unstructured":"Murota, K., Tamura, A.: Application of M-convex submodular flow problem to mathematical economics. Jpn. J. Ind. Appl. Math. 20(3), 257\u2013277 (2003)","journal-title":"Jpn. J. Ind. Appl. Math."},{"issue":"2","key":"1334_CR32","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1006\/aima.1996.0084","volume":"124","author":"K Murota","year":"1996","unstructured":"Murota, K.: Convexity and Steinitz\u2019s exchange property. Adv. Math. 124(2), 272\u2013311 (1996)","journal-title":"Adv. Math."},{"issue":"4","key":"1334_CR33","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1137\/S0895480195279994","volume":"9","author":"K Murota","year":"1996","unstructured":"Murota, K.: Valuated matroid intersection I: optimality criteria. SIAM J. Discrete Math. 9(4), 545\u2013561 (1996)","journal-title":"SIAM J. Discrete Math."},{"issue":"4","key":"1334_CR34","doi-asserted-by":"publisher","first-page":"562","DOI":"10.1137\/S0895480195280009","volume":"9","author":"K Murota","year":"1996","unstructured":"Murota, K.: Valuated matroid intersection II: algorithms. SIAM J. Discrete Math. 9(4), 562\u2013576 (1996)","journal-title":"SIAM J. Discrete Math."},{"key":"1334_CR35","volume-title":"Matrices and Matroids for Systems Analysis","author":"K Murota","year":"2000","unstructured":"Murota, K.: Matrices and Matroids for Systems Analysis, vol. 20. Springer, Berlin (2000)"},{"key":"1334_CR36","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718508","volume-title":"Discrete Convex Analysis. Monographs on Discrete Mathematics and Applications","author":"K Murota","year":"2003","unstructured":"Murota, K.: Discrete Convex Analysis. Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics, Philadelphia (2003)"},{"issue":"1","key":"1334_CR37","first-page":"151","volume":"1","author":"K Murota","year":"2016","unstructured":"Murota, K.: Discrete convex analysis: a tool for economics and game theory. J. Mech. Inst. Des. 1(1), 151\u2013273 (2016)","journal-title":"J. Mech. Inst. Des."},{"key":"1334_CR38","doi-asserted-by":"crossref","unstructured":"Mulmuley, K., Vazirani, U.V., Vazirani, V.V.: Matching is as easy as matrix inversion. In: Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, pp. 345\u2013354. ACM (1987)","DOI":"10.1145\/28395.383347"},{"key":"1334_CR39","unstructured":"Nemirovski, A.: Efficient methods in convex programming (2005)"},{"issue":"1","key":"1334_CR40","doi-asserted-by":"publisher","first-page":"192","DOI":"10.1016\/j.jet.2004.10.007","volume":"129","author":"N Nisan","year":"2006","unstructured":"Nisan, N., Segal, I.: The communication requirements of efficient allocations and supporting prices. J. Econ. Theory 129(1), 192\u2013224 (2006)","journal-title":"J. Econ. Theory"},{"key":"1334_CR41","doi-asserted-by":"crossref","unstructured":"Parkes, D.C.: iBundle: an efficient ascending price bundle auction. In: Proceedings of the 1st ACM Conference on Electronic Commerce, pp. 148\u2013157. ACM (1999)","DOI":"10.1145\/336992.337032"},{"key":"1334_CR42","unstructured":"Parkes, D.C., Ungar, L.H.: An ascending-price generalized Vickrey auction (manuscript). Harvard University (2002)"},{"issue":"1","key":"1334_CR43","doi-asserted-by":"publisher","first-page":"47","DOI":"10.2307\/1911460","volume":"52","author":"AE Roth","year":"1984","unstructured":"Roth, A.E.: Stability and polarization of interests in job matching. Econometrica 52(1), 47\u201357 (1984)","journal-title":"Econometrica"},{"key":"1334_CR44","volume-title":"Theory of Linear and Integer Programming","author":"A Schrijver","year":"1998","unstructured":"Schrijver, A.: Theory of Linear and Integer Programming. Wiley, New York (1998)"},{"issue":"1","key":"1334_CR45","doi-asserted-by":"publisher","first-page":"61","DOI":"10.15807\/jorsj.58.61","volume":"58","author":"A Shioura","year":"2015","unstructured":"Shioura, A., Tamura, A.: Gross substitutes condition and discrete concavity for multi-unit valuations: a survey. J. Oper. Res. Soc. Jpn. 58(1), 61\u2013103 (2015)","journal-title":"J. Oper. Res. Soc. Jpn."},{"issue":"5","key":"1334_CR46","doi-asserted-by":"publisher","first-page":"1385","DOI":"10.1111\/j.1468-0262.2006.00708.x","volume":"74","author":"N Sun","year":"2006","unstructured":"Sun, N., Yang, Z.: Equilibria and indivisibilities: gross substitutes and complements. Econometrica 74(5), 1385\u20131402 (2006)","journal-title":"Econometrica"},{"key":"1334_CR47","unstructured":"Walras, L.: \u00c9l\u00e9ments d\u2019\u00e9conomie politique pure; ou, Th\u00e9orie de la richesse sociale. Corbaz (1874)"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-018-1334-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-018-1334-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-018-1334-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,16]],"date-time":"2020-05-16T16:29:35Z","timestamp":1589646575000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-018-1334-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,9,28]]},"references-count":47,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["1334"],"URL":"https:\/\/doi.org\/10.1007\/s10107-018-1334-9","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,9,28]]},"assertion":[{"value":"24 July 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 September 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 September 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}