ﻻ يوجد ملخص باللغة العربية
The price of anarchy has become a standard measure of the efficiency of equilibria in games. Most of the literature in this area has focused on establishing worst-case bounds for specific classes of games, such as routing games or more general congestion games. Recently, the price of anarchy in routing games has been studied as a function of the traffic demand, providing asymptotic results in light and heavy traffic. The aim of this paper is to study the price of anarchy in nonatomic routing games in the intermediate region of the demand. To achieve this goal, we begin by establishing some smoothness properties of Wardrop equilibria and social optima for general smooth costs. In the case of affine costs we show that the equilibrium is piecewise linear, with break points at the demand levels at which the set of active paths changes. We prove that the number of such break points is finite, although it can be exponential in the size of the network. Exploiting a scaling law between the equilibrium and the social optimum, we derive a similar behavior for the optimal flows. We then prove that in any interval between break points the price of anarchy is smooth and it is either monotone (decreasing or increasing) over the full interval, or it decreases up to a certain minimum point in the interior of the interval and increases afterwards. We deduce that for affine costs the maximum of the price of anarchy can only occur at the break points. For general costs we provide counterexamples showing that the set of break points is not always finite.
This paper examines the behavior of the price of anarchy as a function of the traffic inflow in nonatomic congestion games with multiple origin-destination (O/D) pairs. Empirical studies in real-world networks show that the price of anarchy is close
We consider an atomic congestion game in which each player participates in the game with an exogenous and known probability $p_{i}in[0,1]$, independently of everybody else, or stays out and incurs no cost. We first prove that the resulting game is po
In this paper, we analyze a transportation game first introduced by Fotakis, Gourv`es, and Monnot in 2017, where players want to be transported to a common destination as quickly as possible and, in order to achieve this goal, they have to choose one
Algorithmic-matching sites offer users access to an unprecedented number of potential mates. However, they also pose a principal-agent problem with a potential moral hazard. The agents interest is to maximize usage of the Web site, while the principa
A basic lesson from game theory is that strategic behavior often renders the equilibrium outcome inefficient. The recent literature of information design -- a.k.a. signaling or persuasion -- looks to improve equilibria by providing carefully-tuned in