The Complexity of Coordination

Originally published in Eastern Economic Journal

It is found that agent interactions on a scale-free network converge to an equilibrium within reasonable time. NP computational complexity of Nash equilibria does not diminish its empirical relevance.

The traditional mechanism of finding Nash equilibria presumes economic actors are capable of performing computations that even computers would take far too long to complete. A decentralized and parallel process of interactions between simple economic actors is presented as a more plausible microfoundation of the concept of Nash equilibria. It is found that agent interactions on a scale-free network converge to an equilibrium within reasonable time. NP computational complexity of Nash equilibria does not diminish its empirical relevance.

Find the article at Springer Link.