In this study, we formulate positive and negative externalities caused by changes in the supply of shared vehicles as ride sharing games. The study aims to understand the price of anarchy (PoA) and its improvement via a coordination technique in ride sharing games. A critical question is whether ride sharing games exhibit a pure Nash equilibrium (pNE) since the PoA bound assumes it. Our result shows a sufficient condition for a ride sharing game to have a finite improvement property and a pNE similar to potential games. This is the first step to analyze PoA bound and its improvement by coordination in ride sharing games. We also show an example of coordinating players in ride sharing games using signaling and evaluate the improvement in the PoA.
Since Rosenthal introduced the congestion game @cite_0 , it has been applied to problems of congestion externalities in several areas such as transportation and communication networks @cite_12 . In this game, players choose a combination of resources and the players' payoffs depend on the congestion level, i.e., the number of players using the same resources. The congestion game is a subclass of potential games, which feature the finite improvement property (FIP). This property guarantees that if each player updates his strategy in response to other players by turns, it will reduce his private cost and improve the common potential function, which eventually reaches a local minimum, the pure Nash equilibrium (pNE), where each player has a deterministic strategy. Because of this property, potential and congestion games have been well studied and have wide applications @cite_2 .
@cite_0 @cite_12 @cite_2
2148042342 2070173191 2076641899 2134373565
Congestion games are multi-player games in which players' costs are additive over a set of resources that have anonymous cost functions, with pure strategies corresponding to certain subsets of resources. In a splittable congestion game, each player can choose a convex combination of subsets of resources. We characterize the worst-case price of anarchy — a quantitative measure of the inefficiency of equilibria — in splittable congestion games. Our approximation guarantee is parameterized by the set of allowable resource cost functions, and degrades with the “degree of nonlinearity” of these cost functions. We prove that our guarantee is the best possible for every set of cost functions that satisfies mild technical conditions. We prove our guarantee using a novel “local smoothness” proof framework, and as a consequence the guarantee applies not only to the Nash equilibria of splittable congestion games, but also to all correlated equilibria. We study congestion games where players aim to access a set of resources. Each player has a set of possible strategies and each resource has a function associating the latency it incurs to the players using it. Players are non--cooperative and each wishes to follow a strategy that minimizes her own latency with no regard to the global optimum. Previous work has studied the impact of this selfish behavior on system performance. In this article, we study the question of how much the performance can be improved if players are forced to pay taxes for using resources. Our objective is to extend the original game so that selfish behavior does not deteriorate performance. We consider atomic congestion games with linear latency functions and present both negative and positive results. Our negative results show that optimal system performance cannot be achieved even in very simple games. On the positive side, we show that there are ways to assign taxes that can improve the performance of linear congestion games by forcing players to follow strategies where the total latency suffered is within a factor of 2 of the minimum possible; this result is shown to be tight. Furthermore, even in cases where in the absence of taxes the system behavior may be very poor, we show that the total disutility of players (latency plus taxes) is not much larger than the optimal total latency. Besides existential results, we show how to compute taxes in time polynomial in the size of the game by solving convex quadratic programs. Similar questions have been extensively studied in the model of non-atomic congestion games. To the best of our knowledge, this is the first study of the efficiency of taxes in atomic congestion games. 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. A network congestion game is played on a directed, two-terminal network. Every player chooses a route from his origin to his destination. The cost of a route is the sum of the costs of the arcs on it. The arc cost is a function of the number of players who use it. Rosenthal proved that such a game always has a Nash equilibrium in pure strategies. Here we pursue a systematic study of the classes of networks for which a strong equilibrium is guaranteed to exist, under two opposite monotonicity assumptions on the arc cost functions. Our main results are: (a) If costs are increasing, strong equilibrium is guaranteed on extension-parallel networks, regardless of whether the players’ origins and destinations are the same or may differ. (b) If costs are decreasing, and the players have the same origin but possibly different destinations, strong equilibrium is guaranteed on series-parallel networks. (c) If costs are decreasing, and both origins and destinations may differ, strong equilibrium is guaranteed on multiextension-parallel networks. In each case, the network condition is not only sufficient but also necessary in order to guarantee strong equilibrium. These results extend and improve earlier ones by Holzman and Law-Yone in the increasing case, and by in the decreasing case.