Near-Potential Games
ACM Transactions on Economics and Computation · 2013
DOI: 10.1145/2465769.2465776 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Economics and Computation, 2013. Verfasst von Ozan Candogan und 2 weiteren Autor:innen. Die Arbeit wurde bisher 30-mal zitiert (Crossref) und nennt 45 Literaturangaben. Gefördert von: Division of Electrical, Communications and Cyber Systems, Air Force Office of Scientific Research.
Abstract (Originalsprache)
Potential games are a special class of games for which many adaptive user dynamics converge to a Nash equilibrium. In this article, we study properties of near-potential games, that is, games that are close in terms of payoffs to potential games, and show that such games admit similar limiting dynamics. We first focus on finite games in strategic form. We introduce a distance notion in the space of games and study the geometry of potential games and sets of games that are equivalent, with respect to various equivalence relations, to potential games. We discuss how, given an arbitrary game, one can find a nearby game in these sets. We then study dynamics in near-potential games by focusing on continuous-time perturbed best response dynamics. We characterize the limiting behavior of this dynamics in terms of the upper contour sets of the potential function of a close potential game and approximate equilibria of the game. Exploiting structural properties of approximate equilibrium sets, we strengthen our result and show that for games that are sufficiently close to a potential game, the sequence of mixed strategies generated by this dynamics converges to a small neighborhood of equilibria whose size is a function of the distance from the set of potential games. In the second part of the article, we study continuous games and show that our approach for characterizing the limiting sets in near-potential games extends to continuous games. In particular, we consider continuous-time best response dynamics and a variant of it (where players update their strategies only if there is at least ε utility improvement opportunity) in near-potential games where the strategy sets are compact and convex subsets of a Euclidean space. We show that these update rules converge to a neighborhood of equilibria (or the maximizer of the potential function), provided that the potential function of the nearby potential game satisfies some structural properties. Our results generalize the known convergence results for potential games to near-potential games.
Förderung
- Division of Electrical, Communications and Cyber Systems
- Air Force Office of Scientific Research
Zitieren
APA
Candogan, O., Ozdaglar, A., & Parrilo, P. A. (2013). Near-Potential Games. ACM Transactions on Economics and Computation. https://doi.org/10.1145/2465769.2465776
Vancouver
Candogan O, Ozdaglar A, Parrilo PA. Near-Potential Games. ACM Transactions on Economics and Computation. 2013. doi:10.1145/2465769.2465776
BibTeX
@article{Candogan2013,
author = {Candogan, Ozan and Ozdaglar, Asuman and Parrilo, Pablo A.},
title = {Near-Potential Games},
journal = {ACM Transactions on Economics and Computation},
year = {2013},
doi = {10.1145/2465769.2465776}
}
EUVIMED