We aim to reduce the social cost of congestion in many smart city applications. In our model of congestion, agents interact over limited resources after receiving signals from a central agent that observes the state of congestion in real time. Under natural models of agent populations, we develop new signalling schemes and show that by introducing a non-trivial amount of uncertainty in the signals, we reduce the social cost of congestion, i.e., improve social welfare. The signalling schemes are efficient in terms of both communication and computation, and are consistent with past observations of the congestion. Moreover, the resulting population dynamics converge under reasonable assumptions.
In the transportation literature, @cite_17 introduces the notion of equilibrium as the limit of the congestion distribution if it exists. @cite_5 considers a number of notions of noisy signals and studies greedy policies and equilibria. Our approach is also related to signalling of parking space availability @cite_2 .
@cite_5 @cite_2 @cite_17
2072113937 2076641899 2084281377 1554620983
In the traffic assignment problem, first proposed by Wardrop in 1952, commuters select the shortest available path to travel from their origins to their destinations. We study a generalization of this problem in which competitors, who may control a nonnegligible fraction of the total flow, ship goods across a network. This type of games, usually referred to as atomic games, readily applies to situations in which the competing freight companies have market power. Other applications include intelligent transportation systems, competition among telecommunication network service providers, and scheduling with flexible machines. Our goal is to determine to what extent these systems can benefit from some form of coordination or regulation. We measure the quality of the outcome of the game without centralized control by computing the worst-case inefficiency of Nash equilibria. The main conclusion is that although self-interested competitors will not achieve a fully efficient solution from the system's point of view, the loss is not too severe. We show how to compute several bounds for the worst-case inefficiency that depend on the characteristics of cost functions and on the market structure in the game. In addition, building upon the work of Catoni and Pallotino, we show examples in which market aggregation (or collusion) adversely impacts the aggregated competitors, even though their market power increases. For example, Nash equilibria of atomic network games may be less efficient than the corresponding Wardrop equilibria. When competitors are completely symmetric, we provide a characterization of the Nash equilibrium using a potential function, and prove that this counterintuitive phenomenon does not arise. Finally, we study a pricing mechanism that elicits more coordination from the players by reducing the worst-case inefficiency of Nash equilibria. Abstract 6 introduced the class of congestion games and proved that they always possess a Nash equilibrium in pure strategies. Here we obtain conditions for the existence of a strong equilibrium in this class of games, as well as for the equivalence of Nash and strong equilibria. We also give conditions for uniqueness and for Pareto optimality of the Nash equilibrium. Except for a natural monotonicity assumption on the utilities, the conditions are expressed only in terms of the underlying congestion game form. It turns out that avoiding a certain type of bad configuration in the strategy spaces is essential to positive results. Journal of Economic Literature Classification Numbers: C71, C72, D62. As the provision of roads has become market driven, many intriguing issues have emerged, such as the strategic interactions among private firms in determining road supply and pricing in a network and, more importantly, the resulting inefficiencies when competition substitutes for government regulation. This paper studies both toll and capacity competition among private asymmetric roads with congestion in a network with parallel links. We find that oligopolistic competition yields higher tolls but lower construction capacities than the socially optimal levels and, as a result, the level of traffic congestion does not decline. Based on some widely used assumptions, we show that the usage or the congestion level of each road controlled by each private firm, represented by the volume-capacity (v c) ratio, is independent of the other competitors' choices of capacities and tolls in the oligopolistic market. To quantify the inefficiency of the oligopolistic equilibria via higher tolls and less realized traffic demand, we establish the upper bound of the ratio of the social welfare between the competitive equilibrium and the social optimum. The inefficiency bound depends mainly on the marginal benefit of trip-makers and the realized traffic demand at equilibrium on the private roads. Exact bounds are given by considering both the worst and symmetric cases. Naturally, our results show that the distortion disappears when the oligopoly changes to perfect competition. We present a short geometric proof for the price of anarchy results that have recently been established in a series of papers on selfish routing in multicommodity flow networks. This novel proof also facilitates two new types of results: On the one hand, we give pseudo-approximation results that depend on the class of allowable cost functions. On the other hand, we derive improved bounds on the inefficiency of Nash equilibria for situations in which the equilibrium travel times are within reasonable limits of the free-flow travel times. These tighter bounds help to explain empirical observations in vehicular traffic networks. Our analysis holds in the more general context of congestion games, which provides the framework in which we describe this work.