The Complexity of Coordination

The traditional mechanism of finding Nash equilibria presumes that economic actors are capable of performing computations which even computers would take far too long to perform. A decentralized and parallel process of interactions between simple economic actors is presented as a more plausible micro-foundation of the concept of Nash equilibria. It is found that agent-interactions on a scale-free network converge to an equilibrium within reasonable time, however no convergence is found on a small-world network, a ring and a random graph. The structure of the relations between economic actors matters. NP computational complexity of Nash equilibria does not diminish its empirical relevance