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
2054129049 1989072615 1567092208
In this paper, we introduce and analyze the properties of a class of games, the atomic congestion games on graphs (ACGGs), which is a generalization of the classical congestion games. In particular, an ACGG captures the spatial information that is often ignored in a classical congestion game. This is useful in many networking problems, e.g., wireless networks where interference among the users heavily depends on the spatial information. In an ACGG, a player's payoff for using a resource is a function of the number of players who interact with it and use the same resource. Such spatial information can be captured by a graph. We study fundamental properties of the ACGGs: under what conditions these games possess a pure strategy Nash equilibrium (PNE), or the finite improvement property (FIP), which is sufficient for the existence of a PNE. We show that a PNE may not exist in general, but that it does exist in many important special cases including tree, loop, or regular bipartite networks. The FIP holds for important special cases including systems with two resources or identical payoff functions for each resource. Finally, we present two wireless network applications of ACGGs: power control and channel contention under IEEE 802.11. We study the impact of combinatorial structure in congestion games on the complexity of computing pure Nash equilibria and the convergence time of best response sequences. In particular, we investigate which properties of the strategy spaces of individual players ensure a polynomial convergence time. We show that if the strategy space of each player consists of the bases of a matroid over the set of resources, then the lengths of all best response sequences are polynomially bounded in the number of players and resources. We also prove that this result is tight, that is, the matroid property is a necessary and sufficient condition on the players' strategy spaces for guaranteeing polynomial-time convergence to a Nash equilibrium. In addition, we present an approach that enables us to devise hardness proofs for various kinds of combinatorial games, including first results about the hardness of market sharing games and congestion games for overlay network design. Our approach also yields a short proof for the PLS-completeness of network congestion games. In particular, we show that network congestion games are PLS-complete for directed and undirected networks even in case of linear latency functions. 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 competitive resource allocation problems in which players distribute their demands integrally over a set of resources subject to player-specific submodular capacity constraints. Each player has to pay for each unit of demand a cost that is a non-decreasing and convex function of the total allocation of that resource. This general model of resource allocation generalizes both singleton congestion games with integer-splittable demands and matroid congestion games with player-specific costs. As our main result, we show that in such general resource allocation problems a pure Nash equilibrium is guaranteed to exist by giving a pseudo-polynomial algorithm computing a pure Nash equilibrium.