One household on a street buys a hedge trimmer and the neighbours borrow it; nobody else needs to. Who ends up buying depends entirely on who is next to whom. Structure, not just preferences, decides the outcome.
Network and graphical games
When payoffs depend only on your neighbours, a game lives on a graph. Graphical games make network structure the star: the same simple rule produces very different outcomes on a star, a cycle, or a hub, and local best responses can often find an equilibrium without any global solver.
In a public-goods problem, the benefit of contributing is...
One more car joins a crowded route. Whose travel time can change?
Predict, then play
A best-shot public good: each node can pay 1 to provide something worth 2 to itself and its neighbours. A node is content providing only if no neighbour does. Toggle nodes, then let them best-respond.
Why did that happen?
Take a guess, then reveal the reason
The good only needs to be provided once within each neighbourhood. On a star, the hub touches everyone, so if the hub provides, the whole network is covered and every leaf can free-ride. On a cycle, no single node reaches everyone, so providers must be spaced out: two opposite nodes are enough to cover all six, and running best responses from an empty network lands on the alternating three. Same incentives, same rule, but the graph’s shape sets how many providers are needed and who they are.
The math
A graphical game places players on a graph so that each player’s payoff depends only on its own action and its neighbours’. This makes the game compact to describe and often tractable to solve, since local structure can be exploited. In the best-shot public-goods game, a pure Nash equilibrium is exactly a maximal independent set of providers: no two providers are adjacent (that would waste a contribution), and every non-provider has a provider neighbour (or it would rather provide itself).
Each node’s best response: provide if and only if no neighbour provides. In equilibrium the providers form an independent set (none adjacent) that is maximal (every other node is adjacent to a provider). On a star, the hub alone is a maximal independent set, so one node provides and society’s cost is . On a six-cycle no node covers all the others, so every maximal independent set has at least two members: two opposite nodes suffice (cost ), while the alternating set of three is also maximal (cost ). Which one you land on depends on where the dynamics start, and from an empty network they reach the three.
Local payoffs make the game compact to describe, but locality alone does not guarantee that arbitrary best-response dynamics converge. The button uses one fixed sequential update order and reports whether the resulting state is an equilibrium.
Work it out
Star versus cycle
On the star, suppose the hub provides. Every leaf has the hub as a neighbour, so each leaf is content to free-ride (a provider neighbour exists), and the hub, whose only neighbours are non-providing leaves, is content to provide. That is a maximal independent set of size : the whole street served for a cost of .
On the six-cycle, try one provider: the node opposite it has no providing neighbour, so it would rather provide, breaking the profile. Add it and you have two opposite providers, an independent set (they are not adjacent) that is maximal (each of the four remaining nodes touches one). Cost , and that is the cheapest equilibrium. Run best responses from an empty network instead and the nodes take turns: the first sees no provider and provides, its two neighbours then free-ride off it, the next uncovered node provides, and the sweep settles on the alternating three, cost . Either way the cycle costs more than the star, purely because it has no hub to cover everyone at once.
Key idea
In a graphical game, payoffs depend only on neighbours, so network structure drives the outcome. In best-shot public goods, equilibria are maximal independent sets, and a hub can serve everyone while a cycle needs several providers.
Check yourself
Sources
- Kearns, M., Littman, M. L., and Singh, S. (2001). Graphical models for game theory. Proceedings of UAI, 253-260.