Matching Theory for a Ride-sharing System

Juyoun Lee

Backgrounds and Previous Researches

Ride-sharing is a typical example of a Sharing Economy [1]. It started during the World War 2 in order to conserve resources. It reappeared and spread rapidly in North America due to the fuel crisis. Telephone and internet-based matching made it reliable and organized. Ride-sharing in these days is achieving results in social networking platforms, real-time services, etc. It is expected to be developed in terms of services, technology, and policy areas [2]

It has many benefits such as reduction in emissions [3] and traffic congestion in the city [4], which have been proved by several studies. The shortcomings of ride-sharing, such as concerns about public order, a shortage of the flexibility, and burdensome scheduling can be moderated by using social networks on the Internet [5]

Ride-sharing is an organized ride matching prearranged by matching agencies. When deciding matches in dynamic ride-sharing, deviations from a driver's direct path from origin to destination and driver's preference should be considered. Optimization problem has some typical issues about matching restrictions, cost consideration, dierence between system's and participant's benefts [6]. Ride-sharing can be integrated with public transportation, which has many social benets. Optimizing, incentivizing, and choosing are areas that future researches are needed.

When adopting ride-sharing system in practice, exquisite designing is needed to promote participation and make ride-sharing system successful [7]. There are researches which deal with ride-sharing plan. Reference [8] deals with ride-sharing plans in a real-world setting. It tries to evaluate computationally ideal ride-sharing plan by using the real database. Reference [9] and [10] focus on factors like traffic congestion and flexibility that affect effectiveness of ride-sharing.

The ride-sharing problem can be described as a matching problem [11] [12] [13] [14] [15]. The matching theory is a mathematical approach of pairing two groups which consist of agents who have preference proles to the opponent group. In a matching theory, the stability is important. If some agents prefer other partners to their predetermined ones, they have inducements of leaving from the matching and the system becomes unstable [16]. Also, maximizing the social utility, which means the sum of utilities of all agents, is important.

Ride-sharing Model and Problem Formulation

Ride-sharing Model

Ride-sharing progress can be represented as a many-to-one, two-sided matching between vehicles and passengers, like the college admission model[17]. There are two types of agents; passengers $P$ and vehicles $V$ . Passengers want to be picked up at their desired point. So, the vehicle takes them while moving from the fixed start point to the destination. The number of seats available for passengers are finite for each vehicle. When taking multiple passengers, the route is determined so as to minimize the travel distance.

A matching $\mu$ is a mapping from $V\cup P$ to $V\cup P$ such that for all $p\in P$ and $v\in V$ ,

$\mu( p ) \in V \textrm{ and } \left\vert \mu( p ) \right\vert = 1 \textrm{, }$

$\mu( v ) \in P^{q_{v}}\textrm{ and } \left\vert \mu( v ) \right\vert = q_{v} \textrm{, }$

$\mu( p ) = v \textrm{ if and only if } p\in \mu( v ).$

In the ride-sharing system, agents who compose a pair want to maximize their utilities by minimizing vehicles' travel distance. Furthermore, maximizing the sum of all agents' utilities is important for the system manager, who decide the matching which all agents should accept. When matching $\mu_k$ between vehicle $v_j$ and passengers $\mu_k (v_j)$ is composed, the travel distance of the pair is $d_{v_j,\mu_k}$ .The utilities of the vehicles, passengers, and the social utility can be defined mathematically as follows:

$U_{v_j,\mu_k} = -d_{v_j,\mu_k} \textrm{ : the utility of the vehicle } v_j$

$U_{p_i,\mu_k} = -d_{\mu_k(p_i),\mu_k} \textrm{ : the utility of the passenger }p_i$

$U_{\mu_k} =\sum_{j=1}^n U_{v_j,\mu_k} + \sum_{i=1}^m U_{p_i\mu_k}\textrm{ : the social utility}$

Each agent $x\in{V \cup P}$ has a preference relation $\succ_{p_i}$ over the matching. The preference relations are determined from the largest to smallest utility. $\mu \succ_x \mu'$ indicates that a vehicle $v_j$ prefers matching $\mu$ to matching $\mu'$ and this means $U_{x,\mu^\prime}>U_{x,\mu}$

Problem Formulation

Consider there are two vehicles and four passengers. There are six numbers of matching possible. The system manager choose the matching which maximizes the social utility. This matching is not necessarily the best option for every agents and a matter of stability can appear. When there exists one blocking pair in the matching, agents can always get rid of it by transferring utility margin $\Delta U$ . This means the utility of one who transfer utility margin is reduced by $\Delta U$ and the utility of another one who possess blocking pair increases by $\Delta U$ . To make unstable matching stable by exchanging utilities, agents should be able to transfer their utilities while not possessing other blocking pairs.

Consider the case of the ride-sharing system as shown in Figure 3.1. There are two vehicles and four passengers. The $\textit{x,y}$ coordinates of agents' start points and destination are fixed. There are six numbers of matching possible. The matching which maximizes the social utility is matching $\mu_1$ . Since the pair $(v_1,p_1,p_3)$ makes a blocking pair, this matching is unstable.

