{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:26:41Z","timestamp":1787340401049,"version":"build-2736575974"},"reference-count":31,"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":[[2011,1]]},"abstract":"<jats:p>We present a game-theoretic model that captures many of the intricacies of interdomain routing in today's Internet. In this model, the strategic agents are source nodes located on a network, who aim to send traffic to a unique destination node. The interaction between the agents is dynamic and complex\u2014asynchronous, sequential, and based on partial information. Best-reply dynamics in this model capture crucial aspects of the de facto standard interdomain routing protocol, namely, the Border Gateway Protocol (BGP). We study complexity and incentive-related issues in this model. Our main results show that in realistic and well-studied settings, BGP is incentive-compatible. That is, not only does myopic behavior of all players converge to a \u201cstable\u201d routing outcome, but no player has motivation to unilaterally deviate from BGP. Moreover, we show that even coalitions of players of any size cannot improve their routing outcomes by collaborating. Unlike the vast majority of works in mechanism design, our results do not require any monetary transfers (to or by the agents).<\/jats:p>","DOI":"10.1137\/080734017","type":"journal-article","created":{"date-parts":[[2011,12,22]],"date-time":"2011-12-22T10:05:42Z","timestamp":1324548342000},"page":"1892-1912","source":"Crossref","is-referenced-by-count":8,"title":["Interdomain Routing and Games"],"prefix":"10.1137","volume":"40","author":[{"given":"Hagay","family":"Levin","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael","family":"Schapira","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aviv","family":"Zohar","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2011,12,22]]},"reference":[{"key":"R1","unstructured":"K. Butler, T. Farley, P. Mcdaniel, and J. Rexford,\n                      A Survey of BGP Security Issues and Solutions\n                      , Technical report TD-5UGJ33, AT&T Labs, Florham Park, NY, 2004."},{"key":"R2","doi-asserted-by":"crossref","unstructured":"V. Conitzer and T. Sandholm,\n                      Communication complexity as a lower bound for learning in games\n                      , in Proceedings of the International Conference on Machine Learning (ICML), Banf, Alberta, Canada, 2004, pp. 185\u2013192.","DOI":"10.1145\/1015330.1015351"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"R. R. Dakdouk, S. Salihoglu, H. Wang, and H. Xie,\n                      Interdomain routing as social choice\n                      , in Proceedings of ICDCSW '06, IEEE Computer Society, Washington, DC, 2006, p. 38.","DOI":"10.1109\/ICDCSW.2006.65"},{"key":"R4","unstructured":"A. Fabrikant and C. Papadimitriou,\n                      The complexity of game dynamics: BGP oscillations, sink equilibria, and beyond\n                      , in Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, SIAM, Philadelphia, 2008, pp. 844\u2013853."},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1145\/1090191.1080096"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.02.020"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-005-0122-y"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"J. Feigenbaum, V. Ramachandran, and M. Schapira,\n                      Incentive-compatible interdomain routing\n                      , in Proceedings of the 7th ACM Conference on Electronic Commerce, ACM, New York, 2006, pp. 130\u2013139.","DOI":"10.1145\/1134707.1134722"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-005-0134-7"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"J. Feigenbaum, M. Schapira, and S. Shenker,\n                      Algorithmic Game Theory\n                      , Cambridge University Press, Cambridge, UK, 2007, pp. 363\u2013383.","DOI":"10.1017\/CBO9780511800481.016"},{"key":"R11","unstructured":"L. Gao, T. G. Griffin, and J. Rexford,\n                      Inherently safe backup routing with BGP\n                      , in Proceedings of the 20th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2001), IEEE, Washington, DC, 2001, pp. 547\u2013556."},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1109\/90.974523"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"S. Goldberg, S. Halevi, A. D. Jaggard, V. Ramachandran, and R. N. Wright,\n                      Rationality and traffic attraction: Incentives for honest path announcements in BGP\n                      , in Proceedings of SIGCOMM, V. Bahl, D. Wetherall, S. Savage, and I. Stoica, eds., ACM, New York, 2008, pp. 267\u2013278.","DOI":"10.1145\/1402958.1402989"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"T. G. Griffin, A. D. Jaggard, and V. Ramachandran,\n                      Design principles of policy languages for path vector protocols\n                      , in Proceedings of the 2003 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, ACM, New York, 2003, pp. 61\u201372.","DOI":"10.1145\/863955.863964"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"T. G. Griffin, F. B. Shepherd, and G. Wilfong,\n                      Policy disputes in path-vector protocols\n                      , in Proceedings of the 7th Annual International Conference on Network Protocols, IEEE Computer Society, Los Alamitos, CA, 1999, pp. 21\u201330.","DOI":"10.1109\/ICNP.1999.801912"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1145\/316194.316231"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"A. Hall, E. Nikolova, and C. Papadimitriou,\n                      Incentive-compatible interdomain routing with linear utilities\n                      , in Proceedings of the 3rd International Workshop on Internet and Network Economics (WINE 2007), Lecture Notes in Comput. Sci. 4858, Springer, New York, 2007, pp. 232\u2013244.","DOI":"10.1007\/978-3-540-77105-0_23"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"S. Hart and Y. Mansour,\n                      The communication complexity of uncoupled nash equilibrium procedures\n                      , in Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC 2007), ACM, New York, 2007, pp. 345\u2013353.","DOI":"10.1145\/1250790.1250843"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1007\/BF02392825"},{"key":"R20","unstructured":"P. E. Haxell and G. T. Wilfong,\n                      A fractional model of the border gateway protocol (BGP)\n                      , in Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, SIAM, Philadelphia, 2008, pp. 193\u2013199."},{"key":"R21","unstructured":"G. Huston,\n                      Interconnection, peering, and settlements\n                      , in Proceedings of the Internet Global Summit (INET), The Internet Society, San Jose, CA, 1999."},{"key":"R22","unstructured":"S. Kintali,\n                      A Distributed Protocol for Fractional Stable Paths Problem\n                      , Technical report, GT-CS-08-06, Georgia Institute of Technology, Atlanta, GA, 2008."},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2009.04.003"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"E. Kushilevitz and N. Nisan,\n                      Communication Complexity\n                      , Cambridge University Press, Cambridge, UK, 1997.","DOI":"10.1017\/CBO9780511574948"},{"key":"R25","unstructured":"A. Mu'alem and M. Schapira,\n                      Setting lower bounds on truthfulness\n                      , in Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2007), ACM, New York, SIAM, Philadelphia, 2007, pp. 1143\u20131152."},{"key":"R26","doi-asserted-by":"crossref","unstructured":"R. Sami, M. Schapira, and A. Zohar,\n                      Searching for stability in interdomain routing\n                      , in Proceedings of the 28th IEEE Conference on Computer Communications (INFOCOM 2009), IEEE, Washington, DC, 2009, pp. 549\u2013557.","DOI":"10.1109\/INFCOM.2009.5061961"},{"key":"R27","unstructured":"R. Sami, M. Schapira, and A. Zohar,\n                      Security and selfishness in interdomain routing\n                      , working paper, 2008."},{"key":"R28","unstructured":"Secure BGP Project Page\n                      , http:\/\/www.ir.bbn.com\/sbgp\/."},{"key":"R29","doi-asserted-by":"crossref","unstructured":"J. Shneidman and D. C. Parkes,\n                      Specification faithfulness in networks with rational nodes\n                      , in Proceedings of the 23rd Annual ACM Symposium on Principles of Distributed Computing (PODC 2004), ACM, New York, 2004, pp. 88\u201397.","DOI":"10.1145\/1011767.1011781"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2005.857111"},{"key":"R31","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\/080734017","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:33:23Z","timestamp":1787337203000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/080734017"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,1]]},"references-count":31,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2011,1]]}},"alternative-id":["10.1137\/080734017"],"URL":"https:\/\/doi.org\/10.1137\/080734017","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,1]]}}}