{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,5]],"date-time":"2026-10-05T08:58:26Z","timestamp":1791190706851,"version":"4.1.0"},"reference-count":46,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2013,1]]},"abstract":"<jats:p>We resolve the computational complexity of a number of outstanding open problems with practical applications. Here is the list of problems we show to be ${\\bf{PPAD}}$-complete, along with the domains of practical significance: fractional stable paths problem (FSPP)---Internet routing; core of balanced games---economics and game theory; Scarf's lemma---combinatorics; hypergraph matching---social choice and preference systems; fractional bounded budget connection games (FBBC)---social networks; and strong fractional kernel---graph theory. In fact, we show that no fully polynomial-time approximation schemes exist (unless ${\\bf{PPAD}}$ is in ${\\bf{FP}}$). This paper is entirely a series of reductions that build in nontrivial ways on the framework established in previous work. In the course of deriving these reductions, we created two new concepts---preference games and personalized equilibria. The entire set of new reductions can be presented as a lattice with the above problems sandwiched between preference games (at the \u201ceasy\u201d end) and personalized equilibria (at the \u201chard\u201d end). Our completeness results extend to natural approximate versions of most of these problems.<\/jats:p>","DOI":"10.1137\/120874655","type":"journal-article","created":{"date-parts":[[2013,11,5]],"date-time":"2013-11-05T11:50:33Z","timestamp":1383652233000},"page":"2063-2113","source":"Crossref","is-referenced-by-count":21,"title":["Reducibility among Fractional Stability Problems"],"prefix":"10.1137","volume":"42","author":[{"given":"Shiva","family":"Kintali","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Laura J.","family":"Poplawski","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rajmohan","family":"Rajaraman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ravi","family":"Sundaram","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shang-Hua","family":"Teng","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2013,11,5]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(02)00028-X"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1997.1731"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1016\/0304-4068(74)90037-8"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1111\/1468-0262.00155"},{"key":"atypb5","unstructured":"O. N. Bondareva,\n                      Some applications of the methods of linear programming to the theory of cooperative games\n                      , Problemy Kibernet., No. 10 (1963), pp. 119-139."},{"key":"atypb6","unstructured":"X. Chen and X. Deng,\n                      $3$-NASH Is PPAD-Complete\n                      , Report TR05-134, Electronic Colloquium on Computational Complexity (ECCC), 2005."},{"key":"atypb7","doi-asserted-by":"crossref","unstructured":"X. Chen and X. Deng\n                      Settling the complexity of two-player Nash equilibrium\n                      , in Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2006, pp. 261-272.","DOI":"10.1109\/FOCS.2006.69"},{"key":"atypb8","doi-asserted-by":"crossref","unstructured":"X. Chen, X. Deng, and S.H. Teng,\n                      Computing Nash equilibria: Approximation and smoothed complexity\n                      , in Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2006, pp. 603-612.","DOI":"10.1109\/FOCS.2006.20"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1145\/1516512.1516516"},{"key":"atypb10","doi-asserted-by":"crossref","unstructured":"V. Conitzer and T. Sandholm,\n                      Complexity of determining nonemptiness of the core\n                      , in Proceedings of the 4th ACM Conference on Electronic Commerce, 2003, pp. 230-231.","DOI":"10.1145\/779928.779973"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2006.01.005"},{"key":"atypb12","unstructured":"G. Dantzig,\n                      Linear Programming and Extensions\n                      , Princeton University Press, Princeton, NJ, 1998."},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1137\/070699652"},{"key":"atypb14","first-page":"347","author":"Fabrikant A.","year":"2003","journal-title":"New York"},{"key":"atypb15","first-page":"439","author":"Fang Q.","year":"2007","journal-title":"Heidelberg"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1962.11989827"},{"key":"atypb17","doi-asserted-by":"crossref","unstructured":"R. Garg, V. Kumar, A. Rudra, and A. Verma,\n                      Coalitional games on graphs: Core structure, substitutes and frugality\n                      , in Proceedings of the 4th ACM Conference on Electronic Commerce (EC), 2003, pp. 248-289.","DOI":"10.1145\/779928.779982"},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"P. W. Goldberg and C. H. Papadimitriou,\n                      Reducibility among equilibrium problems\n                      , in Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC), 2006, pp. 61-70.","DOI":"10.1145\/1132516.1132526"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1109\/90.993304"},{"key":"atypb20","unstructured":"P. E. Haxell and G. T. Wilfong,\n                      A fractional model of the Border Gateway Protocol (BGP)\n                      , in Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2008, pp. 193-199."},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1137\/080730019"},{"key":"atypb22","first-page":"150","author":"Immorlica N.","year":"2006","journal-title":"Heidelberg"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1006\/jeth.1996.0108"},{"key":"atypb24","first-page":"253","author":"Kearns M.","year":"2001","journal-title":"San Francisco"},{"key":"atypb25","unstructured":"S. Kintali,\n                      A distributed protocol for fractional stable paths problem\n                      , in Proceedings of the DIMACS\/DyDAn Workshop on Secure Internet Routing, Rutgers University, Piscataway, NJ, 2008."},{"key":"atypb26","doi-asserted-by":"crossref","unstructured":"S. Kintali, L. J. Poplawski, R. Rajaraman, R. Sundaram, and S.H. Teng,\n                      Reducibility among fractional stability problems\n                      , in Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2009, pp. 283-292.","DOI":"10.1109\/FOCS.2009.57"},{"key":"atypb27","first-page":"131","author":"Pap T.","year":"2010","journal-title":"Japan"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1016\/j.jmateco.2007.05.012"},{"key":"atypb29","doi-asserted-by":"crossref","unstructured":"N. Laoutaris, L. J. Poplawski, R. Rajaraman, R. Sundaram, and S.H. Teng,\n                      Bounded budget connection (BBC) games or how to make friends and influence people, on a budget\n                      , in Proceedings of the Twenty-Seventh ACM Symposium on Principles of Distributed Computing (PODC), 2008, pp. 165-174.","DOI":"10.1145\/1400751.1400774"},{"key":"atypb30","doi-asserted-by":"crossref","unstructured":"N. Laoutaris, L. J. Poplawski, R. Rajaraman, R. Sundaram, and S.H. Teng,\n                      Bounded Budget Connection (BBC) Games or How to Make Friends and Influence People, on a Budget\n                      , preprint, arXiv:0806.1727v1 [cs.GT], 2008.","DOI":"10.1145\/1400751.1400774"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1137\/0112033"},{"key":"atypb32","doi-asserted-by":"crossref","unstructured":"E. Markakis and A. Saberi,\n                      On the core of the multicommodity flow game\n                      , in Proceedings of the 4th ACM Conference on Electronic Commerce, 2003, pp. 93-97.","DOI":"10.1145\/779928.779940"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90200-L"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.36.1.48"},{"key":"atypb35","doi-asserted-by":"crossref","unstructured":"J. Nash,\n                      Non-cooperative games\n                      , Ann. of Math. (2), 54 (1951), pp. 286-295.","DOI":"10.2307\/1969529"},{"key":"atypb36","doi-asserted-by":"crossref","unstructured":"N. Nisan, T. Roughgarden, E. Tardos, and V. V. Vazirani,\n                      Algorithmic Game Theory\n                      , Cambridge University Press, New York, 2007.","DOI":"10.1017\/CBO9780511800481"},{"key":"atypb37","unstructured":"M. J. Osborne and A. Rubinstein,\n                      A Course in Game Theory\n                      , MIT Press, Cambridge, MA, 1994."},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80063-7"},{"key":"atypb39","doi-asserted-by":"crossref","unstructured":"Y. Rehkter and T. Li,\n                      A Border Gateway Protocol $4$ (BGP-$4$)\n                      , RFC 1771, Network Working Group, http:\/\/www.ietf.org\/rfc\/rfc1771.txt (1995).","DOI":"10.17487\/rfc1771"},{"key":"atypb40","first-page":"35","volume":"69","author":"Scarf H. E.","year":"1967","journal-title":"Econometrica"},{"key":"atypb41","unstructured":"A. Schrijver,\n                      Combinatorial Optimization. Polyhedra and Efficiency\n                      , Vol. B, Springer-Verlag, Berlin, 2003."},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800140404"},{"key":"atypb43","doi-asserted-by":"crossref","unstructured":"L. S. Shapley,\n                      A note on the Lemke-Howson algorithm. Pivoting and extensions\n                      , Math. Programming Stud., No. 1 (1974), pp. 175-189.","DOI":"10.1007\/BFb0121248"},{"key":"atypb44","unstructured":"J. W. Stewart III,\n                      BGP$4$:Inter-Domain Routing in the Internet\n                      , Addison-Wesley, Boston, 1998."},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1.1.54"},{"key":"atypb46","doi-asserted-by":"publisher","DOI":"10.1016\/S1389-1286(99)00108-5"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/120874655","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:38:10Z","timestamp":1787337490000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/120874655"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1]]},"references-count":46,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2013,1]]}},"alternative-id":["10.1137\/120874655"],"URL":"https:\/\/doi.org\/10.1137\/120874655","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,1]]}}}