Local-Effect Games

Leyton-Brown, Kevin; Tennenholtz, Moshe

Local-Effect Games

Download BibTeX Cite

Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence. Pages 772-779.

Abstract

We present a new class of games, local-effect games (LEGs), which exploit structure in a different way from other compact game representations studied in AI. We show both theoretically and empirically that these games often (but not always) have pure-strategy Nash equilibria. Finding a potential function is a good technique for finding such equilibria. We give a complete characterization of which LEGs have potential functions and provide the functions in each case; we also show a general case where pure-strategy equilibria exist in the absence of potential functions. In experiments, we show that myopic best-response dynamics converge quickly to pure strategy equilibria in games not covered by our positive theoretical results.

Kevin Leyton-Brown, and Moshe Tennenholtz. 2003. Local-Effect Games. In Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, IJCAI-03. IJCAI, 772–779. https://ijcai.org/proceedings/2003/112

@inproceedings{ijcai2003p112,
  title     = {Local-Effect Games},
  author    = {Leyton-Brown, Kevin and Tennenholtz, Moshe},
  booktitle = {Proceedings of the Eighteenth International Joint Conference on
               Artificial Intelligence, {IJCAI-03}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Georg Gottlob},
  pages     = {772--779},
  year      = {2003},
  url       = {https://ijcai.org/proceedings/2003/112},
}

TY  - CPAPER
TI  - Local-Effect Games
AU  - Leyton-Brown, Kevin
AU  - Tennenholtz, Moshe
T2  - Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, IJCAI-03
PB  - International Joint Conferences on Artificial Intelligence
PY  - 2003
SP  - 772
EP  - 779
UR  - https://ijcai.org/proceedings/2003/112
ER  -