Monotonicity of equilibria in nonatomic congestion games

Abstract

Game theory ComonotonicitySingleton congestion games Wardrop equilibrium1. IntroductionDecision making in a multi-agent strategic context is prone to various paradoxes that are impossible in a single-agent framework. For instance, expanding the feasible choice set produces a better outcome in single-agent optimization, but, in a game, it may give rise to an equilibrium that is worse for all players. Analogously, more information is beneficial in single-agent decision making under risk, but may induce worse Bayes-Nash equilibria in a game.Several paradoxes arise in routing games. These games represent situations where roads to go from one origin to the corresponding destination are chosen strategically by travelers in a way that mini- mizes their traveling time. The nonatomic version of these games is a good approximation of situations with a large number of travelers. In nonatomic games the standard equilibrium concept, due to Wardrop (1952), prescribes that, for each OD pair, only the paths with the smallest traveling time are used and they all have the same traveling time. A famous paradox in routing games, due to Braess (1968), Braess et al. (2005), shows that adding an edge to a network can make the traveling time worse for all players. Other paradoxes arise in this class of games. For instance, although one could expect that an increase in traffic demand would make the traveling time higher across the network, this is not always the case. In fact, while Hall (1978) proved that – ceteris paribus – an increase in the demand of one OD pair increases the traveling time of this OD, Fisk (1979) showed that anincrease of traffic demand of one OD pair can be beneficial for some other OD pair by decreasing its traveling time. Even in networks with a single OD pair, an increment in the traffic demand may decrease the equilibrium load on some edges in the network. These paradoxes will be examined in detail in Examples 3 and 4.Networks in which the equilibrium loads of all the edges increase with the travel demand of every OD pair are more predictable and easier to handle for a social planner, because an edge is never used below a certain level of demand and is always used above that level. The goal of this paper is precisely to understand when the equilibrium travel times and edge loads are monotone in the demand, so that the paradoxical phenomena observed in the above examples cannot happen. Rather than focusing on routing games, we will state our results for the wider class of congestion games, of which routing games are a significant but particular example.1.1. Our resultsNonatomic congestion games are defined by a finite set of resources and a finite set of commodities. Each commodity has a demand that can be satisfied by different strategies in a strategy set, where each strategy is a subset of the resource set. In a Wardrop equilibrium each resource has a nonnegative load (a fraction of the total demand), which varies with the demand vector.ABSTRACTThis paper studies the monotonicity of equilibrium costs and equilibrium loads in nonatomic congestion games, in response to variations of the demands. The main goal is to identify conditions under which a paradoxical non-monotone behavior can be excluded. In contrast with routing games with a single commodity, where the network topology is the sole determinant factor for monotonicity, for general congestion games with multiple commodities the structure of the strategy sets plays a crucial role.We frame our study in the general setting of congestion games, with a special focus on singleton congestion games, for which we establish the monotonicity of equilibrium loads with respect to every demand. We then provide conditions for comonotonicity of the equilibrium loads, i.e., we investigate when they jointly increase or decrease after variations of the demands. We finally extend our study from singleton congestion games to the larger class of constrained series–parallel congestion games, whose structure is reminiscent of the concept of a series–parallel network.