A Mechanism for Dynamic Ride Sharing Based on Parallel Auctions

1 Introduction

Road transportation is one of the major challenges for the new millennium, as the current transportation models are both not environmentally and socially sustainable. On the one hand, car pollution is a major source of greenhouse emissions (see for example [European Commission, 2010]) that, in turn, is a cause of global climate change. On the other hand, traffic congestions are a world-wide problem and are believed to yield to a reduction of people's quality of life [European Conference of Ministers of Transport, 1999]. Apparently, there is plenty of room for improvements, for example, when considering the fact that on average cars carry 1.6 passengers, i.e., only an estimated 25% of emissions are caused by people traveling, and the rest by moving "empty seats" [Jeanes, 2010]. Many researchers, spanning over multiple disciplines such as transportation [Morency, 2007], economics [Brownstone and Golob, 1992], and behavioral, social and environmental psychology [Nordlund and Garvill, 2003], have identified ride sharing as a solution to the inefficiency of current transportation models.

∗The authors are grateful to Robert Mattm¨uller for the extensive discussions and useful suggestions.

To date, DRS systems (e.g., www.avego.com and www. carticipate.com) are not capable of retaining a critical mass of users. The experience from previous projects (see dynamicridesharing.org for a discussion on the topic) highlights that major drawbacks of existing systems are related to flexibility in usage, e.g., allowing people to decide with whom they share a ride, and to high availability, as, on average, if users do not get a ride within the first three attempts, they will not return. In order to provide high availability of service, a DRS system must be able to provide adequate incentives to users and, in particular, to drivers. Kamar and Horvitz [Kamar and Horvitz, 2009] recently proposed the ABC DRS system that dynamically generates shared plans and computes fair payments using a VCG mechanism [Nisan et al., 2007] as incentives for the users. However, besides fair payments (which are not incentive compatible) their system does not provide the required flexibility, as users have no influence on their assignments.

In this paper we present a DRS solution based on auctions with a second-price scheme. In contrary to existing solutions, the proposed mechanism facilites both individual user preferences for ride sharing partners and personal valuations for specific rides. In colloquial terms, passengers are bidding for increasing their ranking, and thus visibility to drivers, whereas drivers can select passengers according to their preferences. From the perspective of a single driver, potential passengers can require different detours for being picked-up.

One important feature of our system is that it allows to tradeoff the minimization of Vehicle Kilometers Travelled (VKT), i.e. greenhouse emissions, with the overall probability of successful ride-shares. On the one hand side, the auction mechanism automatically increases the chances of passengers bidding with higher valuation since their bid might cover the detour costs of several drivers. On the other hand side, longer detours are increasing the overall VKTs. We show empirically that the variance in valuation and thus the potential detour distances impacts both the probability for ride-shares and the amont of saved VKTs. In fact, we show that the lower the variance the closer the system performs towards the optimal assignment in terms of VKT savings. This opens the door for regulating the tradeoff, which is an important feature particularly for bootstrapping the system. For example, permitted detour distances can be kept unbounded at the beginning and then stepwise be decreased during the life-time of the system in order to minimize VKTs.

The presented approach is related to the generalized second-prize auctions (GSP) [Edelman et al., 2007] (also known as Position Auctions [Varian, 2007]), used by Yahoo! and Google to assign advertisement slots within web search results [Battelle, 2005]. In general, it is very difficult to obtain both efficiency and incentive compatibility in a GSP, as for example the aforementioned ad auctions are not incentive compatible. We show that our approach is incentive compatible for passenger bids.

The paper is structured as follows. First, in Section 2, we provide a brief overview of our DRS system. Then, in Section 3, we provide a formal characterization of our system and we show that it is incentive compatible. In Section 3.3, we describe our approach on dealing with the dynamic nature of the problem. In Section 4, we describe an optimal, yet strict, assignment method that we use as a baseline for the evaluation of our system. In Section 5, we provide empirical results, and in Section 6, we conclude with some discussion.

2 SystemOverview

The target system of our DRS approach is a smartphone application for dynamic ride-sharing that operates in real-time, does not require pre-declared paths or pickup points, and can be used from virtually any location at any time. The system promotes ride-shares among people with connections within social networks (e.g., Facebook) in order to favor ride-shares among users that trust each other. From a passenger's perspective, the DRS system is like an "eBay of rides". When the application is launched on a smartphone, the user is asked to enter a goal location, a deadline, and to place a bid. Then, the system determines drivers that are online and compatible for this ride based on the length of the detour to be performed, and whether deadlines will comply. The passenger can then select from the list of compatible drivers, which are presented with additional information such as user ratings and social network status. Finally, these drivers will receive the bid, which is considered as a binding commitment of the passenger, i.e., to accept the first driver that accepts. After the ride, the passenger has the possibility to review the driver, for example, by a rating (zero to five stars), and optionally a comment.

