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 2565919573 1817264369 2364071307
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. Ride-sharing services are transforming urban mobility by providing timely and convenient transportation to anybody, anywhere, and anytime. These services present enormous potential for positive societ al impacts with respect to pollution, energy consumption, congestion, etc. Current mathematical models, however, do not fully address the potential of ride-sharing. Recently, a large-scale study highlighted some of the benefits of car pooling but was limited to static routes with two riders per vehicle (optimally) or three (with heuristics). We present a more general mathematical model for real-time high-capacity ride-sharing that ( i ) scales to large numbers of passengers and trips and ( ii ) dynamically generates optimal routes with respect to online demand and vehicle locations. The algorithm starts from a greedy assignment and improves it through a constrained optimization, quickly returning solutions of good quality and converging to the optimal assignment over time. We quantify experimentally the tradeoff between fleet size, capacity, waiting time, travel delay, and operational costs for low- to medium-capacity vehicles, such as taxis and van shuttles. The algorithm is validated with ∼3 million rides extracted from the New York City taxicab public dataset. Our experimental study considers ride-sharing with rider capacity of up to 10 simultaneous passengers per vehicle. The algorithm applies to fleets of autonomous vehicles and also incorporates rebalancing of idling vehicles to areas of high demand. This framework is general and can be used for many real-time multivehicle, multitask assignment problems. Dynamic ride-sharing systems enable people to share rides and increase the efficiency of urban transportation by connecting riders and drivers on short notice. Automated systems that establish ride-share matches with minimal input from participants provide the most convenience and the most potential for system-wide performance improvement, such as reduction in total vehicle-miles traveled. Indeed, such systems may be designed to match riders and drivers to maximize system performance improvement. However, system-optimal matches may not provide the maximum benefit to each individual participant. In this paper we consider a notion of stability for ride-share matches and present several mathematical programming methods to establish stable or nearly-stable matches, where we note that ride-share matching optimization is performed over time with incomplete information. Our numerical experiments using travel demand data for the metropolitan Atlanta region show that we can significantly increase the stability of ride-share matching solutions at the cost of only a small degradation in system-wide performance. The ubiquitous deployment of mobile and sensor technologies has led to both the capacity to observe human behavior in physical (offline) settings as well as to record it. This provides researchers with a new lens to study and better understand the individual decision processes that were previously unobserved. In this paper, we study decision making behavior of 11,196 taxi drivers in a large Asian city using a rich data set consisting of 10.6 million fine-grained GPS trip records. These records include detailed taxi GPS trajectories, taxi occupancy data (i.e., whether a taxi was occupied with a passenger or was vacant) and taxi drivers’ daily incomes. This capacity to use data where occupancy of the taxi is known is a distinctive feature of our data set and sets this work apart from prior work which has attempted to study driver behavior. The specific decision we focus on pertains to actions drivers take to find new passengers after they have dropped off their current passengers. In particular, we study the role of information derivable from the GPS trace data (e.g., where passengers are dropped off, where passengers are picked up, longitudinal taxicab travel history with fine-grained time stamps) observable by or made available to drivers in enabling them to learn the distribution of demand for their services over space and time. We conduct our study using a heterogeneous Bayesian learning model. We find strong heterogeneity in individual learning behavior and driving decisions, which is significantly associated with individual economic outcomes. Drivers with higher incomes benefit significantly from their ability to learn from not only demand information directly observable in the local market, but also aggregate information on demand flows across markets. Interestingly, our policy simulations indicate information that is noisy at the individual level becomes valuable after being aggregated across various spatial and temporal dimensions. Moreover, the value of information does not increase monotonically with the scale and frequency of information sharing. Finally, our study has important welfare implications in that efficient information sharing leads to an income increase among all drivers, instead of a redistribution of income between different types of drivers. Our work allows us not only to explain driver decision making behavior using these detailed behavioral traces, but also to prescribe information sharing strategy for the firm in order to improve the overall market efficiency.