{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,25]],"date-time":"2026-09-25T00:48:54Z","timestamp":1790297334146,"version":"4.1.0"},"reference-count":17,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2010,1]]},"abstract":"<jats:p>Inspired by the convex program of Eisenberg and Gale which captures Fisher markets with linear utilities, Jain and Vazirani [K. Jain and V. V. Vazirani, Games and Economic Behavior, 70 (2010), pp. 84\u2013106] introduced the class of Eisenberg\u2013Gale (EG) markets. We study the structure of EG(2) markets, the class of EG markets with two agents. We prove that all markets in this class are rational, that is, they have rational equilibrium, and they admit strongly polynomial time algorithms whenever the polytope containing the set of feasible utilities of the two agents can be described via a combinatorial linear program (LP). This helps positively resolve the status of two markets left as open problems by Jain and Vazirani: the capacity allocation market in a directed graph with two source-sink pairs and the network coding market in a directed network with two sources. Our algorithms for solving the corresponding nonlinear convex programs are fundamentally different from those obtained by Jain and Vazirani; whereas they use the primal-dual schema, our main tool is binary search powered by the strong LP-duality theorem.<\/jats:p>","DOI":"10.1137\/070693072","type":"journal-article","created":{"date-parts":[[2010,9,15]],"date-time":"2010-09-15T16:40:28Z","timestamp":1284568828000},"page":"1117-1136","source":"Crossref","is-referenced-by-count":4,"title":["Rationality and Strongly Polynomial Solvability of Eisenberg\u2013Gale Markets with Two Agents"],"prefix":"10.1137","volume":"24","author":[{"given":"Deeparnab","family":"Chakrabarty","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nikhil R.","family":"Devanur","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Vijay V.","family":"Vazirani","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2010,9,14]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1109\/18.850663"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"S. Boyd and L. Vandenberghe,\n                      Convex Optimization\n                      , Cambridge University Press, Cambridge, UK, 2006.","DOI":"10.1109\/CHICC.2006.280567"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"X. Chen, X. Deng, and S.H. Teng,\n                      Settling the complexity of computing two-player Nash equilibria\n                      , J. ACM, 56 (2009).","DOI":"10.1145\/1516512.1516516"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"B. Codenotti and K. Varadarajan,\n                      Efficient computation of equilibrium prices for markets with Leontief utilities\n                      , in Proceedings of International Colloquium on Algorithms, Logic and Programming, 2004, pp. 371\u2013382.","DOI":"10.1007\/978-3-540-27836-8_33"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177706369"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.7.4.337"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1137\/080720826"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.02.017"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1287\/opre.11.3.344"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2008.11.011"},{"key":"R11","unstructured":"K. Jain, V. V. Vazirani, and Y. Ye,\n                      Market equilibrium for homothetic, quasi-concave utilities and economies of scale in production\n                      , in Proceedings of the ACM Symposium on Discrete Algorithms, ACM, New York, 2005, pp. 63\u201371."},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1002\/ett.4460080106"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.2307\/1907266"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.36.1.48"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1287\/opre.34.2.250"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"V. V. Vazirani, 2\n                      -player Nash and nonsymmetric bargaining games: Algorithms and structural properties\n                      , in 3rd International Symposium on Algorithmic Game Theory (SAGT), Athens, Greece, 2010, to appear.","DOI":"10.1007\/978-3-642-16170-4_28"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.02.016"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/070693072","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:59:43Z","timestamp":1787320783000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/070693072"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,1]]},"references-count":17,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2010,1]]}},"alternative-id":["10.1137\/070693072"],"URL":"https:\/\/doi.org\/10.1137\/070693072","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,1]]}}}