Worst-case equilibria in congestion games are fragile or efficient
On the Fragility of Worst-Case Nash Equilibria in Atomic Congestion Games
Computer Science and Game Theory
Summary
When many selfish people share limited resources, like roads, their individual choices can lead to traffic jams. This paper shows that the worst traffic jams happen only when people feel about the same about switching their routes as sticking to their current ones. In other words, either everyone is fairly happy with their routes and traffic is pretty good, or traffic is really bad but people could easily change to routes that improve things. The authors reveal that the worst situations are fragile and hardly stable because everyone is unsure about their choices.
What this means in practice
- •For traffic system designers: Improve traffic management by identifying when worst-case congestion equilibria are unstable and can be shifted toward better traffic flow.
- •For cloud resource managers: Predict fragile equilibria in resource allocation to design incentives that promote efficient and stable system-wide resource use.
A theory result. No direct application yet.
Authors
Colton Hill, Brandon Collins, Philip N. Brown
Abstract
Aggregate performance in smart mobility systems depends heavily on the emergent behavior of selfish, resource-sharing agents that participate within the systems. As a result, recent work has focused on how a system designer can leverage incentives to influence behavior so that system cost (e.g., traffic congestion) is minimized. These results show that worst-case equilibria can be quite inefficient compared to system-optimal allocations. However, it is unclear to what extent agents are ``satisfied'' with their decisions in these worst-case scenarios. We demonstrate that in any incentivized atomic congestion game, agents' aggregate satisfaction at equilibrium (relative to their actions in an optimal allocation) is correlated with the efficiency of the corresponding system cost, in the sense that if agents are very satisfied with their equilibrium choices, the equilibrium must be relatively efficient. Further, we show that worst-case Nash equilibria are fragile, as every agent is indifferent between their action in a worst-case equilibrium and their action in a system-optimal allocation. In summary, at equilibrium, either agents are highly satisfied with their decisions or their decisions are highly inefficient, but both cannot be true simultaneously. This work adds to recent results for other classes of games which indicate that worst-case equilibrium efficiency guarantees only occur when agents are indifferent about their decisions.