2026-07-22T05:41:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11758 2024-03-06T10:48:38Z ddc:004 open_access

Smoothed Efficient Algorithms and Reductions for Network Coordination Games Boodaghians, Shant Kulkarni, Rucha Mehta, Ruta Network Coordination Games Smoothed Analysis 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(n^8)-time smoothed algorithm when k=2. These reductions extend smoothed efficient algorithms from one problem to another. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shant Boodaghians and Rucha Kulkarni and Ruta Mehta 2020 Is Part Of LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2020.73 urn:nbn:de:0030-drops-117581 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.73 eng https://creativecommons.org/licenses/by/3.0/legalcode