Coordination Failure and Congestion in Information Networks

Book One

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 17

Agents

Coordination failure, or agents’ uncertainty about the action of other agents, may be an important source of congestion in large decentralized systems. The market entry game studied by experimental economists and the El Farol problem proposed by W. Brian Arthur provide a simple paradigm for congestion and coordination problems that may arise with over utilization of the Internet. This paper reviews the market entry game and the El Farol problem and surveys previous approaches, which typically involve complex deterministic learning algorithms that exhibit chaotic-like trajectories. This paper recasts the problem in a stochastic framework and derives a simple adaptive strategy that has intriguing optimization properties; a large collection of decentralized decision makers, each acting in their own best interests and with limited knowledge, converge to a solution that (optimally) solves a complex congestion and social coordination problem. A variation in which agents are allowed access to full information is not nearly as successful. The algorithm, which can be viewed as a kind of habit formation, is analyzed using a weak convergence approach, and simulations illustrate the major results.