In the above example, vehicle $v_2$ does not consist a blocking pair and has the utility margin $\Delta U_{v_2}$ such that

$U_{v_1,\mu_2}-U_{v_1,\mu_1}(=0.17) < \Delta U_{v_2} < U_{v_2,\mu_1}-U_{v_2,\mu_2}(=1.86)$

, so vehicle $v_2$ can transfer $\Delta U_{v_2}$ to vehicle $v_1$ . Since no other blocking pairs appear, matching $\mu_1$ becomes stable.

Conclusion

In this thesis, we have designed a ride-sharing problem as one-to-many, two-sided matching between two kinds of agents; vehicles and passengers. We assumed that a system manager determines the matching which maximizes the social utility, i.e, the sum of all agents' utilities and all agents follow it. Since each agent wants to maximize their own utility, there could be a case in which a blocking pair appears and the matching becomes unstable. To get rid of a blocking pair and stabilize the given matching, we proposed transferring utilities between vehicles or passengers. We showed that when there is one blocking pair, transferring utility margin is always possible. If agents who transfer their utility margin to another one do not possess any other blocking pairs, the matching becomes stable. By doing this, both stability and maximizing the social utility could be achieved. We also expanded this method to the case in which two blocking pairs exist.

Bibliography

[1] M. Furuhata, M. Dessouky, F. Ordonez, M.-E. Brunet, X. Wang, and S. Koenig, "Ridesharing: The state-of-the-art and future directions," Transportation Research Part B: Methodological, vol. 57, pp. 28-46, 2013.

[2] N. D. Chan and S. A. Shaheen, "Ridesharing in north america: Past, present, and future," Transport Reviews, vol. 32, no. 1, pp. 93-112, 2012.

[3] B. Caulfeld, "Estimating the environmental benefts of ride-sharing: A case study of dublin," Transportation Research Part D: Transport and Environment, vol. 14, no. 7, pp. 527-531, 2009.

[4] B. Cici, A. Markopoulou, E. Frias-Martinez, and N. Laoutaris, "Assessing the potential of ridesharing using mobile and social data: a tale of four cities," in Proceedings of the 2014 ACM International Joint Conference on Pervasive and Ubiquitous Computing. ACM, 2014, pp. 201-211.

[5] C. Stach, "Saving time, money and the environment-vhike a dynamic ride-sharing service for mobile devices," in 2011 IEEE International Conference on Pervasive Computing and Communications Workshops (PERCOM Workshops). IEEE, 2011, pp. 352-355.

[6] N. Agatz, A. Erera, M. Savelsbergh, and X. Wang, "Optimization for dynamic ride-sharing: A review," European Journal of Operational Research, vol. 223, no. 2, pp. 295-303, 2012.

[7] A. Levofsky and A. Greenberg, "Organized dynamic ride sharing: The potential environmental benefts and the opportunity for advancing the concept," in Transportation Research Board 2001 Annual Meeting, 2001, pp. 7-11.

[8] E. Kamar and E. Horvitz, "Collaboration and shared plans in the open world: Studies of ridesharing." in IJCAI, vol. 9, 2009, p. 187.

[9] H. Xu, F. Ordonez, and M. Dessouky, "A traffic assignment model for a ridesharing transportation market," Journal of Advanced Transportation, vol. 49, no. 7, pp. 793-816, 2015.

[10] M. Stiglic, N. Agatz, M. Savelsbergh, and M. Gradisar, "Making dynamic ride-sharing work: The impact of driver and rider flexibility," Transportation Research Part E: Logistics and Transportation Review, vol. 91, pp. 190-207, 2016.

[11] P. Thaithatkul, T. Seo, T. Kusakabe, and Y. Asakura, "A passengers matching problem in ridesharing systems by considering user preference," Journal of the Eastern Asia Society for Transportation Studies, vol. 11, pp. 1416-1432, 2015.

[12] M. Nourinejad and M. J. Roorda, "Agent based model for dynamic ridesharing," Transportation Research Part C: Emerging Technologies, vol. 64, pp. 117-132, 2016.

[13] X. Wang, "Optimizing ride matches for dynamic ride-sharing systems," Ph.D. dissertation, Georgia Institute of Technology, 2013.

[14] H. Zhang and J. Zhao, "Mobility sharing as a preference matching problem," IEEE Transactions on Intelligent Transportation Systems, 2018.

[15] Z. Han, Y. Gu, and W. Saad, "Fundamentals of matching theory," in Matching Theory for Wireless Networks. Springer, 2017, pp. 9-15.

[16] G. Demange, D. Gale, and M. Sotomayor, "A further note on the stable matching problem," Discrete Applied Mathematics, vol. 16, no. 3, pp. 217-222, 1987.

[17] D. Gale and L. S. Shapley, \College admissions and the stability of marriage," The American Mathematical Monthly, vol. 69, no. 1, pp. 9-15, 1962.