{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:19:14Z","timestamp":1750306754726,"version":"3.41.0"},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2013,9,1]],"date-time":"2013-09-01T00:00:00Z","timestamp":1377993600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100005386","name":"Israeli Centers for Research Excellence","doi-asserted-by":"publisher","award":["Center No. 4\/11"],"award-info":[{"award-number":["Center No. 4\/11"]}],"id":[{"id":"10.13039\/501100005386","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["FA9550-09-1-0538"],"award-info":[{"award-number":["FA9550-09-1-0538"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004963","name":"Seventh Framework Programme","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100004963","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-0830540, CCF-1101215","CCF-095312, CCF-1101283"],"award-info":[{"award-number":["CCF-0830540, CCF-1101215","CCF-095312, CCF-1101283"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001742","name":"United States-Israel Binational Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001742","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004965","name":"Sixth Framework Programme","doi-asserted-by":"publisher","award":["IST 2002-506778"],"award-info":[{"award-number":["IST 2002-506778"]}],"id":[{"id":"10.13039\/501100004965","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N00014-09-1-0751"],"award-info":[{"award-number":["N00014-09-1-0751"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2013,9]]},"abstract":"<jats:p>\n            In this work, we study the degree to which small fluctuations in costs in well-studied potential games can impact the result of natural best-response and improved-response dynamics. We call this the\n            <jats:italic>Price of Uncertainty<\/jats:italic>\n            and study it in a wide variety of potential games including fair cost-sharing games, set-cover games, routing games, and job-scheduling games. We show that in certain cases, even extremely small fluctuations can have the ability to cause these dynamics to spin out of control and move to states of much higher social cost, whereas in other cases these dynamics are much more stable even to large degrees of fluctuation.\n          <\/jats:p>\n          <jats:p>\n            We also consider the resilience of these dynamics to a small number of Byzantine players about which no assumptions are made. We show again a contrast between different games. In certain cases (e.g., fair cost-sharing, set-cover, job-scheduling) even a single Byzantine player can cause best-response dynamics to transition from low-cost states to states of substantially higher cost, whereas in others (e.g., the class of\n            <jats:italic>\u03b2<\/jats:italic>\n            -nice games, which includes routing, market-sharing and many others) these dynamics are much more resilient.\n          <\/jats:p>\n          <jats:p>\n            Overall, our work can be viewed as analyzing the inherent resilience or\n            <jats:italic>safety<\/jats:italic>\n            of games to different kinds of imperfections in player behavior, player information, or in modeling assumptions made.\n          <\/jats:p>","DOI":"10.1145\/2509413.2509415","type":"journal-article","created":{"date-parts":[[2013,9,23]],"date-time":"2013-09-23T13:47:05Z","timestamp":1379944025000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["The Price of Uncertainty"],"prefix":"10.1145","volume":"1","author":[{"given":"Maria-Florina","family":"Balcan","sequence":"first","affiliation":[{"name":"Georgia Institute of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Avrim","family":"Blum","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yishay","family":"Mansour","sequence":"additional","affiliation":[{"name":"Tel Aviv University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2013,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.55"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.68"},{"key":"e_1_2_1_3_1","unstructured":"Arieli I. and Young P. 2011. Fast convergence in population games. Tech. rep. 570 Oxford.  Arieli I. and Young P. 2011. Fast convergence in population games. Tech. rep. 570 Oxford."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1386790.1386832"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250910.1250926"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25510-6_1"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.1993.1023"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0899-8256(02)00554-7"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-79309-0_30"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Candogan O. Ozdaglar A. and Parrilo P. A. 2011. Dynamics in near-potential games. Tech. rep. 2872 LIDS.  Candogan O. Ozdaglar A. and Parrilo P. A. 2011. Dynamics in near-potential games. Tech. rep. 2872 LIDS.","DOI":"10.1109\/CDC.2011.6160867"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/11672142_28"},{"volume-title":"Proceedings of the 13th ACM-SIAM SODA.","author":"Czumaj A.","key":"e_1_2_1_12_1","unstructured":"Czumaj , A. and Voecking , B . 2002. Tight bounds for worst-case equilibria . In Proceedings of the 13th ACM-SIAM SODA. Czumaj, A. and Voecking, B. 2002. Tight bounds for worst-case equilibria. In Proceedings of the 13th ACM-SIAM SODA."},{"key":"e_1_2_1_13_1","volume-title":"La Prevision: Ses Lois Logiques, Ses Sources Subjectives. Annales de lInstitut Henri Poincare 7, 1--68.","author":"de Finetti B.","year":"1937","unstructured":"de Finetti , B. 1937 . La Prevision: Ses Lois Logiques, Ses Sources Subjectives. Annales de lInstitut Henri Poincare 7, 1--68. de Finetti, B. 1937. La Prevision: Ses Lois Logiques, Ses Sources Subjectives. Annales de lInstitut Henri Poincare 7, 1--68."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1273340.1273348"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2006.872884"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/293347.293351"},{"volume-title":"Proceedings of the 16th STACS. 404--413","author":"Koutsoupias E.","key":"e_1_2_1_17_1","unstructured":"Koutsoupias , E. and Papadimitriou , C. H . 1999. Worst-case equilibria . In Proceedings of the 16th STACS. 404--413 . Koutsoupias, E. and Papadimitriou, C. H. 1999. Worst-case equilibria. In Proceedings of the 16th STACS. 404--413."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.1996.0044"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1146381.1146391"},{"key":"e_1_2_1_20_1","volume-title":"Eds","author":"Nisan N.","year":"2007","unstructured":"Nisan , N. , Roughgarden , T. , Tardos , E. , and Vazirani , V . Eds . 2007 . Algorithmic Game Theory. Cambridge University Press . Nisan, N., Roughgarden, T., Tardos, E., and Vazirani, V. Eds. 2007. Algorithmic Game Theory. Cambridge University Press."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01737559"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92185-1_20"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536485"},{"volume-title":"The Foundations of Statistics","author":"Savage L. J.","key":"e_1_2_1_24_1","unstructured":"Savage , L. J. 1954. The Foundations of Statistics . Wiley . Savage, L. J. 1954. The Foundations of Statistics. Wiley."},{"key":"e_1_2_1_25_1","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"Schrijver A.","year":"2002","unstructured":"Schrijver , A. 2002 . Combinatorial Optimization: Polyhedra and Efficiency . Springer . Schrijver, A. 2002. Combinatorial Optimization: Polyhedra and Efficiency. Springer."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1811039.1811052"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.7455683"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/645413.652124"},{"key":"e_1_2_1_29_1","unstructured":"von Neumann J. and Morgenstern O. 1944. Theory of Games and Economic Behavior. Princeton University Press.  von Neumann J. and Morgenstern O. 1944. Theory of Games and Economic Behavior . Princeton University Press."}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2509413.2509415","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2509413.2509415","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:28:35Z","timestamp":1750231715000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2509413.2509415"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,9]]},"references-count":29,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2013,9]]}},"alternative-id":["10.1145\/2509413.2509415"],"URL":"https:\/\/doi.org\/10.1145\/2509413.2509415","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"type":"print","value":"2167-8375"},{"type":"electronic","value":"2167-8383"}],"subject":[],"published":{"date-parts":[[2013,9]]},"assertion":[{"value":"2011-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-09-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}