Cascading to Equilibrium: Hydraulic Computation of Equilibria in Resource Selection Games
September 17, 2014
We present a novel construction, drawing intuition from a (physical) hydraulic system, constructively showing the existence of a strong Nash equilibrium in resource selection games with nonatomic players, the coincidence of strong equilibria and Nash equilibria in such games, and the invariance of the load on each given resource across all Nash equilibria. The existence proof allows for explicit calculation of a Nash equilibrium and for explicit and direct calculation of the resulting (invariant) loads on resources, and does not hinge on any fixed-point theorem, on the Minimax Theorem or any equivalent result, nor on the existence of a potential. A generalization of resource selection games, called resource selection games with ID-dependent weighting, is defined, and the results are extended to this family, showing that while resource loads are no longer invariant across Nash equilibria in games of this family, they are nonetheless invariant across all strong Nash equilibria. A natural application of the resulting machinery to a large class of constraint-satisfaction problems is also described.

This is joint work with Moshe Tennenholtz.