From a driver's perspective, the DRS system may be thought as a GPS car navigation system connected to a social network. The driver, just before starting to drive, declares a goal location, and a deadline. Then, the system computes the shortest path and gives directions to the driver for reaching the goal. During the ride the driver may be informed, e.g. vocally, about ride sharing offers from passengers nearby to his route. For example, the systemmight announce that there are three bids and the best one offers a profit of e10 for a detour of 15 minutes (computed by the system). The systemmay also announce that there is a bidding passenger that is a remote friend according to a social network graph, e.g. Facebook, and that other drivers rated him on average with four stars out of five. The driver may accept the first bid or request information on the next bid. Note that the cognitive load of the driver can be reduced by a set of individually adjustable preferences that filter-out uninteresting offers beforehand. When the driver accepts an offer, the application changes the route according to the optimal joint route of both. At the end of the trip, the system automatically performs the payment and the driver has also the possibility to review the passenger.

The implementation of the system is still ongoing work. For our feasibility study we implemented a server platform than can simulate offers and demands from drivers and passengers based on the road network of any city in the world. Furthermore, we implemented a client application running on the Android mobile phone architecture for accessing this data from the road.

3 Multi-Agent DRS System

The DRS system may be thought of as a multi-agent system composed of selfish agents that dynamically enter and exit the system. Agents can enter the system either as passengers or as drivers, and exit when they share a ride, reach their goal locations, or meet their deadline. For the purpose of this paper, we assume that only one passenger can be assigned to (i.e., share a ride with) one driver. The proposed system can generally be extended for assigning multiple passengers to a single driver. However, then the computational complexity for computing all possible roundtrips (in the worst case (n-1)!/2) increases, which necessitates the deployment of heuristic algorithms, such as for example ant colony optimization [Dorigo and Gambardella, 1997].

The goal of our system is twofold. On the one hand, to minimize the greenhouse emissions by minimizing VKTs and on the other hand, to increase the number of ride-matches by providing an incentive compatible mechanism.

3.1 Agents

We denote by At the set of agents that are in the system at time t. Each agent a ∈ At has associated a type 〈s(a,t), g(a,t), dl(a,t)〉, where s(a,t), g(a,t) and dl(a,t) are, respectively, the current position, the goal position and the deadline for reaching the goal of a at time t.

The set At of agents in the system at time t is partitioned in two sets:

• the set of drivers Dt at time t, i.e. the set of people that have a car and are willing to drive it;
• the set of passengers Pt at time t, i.e. the set of people that either do not have a car, or they have it, but are not willing to drive it.

Figure 1 shows the single paths of the driver and passenger if driving alone (left side) and the path required if they decide to share a ride (right side). It can easily be shown that in some cases the joint route is significantly shorter than the sum of both. For example, in case that both have the same goal at a far distance and their starting locations are located in the same neighborhood.

The estimated duration of a ride share is, in general, different for the passenger and the driver as the driver has to travel an extra path. We define these durations as follows:

• durationp(d, p), i.e., the time required to drive by car the shortest path going through s(d,t), s(p,t) and g(p,t);
• durationd(d, p), i.e., the time required to drive by car the shortest path going through s(d,t), s(p,t), g(p,t) and g(d,t) .

In order for a passenger and a driver to share a ride, their deadlines must be compatible with respect to the time required to drive to their goal locations. For each point in time t and for each passenger p ∈ Pt, we define the set C(p,t) composed of all drivers di ∈ Dt that are compatible with p, i.e. (durationp(d, p) < dl(p,t) - t) ∧ (durationd(d, p) < dl(d,t) - t).

Let us define cdkm as the cost per km of a driver. Moreover, we define len(p, p′ ) as the length of the shortest path that leads from position p to position p′ by car in km. For convenience of notation, we define the length of the path for the passenger lp(p) = len(s(p,t), g(p,t)), the length of the original path of the driver ld(d) = len(s(d,t), g(d,t)), and the overall path of the ride share lt(d, p) = len(s(d,t), s(p,t)) + len(s(p,t), g(p,t)) + len(g(p,t), g(d,t)).

