Fast and Compact: A Simple Class Of Congestion Games

Samuel Ieong, Robert McGrew, Eugene Nudelman, Yoav Shoham, Qixiang Sun

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 dynamics, 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.

Content Area: 7.Game Theory and Economic Models

Subjects: 7.1 Multi-Agent Systems; 9.2 Computational Complexity

Submitted: May 10, 2005

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.