# Stable Matching of Users in a Ridesharing Model
## 2 The Proposed Model  
A network of roads is modeled through a directed multi-graph \(G=(V,A)\), where the set of vertices \(V\) represents the intersections or corners in the network, and the set of edges \(A\) the road segments. Let \(u\) be a _user_ traveling through a path (or route) in \(G\). The _route_ of \(u\), from \(v_{0}\) to \(v_{k}\), is a sequence \(R_{u}=v_{0}a_{1}v_{1}a_{2}\cdots a_{k}v_{k}\), where \(\{v_{0},v_{1},\ldots,v_{k}\}\in V\), \(\{a_{1},a_{2},\ldots,a_{k}\}\in A\), and each \(a_{i}\) connects \(v_{i-1}\) to \(v_{i}\), \(\forall i\in[1,k]\). A route \(R^{\prime}_{u}=v^{\prime}_{0}a^{\prime}_{1}v^{\prime}_{1}a^{\prime}_{2} \cdots a^{\prime}_{k}v^{\prime}_{j}\) is a _proper subroute_ of \(R_{u}=v_{0}a_{1}v_{1}a_{2}\cdots a_{k}v_{k}\) iff \(j<k\) y \(v^{\prime}_{0}=v_{i},a^{\prime}_{1}=a_{i+1},v^{\prime}_{1}=v_{i+1},\cdots,a^{ \prime}_{j}=a_{i+j},v^{\prime}_{j}=v_{i+j}\). Additionally, a weight function \(w:A\rightarrow\mathbb{R}^{+}\) denotes the _length_ of each road segment in \(G\). The _total length_ of \(R_{u}\) is computed through the function \(\hat{w}(R_{u})=\sum_{i=1}^{k}w(a_{i})\), \(\forall a_{i}\) included in \(R_{u}\).  
Two types of users, passenger and driver, are defined. Let \(p\) be a passenger requesting a ridesharing service to reduce either the costs generated by using its own vehicle or the travel times spent by using public transportation. On the other hand, let \(d\) be a driver bidding a ridesharing service by considering \(\sigma_{d}\) available places in its vehicle over the route \(R_{d}\). Both types of users, \(p\) and \(d\), can travel together by establishing a joint route \(R_{pd}\) as follows:  
1. _Identifical_ ridesharing: \(R_{p}=R_{d}\), then \(R_{pd}\) is also the same.
2. _Inclusive_ ridesharing: \(R_{p}\) is a proper subroute of \(R_{d}\) (or the opposite). For this case, \(R_{pd}\) is equal to this proper subroute.
3. _Partial_ ridesharing: \(R_{pd}\) is the longest proper subroute that is common between \(R_{p}\) and \(R_{d}\) when \(R_{p}\
eq R_{d}\).  
The type of ridesharing 3 differs from that described in the literature [12; 40]. In the partial ridesharing proposed here, it may be that none of the origin or destination points are included in \(R_{d}\). Figure 1 illustrates the types of ridesharing allowed in the proposed model.  
Let \(\pi_{p\to d}\) be the _utility_ of \(p\) when he/she shares its trip with \(d\) through \(R_{pd}\). Equation (1) models this utility based on two fundamental aspects of the ridesharing service: (1) the _travel savings_ of \(p\) by sharing its trip with \(d\) expressed by the function \(s_{p}(R_{pd})\); and (2) the global _reputation_ of \(d\) calculated by function \(r(d)\in[0,1]\). The coefficients \(\beta_{0}\) and \(\beta_{1}\) are two constants weighting the relevance levels for both aspects of the ridesharing service, where \(\beta_{0},\beta_{1}>0\).  
\[\pi_{p\to d}=\beta_{0}\cdot s_{p}(R_{pd})+\beta_{1}\cdot r(d). \tag{1}\]  
Note that \(\pi_{p\to d}\) is not necessarily equal to \(\pi_{d\to p}\).  
An important assumption of the presented model is that the driver-passenger utility evaluation is independent of interacting with other users. In this vein, travel savings and reputations are computed involving only two users, discarding the information of the others.