A ride share 〈d, p〉t is the assignment to a passenger p ∈ Pt of a driver d ∈ C(p,t) at time t. The valuation of the ride share 〈d, p〉t is

for driver d, while the passenger p values a ride from s(p,t) to g(p,t) with

Notice that the valuation of the ride share for a driver is always not positive, as he may usually have to drive a longer distance to fetch the passenger and deliver him to his goal location.

3.2 AuctionMechanism

The auction mechanism is used to provide a ranking for each driver of the bids received from passengers. Agents when entering the system announce their types. Additionally, passengers announce a bid bp for their rides, which they are willing to pay. In the end, the mechanism ensures that passenger p will pay an amount payp ≤ bp. From specific user preferences and a social distance measure derivable from Facebook or similar means, we assume a function vald(p) returning the value driver d assigns to passenger p. Based on that, the utility for a ride share 〈d, p〉t for the passenger is

and for the driver is

For each passenger p, the system computes the target drivers to whom the bid of p is forwarded:

The bids are ranked for each driver based on the utility functions ud(〈d, p〉t, bp). If the value vald(p) has captured all non-monetary preferences of the driver, the system could just select the passenger on the first rank as the winner of the auction. Notice that translating preferences into a singledimension utility value is quite common in economics. Of course, one could also use multi-criteria preferences with the effect that outcomes are not comparable.

Alternatively, we consider the case that the final decision on who gets the ride is made by the driver by selecting a passenger from the list. In an auction, the bids of the passenger are ordered by the utility of the driver, provided the passengers would actually pay their bid: bp1 , bp2 , . . . , bpn . The passenger that wins an auction, has to pay according to a second price scheme. The winner pi with bid bpi has to pay to the driver paypi , which is the sum of

• -vd(〈d, pi〉t) i.e., the detour cost;
• vd(〈d, pi+1〉t) + bpi+1 + vald(pi+1) i.e., the utility of the ride share with passenger pi+1, provided that pi+1 is the next passenger in the ranking of the auction and that pi+1 would have paid the bid bp+1;
• -vald(pi) i.e, the negative valuation of the presence of pi for the driver.

Notice that negative payments are not possible. In order to be an eligible passenger (see the definition of the set T (p, t)), the utility has to be positive. In particular, even if we would have only the one eligible passenger, he would have to pay the price the he bid - as is the usual way in 2-nd price auctions when there is only one bidder.

3.3 Computation of Dynamic Assignments

In the dynamic ride sharing setting, announcements of passengers (e.g. bids) and drivers are arriving continuously at arbitrary times. Hence, matches between passengers and drivers have to be computed many times during the day which implies that future requests are unknown during each planning cycle. Figure 2 depicts this problem from the perspective of a single driver that receives announcements (circles in the figure) with deadlines (diamonds in the figure) from passengers {p1, . . . , p5}. Regardless of the assignment mechanism, the problem is to decide an appropriate point in time for computing and committing the assignment between drivers and passengers. By computing we specifically mean to decide the best assignment given the current knowledge, e.g., to compute the current ranking of bids for each driver. By committing we mean to let the assignment come into effect, either automatically or by presenting a ranked list of potential passengers to the drivers, which then finally commit a decision by selecting one or none of the passengers on the list.

A common method to solve problems of this kind is the deterministic rolling horizon approach [Sethi and Sorger, 1991], by which assignments are computed using all known information within a planning horizon, but decisions are only committed when necessitated by a deadline. As depicted by the dotted vertical lines in Figure 2, computations are triggered when the planning horizon grows due to deadlines from new passenger announcements. As shown by the bold vertical line in Figure 2, a decision is made shortly before the deadline of passenger 3 expires. Notice that deadlines always expire before passengers and drivers change from being compatible to being incompatible due to (durationp(d, p) > dlp - t) ∨ (durationd(d, p) > dld - t).

3.4 Incentive Compatibility

One desirable property of such a system is that it is incentive compatible, i.e. that it is rational for each user to state his type and preferences truthfully. Let us consider the driver's type first.

The starting position s(a,t) is something the driver hardly can cheat about because it is known by the system. The deadline and the goal location may be something the driver could lie about. However, stating an earlier deadline only limits the number of possible passengers and stating a later deadline might lead to a late arrival. Lying about the goal could potentially change the payment to the driver. However, since the payment is computed automatically, this computation could be done when the driver has finished his trip. If his goal location has changed, the auction payment could be re-evaluated. So, lying about the goal would not help.

