{"id":{"repo_id":"mit","oai_identifier":"oai:dspace.mit.edu:1721.1/145081"},"canonical_url":"https://search.dev.ndltd.org/etd/mit/oai:dspace.mit.edu:1721.1/145081","repository":{"repo_id":"mit","name":"MIT","base_url":"https://dspace.mit.edu/oai/request"},"display":{"title":"Smoothed Complexity of Network Coordination Games","abstract":"The problem of finding or computing Nash equilibria has been an important problem in economics and computer science for decades. Classical worst-case and expectedcase analyses have shown that in many cases for many types of games, computing Nash equilibria is intractable. However, it has been empirically shown that in many instances, approximate Nash equilibria can be computed efficiently. Thus, there is a growing interest in the smoothed complexity of games. That is, the complexity of computing Nash equilibria when the inputs to the problem are confined to look more like real-world inputs. This thesis provides a further analysis of the smoothed complexity of network coordination games. We specifically look at the smoothed complexity of the 2-Flip algorithm. While we do not prove that using the 2-Flip algorithm on 2-Flip-Max-Cut achieves smoothed quasipolynomial time, we discuss multiple attempts at this goal, and hope to provide other researchers with the inspiration to prove quasipolynomial time.","abstract_html":"The problem of finding or computing Nash equilibria has been an important problem in economics and computer science for decades. Classical worst-case and expectedcase analyses have shown that in many cases for many types of games, computing Nash equilibria is intractable. However, it has been empirically shown that in many instances, approximate Nash equilibria can be computed efficiently. Thus, there is a growing interest in the smoothed complexity of games. That is, the complexity of computing Nash equilibria when the inputs to the problem are confined to look more like real-world inputs. This thesis provides a further analysis of the smoothed complexity of network coordination games. We specifically look at the smoothed complexity of the 2-Flip algorithm. While we do not prove that using the 2-Flip algorithm on 2-Flip-Max-Cut achieves smoothed quasipolynomial time, we discuss multiple attempts at this goal, and hope to provide other researchers with the inspiration to prove quasipolynomial time.","abstract_has_math":false,"creators":["Viera, Julian T."],"institution":"Massachusetts Institute of Technology","degree_name":"Master","degree_level":null,"degree_discipline":null,"degree_department":"Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science","school":null,"contributors":[],"advisors":["Daskalakis, Constantinos"],"committee_chairs":[],"committee_members":[],"year":2022,"date_issued":"2022-05","date_published":"2022-05","updated_at":"2026-07-22T22:22:31Z","subjects":[],"languages":[],"rights":["In Copyright - Educational Use Permitted","Copyright MIT"],"rights_urls":["http://rightsstatements.org/page/InC-EDU/1.0/"],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/1721.1/145081","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Daskalakis, Constantinos"]},{"key":"dc:contributor.department","label":"Department","values":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science"]},{"key":"dc:creator","label":"Author","values":["Viera, Julian T."]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2022-08-29T16:31:36Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2022-08-29T16:31:36Z"]},{"key":"dc:date.issued","label":"Date","values":["2022-05"]},{"key":"dc:publisher","label":"Institution","values":["Massachusetts Institute of Technology"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Master","Master of Engineering in Electrical Engineering and Computer Science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:rights","label":"Dc Rights","values":["In Copyright - Educational Use Permitted","Copyright MIT"]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://rightsstatements.org/page/InC-EDU/1.0/"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/1721.1/145081"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["The problem of finding or computing Nash equilibria has been an important problem in economics and computer science for decades. Classical worst-case and expectedcase analyses have shown that in many cases for many types of games, computing Nash equilibria is intractable. However, it has been empirically shown that in many instances, approximate Nash equilibria can be computed efficiently. Thus, there is a growing interest in the smoothed complexity of games. That is, the complexity of computing Nash equilibria when the inputs to the problem are confined to look more like real-world inputs. This thesis provides a further analysis of the smoothed complexity of network coordination games. We specifically look at the smoothed complexity of the 2-Flip algorithm. While we do not prove that using the 2-Flip algorithm on 2-Flip-Max-Cut achieves smoothed quasipolynomial time, we discuss multiple attempts at this goal, and hope to provide other researchers with the inspiration to prove quasipolynomial time."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["M.Eng."]},{"key":"dc:title","label":"Title","values":["Smoothed Complexity of Network Coordination Games"]}]}],"canonical_facts":{"dc:contributor.advisor":["Daskalakis, Constantinos"],"dc:contributor.department":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science"],"dc:creator":["Viera, Julian T."],"dc:date.accessioned":["2022-08-29T16:31:36Z"],"dc:date.available":["2022-08-29T16:31:36Z"],"dc:date.issued":["2022-05"],"dc:description.abstract":["The problem of finding or computing Nash equilibria has been an important problem in economics and computer science for decades. Classical worst-case and expectedcase analyses have shown that in many cases for many types of games, computing Nash equilibria is intractable. However, it has been empirically shown that in many instances, approximate Nash equilibria can be computed efficiently. Thus, there is a growing interest in the smoothed complexity of games. That is, the complexity of computing Nash equilibria when the inputs to the problem are confined to look more like real-world inputs. This thesis provides a further analysis of the smoothed complexity of network coordination games. We specifically look at the smoothed complexity of the 2-Flip algorithm. While we do not prove that using the 2-Flip algorithm on 2-Flip-Max-Cut achieves smoothed quasipolynomial time, we discuss multiple attempts at this goal, and hope to provide other researchers with the inspiration to prove quasipolynomial time."],"dc:description.degree":["M.Eng."],"dc:identifier.uri":["https://hdl.handle.net/1721.1/145081"],"dc:publisher":["Massachusetts Institute of Technology"],"dc:rights":["In Copyright - Educational Use Permitted","Copyright MIT"],"dc:rights.uri":["http://rightsstatements.org/page/InC-EDU/1.0/"],"dc:title":["Smoothed Complexity of Network Coordination Games"],"dc:type":["Thesis"],"thesis:degree_name":["Master","Master of Engineering in Electrical Engineering and Computer Science"]},"updated_at":"2026-07-22T22:22:31Z"}