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.
According to a review of sharing studies in transportation areas @cite_14 , there are few game theory studies on externalities and coordination of players' moves in vehicle sharing problems. Traditional studies on sharing include the optimization of vehicle routes for picking up all passengers (the Dial-a-ride problem ), problems of splitting passengers' fares according to their riding distances, optimization of locations of carpool stations, and problems of relocation of carpool vehicles among stations. Those studies mainly focus on optimization problems under given moves (origins and destinations) of passengers and fixed drivers of vehicles, and therefore, do not analyze the PoA when passengers strategically choose their moves in response to the moves of other passengers and vehicles. The review states that there are no studies on coordination of players' moves to improve the efficiency of sharing or reduce the PoA.
@cite_14
2614461528
Optimizing shared vehicle systems (bike-sharing car-sharing ride-sharing) is more challenging compared to traditional resource allocation settings due to the presence of complex network externalities. In particular, changes in the demand supply at any location (via dynamic pricing, rebalancing of empty vehicles, etc.) affect future supply throughout the system within short timescales. Such externalities are well captured by steady-state Markovian models, which are therefore widely used to analyze and design shared vehicle systems. However, using such models to design pricing control policies is computationally difficult since the resulting optimization problems are high-dimensional and non-convex. To this end, we develop a general approximation framework for designing pricing policies in shared vehicle systems, based on a novel convex relaxation which we term elevated flow relaxation. Our approach provides the first efficient algorithms with rigorous approximation guarantees for a wide range of objective functions (throughput, revenue, welfare). For any shared vehicle system with @math stations and m vehicles, our framework provides a pricing policy with an approximation ratio of 1+(n-1) m. This guarantee is particularly meaningful when m n, the average number of vehicles per station is large, as is often the case in practice. Further, the simplicity of our approach allows us to extend it to more complex settings. Apart from pricing, shared vehicle systems enable other control levers for modulating demand and supply, e.g. rebalancing empty vehicles, redirecting riders to nearby vehicles, etc. Our approach yields efficient algorithms with the same approximation guarantees for all these problems, and in the process, obtains as special cases several existing heuristics and asymptotic guarantees. We also extend our approach to obtain bi-criterion guarantees in multi-objective settings; we illustrate this with the example of Ramsey pricing. From a technical perspective, our work develops a new approach for obtaining control policies with approximation guarantees in steady-state Markovian models. Our approach can be distilled into the following three-step program: (i) construct an upper bound via a relaxation to the original problem that encodes essential conservation laws of the system, (ii) identify a family of control policies inducing known steady-state distributions that achieve the value of the relaxed solution in an appropriate scaling limit (in our case, state-independent policies in the limit m++), and (iii) characterize the performance loss between the finite system (i.e. fixed m) and the scaling limit. This technique may be of independent interest for other settings.