Network Formation Games and the Potential Function Method
Stub. Games where players build a network rather than route on a fixed one: local connection games, global connection games as potential games, and facility location, all analyzed via potential functions. (AGT ch. 19)
Contrasts with routing games: here players choose which edges/links to build (and share the cost of), not just which path to route flow along. The potential-function method — showing the game is an (exact or weighted) potential game — is the main tool for proving equilibria exist and bounding the price of anarchy, applied to local connection games, a global connection game, and facility location.
Outline (TODO — flesh out each)
- The local connection game
- Potential games and a global connection game
- Facility location as a network formation / potential game