Fast and Compact: A Simple Class of Congestion Games
Abstract
We study a simple, yet rich subclass of congestion games that we call singleton games. These games are exponentially more compact than general congestion games. In contrast with some other compact subclasses, we show tractability of many natural game-theoretic questions, such as finding a sample or optimal Nash equilibrium. For best- and better-response dy-namics, we establish polynomial upper and lower bounds on the rate of convergence and present experimental results. We also consider a natural generalization of singleton games and show that many tractability results carry over.
Cite
Text
Ieong et al. "Fast and Compact: A Simple Class of Congestion Games." AAAI Conference on Artificial Intelligence, 2005.Markdown
[Ieong et al. "Fast and Compact: A Simple Class of Congestion Games." AAAI Conference on Artificial Intelligence, 2005.](https://mlanthology.org/aaai/2005/ieong2005aaai-fast/)BibTeX
@inproceedings{ieong2005aaai-fast,
title = {{Fast and Compact: A Simple Class of Congestion Games}},
author = {Ieong, Samuel and McGrew, Robert and Nudelman, Eugene and Shoham, Yoav and Sun, Qixiang},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2005},
pages = {489-494},
url = {https://mlanthology.org/aaai/2005/ieong2005aaai-fast/}
}