{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:47:36Z","timestamp":1781077656850,"version":"3.54.1"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2012,4,1]],"date-time":"2012-04-01T00:00:00Z","timestamp":1333238400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2012,4]]},"abstract":"<jats:p>\n            We introduce the notion of a\n            <jats:italic>rational convex program (RCP)<\/jats:italic>\n            and we classify the known RCPs into two classes: quadratic and logarithmic. The importance of rationality is that it opens up the possibility of computing an optimal solution to the program via an algorithm that is either combinatorial or uses an LP-oracle. Next, we define a new Nash bargaining game, called ADNB, which is derived from the linear case of the Arrow-Debreu market model. We show that the convex program for ADNB is a logarithmic RCP, but unlike other known members of this class, it is nontotal.\n          <\/jats:p>\n          <jats:p>Our main result is a combinatorial, polynomial-time algorithm for ADNB. It turns out that the reason for infeasibility of logarithmic RCPs is quite different from that for LPs and quadratic RCPs. We believe that our ideas for surmounting the new difficulties will be useful for dealing with other nontotal RCPs as well. We give an application of our combinatorial algorithm for ADNB to an important \u201cfair\u201d throughput allocation problem on a wireless channel. Finally, we present a number of interesting questions that the new notion of RCP raises.<\/jats:p>","DOI":"10.1145\/2160158.2160160","type":"journal-article","created":{"date-parts":[[2012,5,1]],"date-time":"2012-05-01T13:43:38Z","timestamp":1335879818000},"page":"1-36","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":35,"title":["The notion of a rational convex program, and an algorithm for the arrow-debreu Nash bargaining game"],"prefix":"10.1145","volume":"59","author":[{"given":"Vijay V.","family":"Vazirani","sequence":"first","affiliation":[{"name":"Georgia Institute of Technology, Atlanta, GA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2012,5,3]]},"reference":[{"key":"e_1_2_2_1_1","volume-title":"Proceedings of INFOCOM.","author":"Andrews M.","unstructured":"Andrews , M. , Qian , L. , and Stolyar , A . 2005. Optimal utility based multi-user throughput allocation subject to throughput constraints . In Proceedings of INFOCOM. Andrews, M., Qian, L., and Stolyar, A. 2005. Optimal utility based multi-user throughput allocation subject to throughput constraints. In Proceedings of INFOCOM."},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.26.2.193.10561"},{"key":"e_1_2_2_3_1","unstructured":"Birnbaum B. Devanur N. and Xiao L. 2010. New convex programs and distributed algorithms for Fisher markets with linear and spending constraint utilities. Unpublished manuscript. CSA Illumina ProQuest-CSA www.questia.com.  Birnbaum B. Devanur N. and Xiao L. 2010. New convex programs and distributed algorithms for Fisher markets with linear and spending constraint utilities. Unpublished manuscript. CSA Illumina ProQuest-CSA www.questia.com."},{"key":"e_1_2_2_4_1","doi-asserted-by":"crossref","unstructured":"Boyd S. and Vandenberghe L. 2004. Convex Optimization. Cambridge University Press Cambridge UK.   Boyd S. and Vandenberghe L. 2004. Convex Optimization. Cambridge University Press Cambridge UK.","DOI":"10.1017\/CBO9780511804441"},{"key":"e_1_2_2_5_1","unstructured":"Brainard W. C. and Scarf H. E. 2000. How to compute equilibrium prices in 1891. Cowles Foundation Discussion Paper 1270.  Brainard W. C. and Scarf H. E. 2000. How to compute equilibrium prices in 1891. Cowles Foundation Discussion Paper 1270."},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/070693072"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.29"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10631-6_66"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1411509.1411512"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-4068(76)90028-8"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1965-045-4"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177706369"},{"key":"e_1_2_2_13_1","unstructured":"Frank A. and Karzanov A. 1992. Determining the distance to the perfect matching polytope of a bipartite graph. Unpublished manuscript.  Frank A. and Karzanov A. 1992. Determining the distance to the perfect matching polytope of a bipartite graph. Unpublished manuscript."},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1110.0517"},{"key":"e_1_2_2_15_1","unstructured":"Grotschel M. Lovasz L. and Schirjver A. 1988. Geometric Algorithms and Combinatorial Optimization. Springer-Verlag.  Grotschel M. Lovasz L. and Schirjver A. 1988. Geometric Algorithms and Combinatorial Optimization. Springer-Verlag."},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588328"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/96559.96597"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447384"},{"key":"e_1_2_2_19_1","first-page":"1","article-title":"Eisenberg-Gale markets: Algorithms and game-theoretic properties","volume":"70","author":"Jain K.","year":"2008","unstructured":"Jain , K. and Vazirani , V. V. 2008 . Eisenberg-Gale markets: Algorithms and game-theoretic properties . Games Econ. Beh. 70 , 1 . Jain, K. and Vazirani, V. V. 2008. Eisenberg-Gale markets: Algorithms and game-theoretic properties. Games Econ. Beh. 70, 1.","journal-title":"Games Econ. Beh."},{"key":"e_1_2_2_20_1","volume-title":"Proceedings of the IEEE Semiannual Vehicular Technology Conference.","author":"Jalali A.","unstructured":"Jalali , A. , Padovani , R. , and Pankaj , R . 2000. Data throughput of CDMA-HDR a high efficiency-high data rate personal communication wireless system . In Proceedings of the IEEE Semiannual Vehicular Technology Conference. Jalali, A., Padovani, R., and Pankaj, R. 2000. Data throughput of CDMA-HDR a high efficiency-high data rate personal communication wireless system. In Proceedings of the IEEE Semiannual Vehicular Technology Conference."},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01774658"},{"key":"e_1_2_2_22_1","volume-title":"Solutions to the bargaining problem","author":"Kalai E.","unstructured":"Kalai , E. 1985. Solutions to the bargaining problem . In Social Goals and Social Organization, L. Hurwicz, D. Schmeidler, and H. Sonnenschein, Eds., Cambridge University Press , 75--105. Kalai, E. 1985. Solutions to the bargaining problem. In Social Goals and Social Organization, L. Hurwicz, D. Schmeidler, and H. Sonnenschein, Eds., Cambridge University Press, 75--105."},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794263695"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1002\/ett.4460080106"},{"key":"e_1_2_2_25_1","doi-asserted-by":"crossref","unstructured":"Lobo M. Fazel M. and Boyd S. 2006. Portfolio optimization with linear and fixed costs. Ann. Oper. Res..  Lobo M. Fazel M. and Boyd S. 2006. Portfolio optimization with linear and fixed costs. Ann. Oper. Res..","DOI":"10.1007\/s10479-006-0145-1"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(84)90160-7"},{"key":"e_1_2_2_27_1","unstructured":"Mittlemann H. Benchmarks for optimization software. http:\/\/plato.asu.edu\/bench.html.  Mittlemann H. Benchmarks for optimization software. http:\/\/plato.asu.edu\/bench.html."},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.2307\/1907266"},{"key":"e_1_2_2_29_1","volume-title":"Report from ALGO","author":"Nisan N.","year":"2009","unstructured":"Nisan , N. September 1 0 , 2009. Report from ALGO 2009 . Algorithmic Game Theory Blog . Nisan, N. September 10, 2009. Report from ALGO 2009. Algorithmic Game Theory Blog."},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02930-1_26"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806731"},{"key":"e_1_2_2_32_1","unstructured":"Osborne M. and Rubinstein A. 1994. A Course in Game Theory. The MIT Press.  Osborne M. and Rubinstein A. 1994. A Course in Game Theory. The MIT Press."},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.2000.1989"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10463-010-0295-4"},{"key":"e_1_2_2_35_1","doi-asserted-by":"crossref","unstructured":"Thomson W. and Lensberg T. 1989. Axiomatic Theory of Bargaining with a Variable Population. Cambridge University Press.  Thomson W. and Lensberg T. 1989. Axiomatic Theory of Bargaining with a Variable Population. Cambridge University Press.","DOI":"10.1017\/CBO9780511664489"},{"key":"e_1_2_2_36_1","unstructured":"Tse D. Multiuser diversity in wireless networks. http:\/\/www.eecs.berkeley.edu\/&sim;dtse\/stanford416.ps.  Tse D. Multiuser diversity in wireless networks. http:\/\/www.eecs.berkeley.edu\/&sim;dtse\/stanford416.ps."},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00011379"},{"key":"e_1_2_2_38_1","series-title":"SIAM J. Disc. Math. To appear","volume-title":"Rational convex programs and efficient algorithms for 2-player Nash and nonsymmetric bargaining games","author":"Vazirani V. V.","unstructured":"Vazirani , V. V. 2012. Rational convex programs and efficient algorithms for 2-player Nash and nonsymmetric bargaining games . SIAM J. Disc. Math. To appear . Vazirani, V. V. 2012. Rational convex programs and efficient algorithms for 2-player Nash and nonsymmetric bargaining games. SIAM J. Disc. Math. To appear."},{"key":"e_1_2_2_39_1","volume-title":"Combinatorial algorithms for market equilibria","author":"Vazirani V. V.","unstructured":"Vazirani , V. V. 2007. Combinatorial algorithms for market equilibria . In Algorithmic Game Theory, N. Nisan, T. Roughgarden, E. Tardos, and V. V. Vazirani, Eds., Cambridge University Press , 103--134. Vazirani, V. V. 2007. Combinatorial algorithms for market equilibria. In Algorithmic Game Theory, N. Nisan, T. Roughgarden, E. Tardos, and V. V. Vazirani, Eds., Cambridge University Press, 103--134."},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1100.0450"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1970392.1970394"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2160158.2160160","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2160158.2160160","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:54:50Z","timestamp":1750240490000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2160158.2160160"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,4]]},"references-count":41,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2012,4]]}},"alternative-id":["10.1145\/2160158.2160160"],"URL":"https:\/\/doi.org\/10.1145\/2160158.2160160","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,4]]},"assertion":[{"value":"2009-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-05-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}