Smoothed efficient algorithms and reductions for network coordination games

Shant Boodaghians, Rucha Kulkarni, Ruta Mehta

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We study the smoothed complexity of finding pure Nash equilibria in Network Coordination Games, a PLS-complete problem in the worst case, even when each player has two strategies. This is a potential game where the sequential-better-response algorithm is known to converge to a pure NE, albeit in exponential time. First, we prove polynomial (respectively, quasi-polynomial) smoothed complexity when the underlying game graph is complete (resp. arbitrary), and every player has constantly many strategies. The complete graph assumption is reminiscent of perturbing all parameters, a common assumption in most known polynomial smoothed complexity results. We develop techniques to bound the probability that an (adversarial) better-response sequence makes slow improvements to the potential. Our approach combines and generalizes the local-max-cut approaches of Etscheid and Röglin (SODA ‘14; ACM TALG, ‘17) and Angel, Bubeck, Peres, and Wei (STOC ‘17), to handle the multi-strategy case. We believe that the approach and notions developed herein could be of interest in addressing the smoothed complexity of other potential games. Further, we define a notion of a smoothness-preserving reduction among search problems, and obtain reductions from 2-strategy network coordination games to local-max-cut, and from k-strategy games (k arbitrary) to local-max-bisection. The former, with the recent result of Bibak, Chandrasekaran, and Carlson (SODA ‘18) gives an alternate O(n8)-time smoothed algorithm when k = 2. These reductions extend smoothed efficient algorithms from one problem to another.

Original languageEnglish (US)
Title of host publication11th Innovations in Theoretical Computer Science Conference, ITCS 2020
EditorsThomas Vidick
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771344
DOIs
StatePublished - Jan 2020
Event11th Innovations in Theoretical Computer Science Conference, ITCS 2020 - Seattle, United States
Duration: Jan 12 2020Jan 14 2020

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume151
ISSN (Print)1868-8969

Conference

Conference11th Innovations in Theoretical Computer Science Conference, ITCS 2020
CountryUnited States
CitySeattle
Period1/12/201/14/20

Keywords

  • Network coordination games
  • Smoothed analysis

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Smoothed efficient algorithms and reductions for network coordination games'. Together they form a unique fingerprint.

Cite this