2026-07-21T12:58:00Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24128 2025-11-12T13:33:23Z ddc:004 open_access

On the Performance of Mildly Greedy Players in k-Coloring Games Bilò, Vittorio D'Ascenzo, Andrea D'Emidio, Mattia Italiano, Giuseppe F. Coloring games (Approximate) Nash Equilibria Price of Anarchy We study the performance of mildly greedy players in k-coloring games, a relevant subclass of anti-coordination games. A mildly greedy player is a selfish agent who is willing to deviate from a certain strategy profile only if her payoff improves by a factor of more than ε, for some given ε ≥ 0. In presence of mildly greedy players, stability is captured by the concept of (1+ε)-approximate Nash equilibrium. In this paper, we first show that, for any k-coloring game, the (1+ε)-approximate price of anarchy, i.e., the price of anarchy of (1+ε)-approximate pure Nash equilibria, is at least (k-1)/((k-1)ε +k), and that this bound is tight for any ε ≥ 0. Then, we evaluate the approximation ratio of the solutions achieved after a (1 + ϵ)-approximate one-round walk starting from any initial strategy profile, where a (1 + ϵ)-approximate one-round walk is a sequence of (1 + ε)-approximate best-responses, one for each player. We provide a lower bound of min{(k-2)/k, (k-1)/((k-1)ε+k)} on this ratio, for any ε ≥ 0 and k ≥ 5; for the cases of k = 3 and k = 4, we give finer bounds depending on ε. Our work generalizes the results known for cut games, the special case of k-coloring games restricted to k = 2. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Vittorio Bilò and Andrea D'Ascenzo and Mattia D'Emidio and Giuseppe F. Italiano 2025 Is Part Of LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2025.21 urn:nbn:de:0030-drops-241287 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.21 eng https://creativecommons.org/licenses/by/4.0/legalcode