Using the perspective of the passenger, the type is again something one hardly would be untruthful about. It does not make sense to lie about starting and goal location. Similarly, the deadline should be stated truthfully because otherwise one might limit the number of drivers or risks of being too late. This is true, at least, if we consider one such auction. However, if we look at the entire system taking time into account, then stating an earlier deadline could help because the end of the auction is determined by the deadline (see Section 3.3).

If stating an earlier deadline causes a passenger who comes later to be excluded, one could win an auction by lying. Of course, this seems to be unavoidable. However, one could at least punish the untruthful statement in cases when a passenger looses an auction by disallowing a similar ride with a later deadline in the next hour by the system.

Concerning the bid, the modified second-prize scheme guarantees incentive compatibility in case of the automatic assignment. Neither a higher nor a lower bid would change the payment in case of winning the auction - provided one bids more than the second bidder. For all losing bidders, a lower bid would not help and a higher bid could hurt. So the statement of the true valuation is a dominant strategy.

Now let us consider the case that the driver selects one passenger from the list. Assuming that with lower ranks there is a strictly decreasing probability that the driver selects a passenger, the expected utility could be defined as the probability of being chosen times the associated utility. Then it looks as if we end up with the generalized second-prize auction (GSP) [Edelman et al., 2007]. Note, however, that in our kind of auction there is only one winner who has to pay the full price, while in a GSP everybody wins something and also has to pay something. So, the process of choosing somebody not on the first rank must either be viewed as a non-rational action or as a process where non-stated preferences play a role. Here a passenger, who has all information, could clearly gain something from placing bids that are below his true valuation.

4 Optimal Assignment

In this paper, the optimal assignment will be used as a baseline for evaluating the proposed auction mechanism. When computing the optimal assignment, the goal is to maximize the total amount of VKT savings in order to reduce the overall travel costs and greenhouse emission. This is a common approach in existing ride sharing systems, e.g., for the ride sharing of commuters [Kamar and Horvitz, 2009].

The optimal assignment between passengers and drivers can be computed by finding the maximum weighted bipartite matching. We consider a matching as feasible only when the travel distance of the joint path of passenger and driver is smaller than the sum of the travel distances of both individual paths, i.e., when the matching yields a reduction of the total travel distance. Therefore, we have to extend the cost matrix by the cases where passengers and drivers travel on their own (assuming they can use a Taxi or their own car).

Equation 1 shows the extended cost matrix where c(di, pj) = lt(di, pj)/2 denotes the half joint cost for the matching of driver di and passenger pj, c(di) = ld(di) the single cost of driver di, and c(pj) = lp(pj) the single cost of passenger pj .

From the cost matrix in Equation 1 the optimal assignment can efficiently be computed in O(N 3 ) by a modified version of the Hungarian algorithm [Kuhn, 1955], where N is the maximal number of rows and columns of the cost matrix.

5 Experimental Results

We developed an experimental platform to validate the hypothesis that an auction based system leads to a higher probability of ride-shares between passengers and drivers when compared to methods optimizing on the VKTs only. We implemented the optimal assignment by using the Hungarian method with the cost matrix shown in Section 4 and the auction approach according to the description in Section 3.2.

5.1 Test Platform

The experimental platform simulates the behavior of drivers and passengers, each having his own (randomly generated) preference over closing a deal. Planned routes of passenger and drivers are randomly sampled from a uniform distribution over city maps by generating for each passenger p ∈ Pt and driver d ∈ Dt the tuples (s(p,t), g(p,t)) and (s(d,t), g(d,t)), respectively. Uniform sampling can be considered as a conservative approach since in a real setting the locations would be much more correlated, e.g., clustered due to commercial areas, industrial areas, and shopping centers.

For sake of simplicity we assume that all drivers and passengers have compatible deadlines, i.e., that any driver can deliver any passenger in time. Note that for both the optimal approach and the auction approach the incompatibility between a driver di and passenger pj can easily be expressed by setting the joint costs lt(di, pj) =∞.

We utilized OpenStreetMaps (openstreetmap.org) data together with the MoNav planner that offers exact routing without heuristic assumptions at very little computational demand due to a routing core based on contraction hierarchies [Vetter, 2010]. The planner is used at each time step to compute the joint cost lt(di, pj) for the matching of driver di and passenger pj, and the single costs ld(pj) and ld(di) of driver di and passenger pj, respectively, for each pj ∈ P and di ∈ D. As a testbed for our experiments we used the German cities of Freiburg and Berlin with a size for sampling locations of 22km2 and 170km2 , respectively. Figure 3 depicts an example output of our system.

