{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,5,13]],"date-time":"2024-05-13T09:11:50Z","timestamp":1715591510289},"reference-count":43,"publisher":"Institute for Operations Research and the Management Sciences (INFORMS)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematics of OR"],"published-print":{"date-parts":[[2014,5]]},"abstract":" We consider a nonlinear extension of the generalized network flow model, with the flow leaving an arc being an increasing concave function of the flow entering it, as proposed by Truemper [Truemper K (1978) Optimal flows in nonlinear gain networks. Networks 8(1):17\u201336] and by Shigeno [Shigeno M (2006) Maximum network flows with concave gains. Math. Programming 107(3):439\u2013459]. We give a polynomial time combinatorial algorithm for solving corresponding flow maximization problems, finding an \u03b5-approximate solution in O(m(m\u03c3+log n)log(MUm\/\u03b5)) arithmetic operations, where M and U are upper bounds on simple parameters, and \u03c3 is the complexity of a value oracle query for the gain functions. This also gives a new algorithm for linear generalized flows, an efficient, purely scaling variant of the Fat-Path algorithm by Goldberg et al. [Goldberg AV, Plotkin SA, Tardos \u00c9 (1991) Combinatorial algorithms for the generalized circulation problem. Math. Oper. Res. 16(2):351\u2013381], not using any cycle cancellations. <\/jats:p> We show that this general convex programming model serves as a common framework for several market equilibrium problems, including the linear Fisher market model and its various extensions. Our result immediately provides combinatorial algorithms for various extensions of these market models. This includes nonsymmetric Arrow-Debreu Nash bargaining, settling an open question by Vazirani [Vazirani VV (2012) The notion of a rational convex program, and an algorithm for the Arrow-Debreu Nash bargaining game. J. ACM 59(2), Article 7]. <\/jats:p>","DOI":"10.1287\/moor.2013.0623","type":"journal-article","created":{"date-parts":[[2013,10,1]],"date-time":"2013-10-01T05:30:11Z","timestamp":1380605411000},"page":"573-596","source":"Crossref","is-referenced-by-count":15,"title":["Concave Generalized Flows with Applications to Market Equilibria"],"prefix":"10.1287","volume":"39","author":[{"given":"L\u00e1szl\u00f3 A.","family":"V\u00e9gh","sequence":"first","affiliation":[{"name":"Department of Management, London School of Economics, London WC2A 2AE, United Kingdom"}]}],"member":"109","reference":[{"key":"B1","doi-asserted-by":"publisher","DOI":"10.1145\/35078.42181"},{"key":"B2","volume-title":"Network Flows: Theory, Algorithms, and Applications","author":"Ahuja RK","year":"1993"},{"key":"B3","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623495285886"},{"key":"B4","doi-asserted-by":"publisher","DOI":"10.1007\/BF01582579"},{"key":"B5","doi-asserted-by":"publisher","DOI":"10.1515\/9781400884179"},{"key":"B6","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2213992"},{"key":"B7","doi-asserted-by":"publisher","DOI":"10.1145\/1411509.1411512"},{"key":"B8","doi-asserted-by":"publisher","DOI":"10.1145\/321694.321699"},{"key":"B9","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177706369"},{"key":"B10","doi-asserted-by":"publisher","DOI":"10.1007\/s101070100238"},{"key":"B11","doi-asserted-by":"publisher","DOI":"10.1145\/28869.28874"},{"key":"B12","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1110.0517"},{"key":"B13","doi-asserted-by":"publisher","DOI":"10.1145\/76359.76368"},{"key":"B14","doi-asserted-by":"publisher","DOI":"10.1287\/moor.16.2.351"},{"key":"B15","doi-asserted-by":"publisher","DOI":"10.1287\/moor.21.3.529"},{"key":"B16","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-002-0333-y"},{"key":"B17","doi-asserted-by":"publisher","DOI":"10.1007\/s101070100248"},{"key":"B18","doi-asserted-by":"publisher","DOI":"10.1287\/moor.22.4.793"},{"key":"B19","doi-asserted-by":"publisher","DOI":"10.1145\/96559.96597"},{"key":"B20","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2008.11.011"},{"key":"B21","doi-asserted-by":"publisher","DOI":"10.1287\/opre.10.4.476"},{"key":"B22","doi-asserted-by":"publisher","DOI":"10.1007\/BF01774658"},{"issue":"4","key":"B23","first-page":"366","volume":"6","author":"Kantorovich LV","year":"1939","journal-title":"Publication House of the Leningrad State University 68"},{"key":"B24","doi-asserted-by":"publisher","DOI":"10.1007\/BF02592100"},{"key":"B25","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794263695"},{"key":"B26","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0121104"},{"key":"B27","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511800481"},{"key":"B28","doi-asserted-by":"publisher","DOI":"10.1109\/TCT.1966.1082612"},{"key":"B29","doi-asserted-by":"publisher","DOI":"10.1016\/0016-0032(67)90046-4"},{"key":"B30","doi-asserted-by":"publisher","DOI":"10.1287\/opre.41.2.338"},{"key":"B31","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806731"},{"key":"B33","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(03)00403-1"},{"key":"B34","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-007-0183-8"},{"key":"B35","first-page":"244","volume":"47","author":"Shigeno M","year":"2004","journal-title":"J. Oper. Res. Soc. Japan"},{"key":"B36","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-005-0608-1"},{"key":"B37","doi-asserted-by":"publisher","DOI":"10.1134\/S1990478909040097"},{"key":"B38","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-69346-7_24"},{"key":"B39","doi-asserted-by":"publisher","DOI":"10.1137\/0132037"},{"key":"B40","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230080106"},{"key":"B41","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1100.0450"},{"key":"B42","doi-asserted-by":"publisher","DOI":"10.1145\/2160158.2160160"},{"key":"B43","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2213981"},{"key":"B44","doi-asserted-by":"publisher","DOI":"10.1287\/moor.27.3.445.313"}],"container-title":["Mathematics of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/pubsonline.informs.org\/doi\/pdf\/10.1287\/moor.2013.0623","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,2]],"date-time":"2023-04-02T19:48:57Z","timestamp":1680464937000},"score":1,"resource":{"primary":{"URL":"https:\/\/pubsonline.informs.org\/doi\/10.1287\/moor.2013.0623"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,5]]},"references-count":43,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,5]]}},"alternative-id":["10.1287\/moor.2013.0623"],"URL":"https:\/\/doi.org\/10.1287\/moor.2013.0623","relation":{},"ISSN":["0364-765X","1526-5471"],"issn-type":[{"value":"0364-765X","type":"print"},{"value":"1526-5471","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,5]]}}}