Papers for

traffic system designers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Worst-case equilibria in congestion games are fragile or efficient

On the Fragility of Worst-Case Nash Equilibria in Atomic Congestion Games

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.

Thu 10 SeptComputer Science and Game Theory
The gist
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.
Open 2609.12220v1