As performance metrics we counted during each run the frequencies of successful ride agreements and the savings of VKTs by comparing the joint kilometers against the kilometers driven when driver and passenger are traveling on their own. Experiments were conducted with varying ratios among drivers and passengers. Results are averaged over 100 runs for each combination of number of drivers (1-50) and number of passengers (1-50).

5.2 Optimal Assignment

In this experiment we evaluated the probability of matches between drivers and passengers when applying the optimal assignment on the map of Freiburg. In the optimal assignment matches are only possible when the cost of the joint route of driver and passenger is below or equal to the sum of both routes travelled individually.

A commercial DRS based on the optimal assignment could be implemented so that each participant pays a monthly base fee in advance. Then, these fees could be used for supporting individual ride matches, i.e., lowering the joint cost artificially by covering extra detour costs of the drivers. Figure 4 summarizes the matching probability from conducted experiments with varying ratios between the number of passengers and the number of drivers. Mean and variance are presented at different degrees of system support, i.e., the maximal amount of detour kilometers that would be payed by the system for enabling the match.

These results show clearly that without financial support from the outside no satisfying matching probability can be achieved which in turn can increase the number of people abandoning the system. Adding system support increases the number of matchings, however, it is unclear in a practical setting how to weight it for specific driver-passenger pairings, and how to define the base fee. Results presented in the following section are related to the auction system that in contrary automatically adjusts to individual user valuations.

5.3 Optimal vs Auction Based Assignment

In this section we compare the auction-based mechanism with the optimal assignment. In the auction setting we simulated the individual valuations of passengers by random sampling from a half-Gaussian distribution over the interval lp(p) ∗ ctaxi km ≥ vd(〈d, p〉t) ≥ lp(p) ∗ ckm, where ctaxi km denotes the taxi price per km (e3.1) and ckm the base cost per km for a private driver (e0.3). The half-Gaussian distribution was chosen to model that with high probability passengers are willing to pay an amount close to the minimal costs for a single ride and with low probability an amount that is close to the price of the same ride with a taxi. For each randomly generated set Dt and Pt a sequence of auctions was initiated with one for each driver d ∈ Dt. Passengers p ∈ Pt participated in every compatible auction and the results of the auctions were computed sequentially. Figure 5 and Figure 6 depict the VKT savings and the probabilities for matching rides on the Freiburg and Berlin map, respectively. We compared the optimal assignment and the auction method using different variances σ for the half-Gaussian distribution.

The results clearly show that with increasing variance, i.e. higher willingness of the passengers to pay more than the base costs, the probability of matchings increases. This is obvious since higher investments have more potential for covering longer detours. However, with increasing variance also the amount of VKTs savings decreases since longer detours are taken by the drivers. Interestingly, when limiting the maximal valuation of passengers to zero, i.e. bids are exclusively the base costs (denoted by auction base in the figures), nearly the same amount of VKT savings are reached as with the optimal assignment. Therefore, our approach allows to trade-off near to optimal VKT savings for higher system availability by limiting the amount of allowed detour costs, as needed. This can easily be implemented by removing drivers from the set of compatible drivers in Section 3.2 if their detours are above the limit.

6 Discussion

In this paper we have presented a novel DRS system that: 1) allows more flexibility than state of the art systems, as it gives more freedom to users in the choice of their ride-sharing partner; 2) is robust in the sense that it promotes truth-telling about most aspects and fairness in payments; and 3) allows to trade-off VKT savings with the probability in finding matches between drivers and passengers.

Moreover, despite giving freedom to users to deviate from the optimal solution, experimental results show that the performance of our system is very close to optimal. In particular, it emerges that, depending on the maximum detour we allow in the system, we can tradeoff the probability of having a matching (i.e. a ride-share) versus minimization of VKT.

This result can be exploited to tune the system in order to achieve a critical mass, and thus high availability of service. For example, when the system is first launched one could allow for higher detours in order to maximize the matches and, thus, promote the creation of a critical mass of users. Then, detours would be limited as a long term solution in order to minimize VKT.

Current limitations of our system are the restriction to dual ride shares, i.e., one passenger and one driver, as well as the lack of a large-scale experiment proving the performance of our system in practice. In the near future, we plan to develop realistic simulations based on existing traces of user behaviors and field experiments with real users, in order to better understand the impact of limiting detours with respect to the achievement of critical mass. Moreover, we plan to address the issues related to the creation of ride-shares composed of more than two users and the impact of heuristic methods for computing the round-trips.