Coordination failure, or agents' uncertainty about the action of other agents, may be an important source of congestion in large decentralized systems. The El Farol problem provides a simple paradigm for congestion and coordination problems that may arise with over utilization of the Internet. This paper reviews 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.
A. M. Bell, W. A. Sethares, and J. A. Bucklew, "Coordination failure as a source of congestion" IEEE Transactions on Signal Processing, Vol. 51. No. 3, March 2003. [Weak convergence analysis of a simple stochastic adaptive algorithm that solves the El Farol problem, emphasizing how agents' uncertainty about the actions of other agents may be a source of congestion in large decentralized systems.]
Casti calls the El Farol problem "the most important problem in complex adaptive systems." We argue why he's wrong, by showing that a very simple adaptive "solution" exists to this problem.
A. M. Bell and W. A. Sethares, ``Avoiding global congestion using decentralized adaptive agents" IEEE Transactions on Signal Processing, Vol. 49, No. 11, November 2001.
To get to my homepage, click here.