Smoothed Complexity of Network Coordination Games

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.

Name thesis:degree_name

Master

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2022

Author dc:creator

• Viera, Julian T.

Advisor dc:contributor.advisor

• Daskalakis, Constantinos

Statement dc:rights

• In Copyright - Educational Use Permitted
• Copyright MIT

Licence dc:rights.uri

• http://rightsstatements.org/page/InC-EDU/1.0/

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/145081

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/145081