# Stable Matching of Users in a Ridesharing Model
## 3 Stable Matching  
In this work, an algorithm is proposed to solve the stable matching problem in ridesharing systems according to the model described in Section 2. This algorithm is an \"iterated\" version of the well-known Gale-Shapley algorithm [28], relaxing the original restrictions concerning the equality in the size of the sets and the assumption of complete and strict preference lists. The set of users \(U\) of the ridesharing system consists of \(n=n_{p}+n_{d}\) elements of the type \(p\) and \(d\), respectively. The number of available seats in the vehicle driven by a user of type \(d\) is \(\sigma_{d}\), where \(\sigma_{d}\geq 1\). When a matching occurs between a pair of users \(p\) and \(d\), a seat is assigned to \(p\), decreasing \(\sigma_{d}\) in one. Let \(N_{\text{seats}}\) be the total of available seats in the ridesharing system, i.e., \(N_{\text{seats}}=\sum_{d}\sigma_{d}\). Without loss of generality, assume that \(n_{p}\geq N_{\text{seats}}\) and \(\delta_{\text{seats}}=n_{p}-N_{\text{seats}}\). To ensure convergence to a stable matching, a waiting list \(\mu_{d}\) is assumed. This waiting list contains \(\delta_{\text{seats}}=\sigma_{\mu_{d}}\) remaining seats intended to those users of type \(p\) that do not find a place in a vehicle. Since the waiting list represents the last option for any passenger \(p\), the model assigns \(\pi_{p\to\mu_{d}}=-\infty\), and \(\pi_{\mu_{d}\to p}=1\). The proposed algorithm takes as input a complete bipartite graph \(B=(U,E)\), where the set of vertices \(U=\{p_{1},p_{2},\ldots,p_{n_{p}}\}\cup\{d_{1},d_{2},\ldots,d_{n_{d}},\mu_{d}\}\) and the set of edges \(E\) represents all possible allocations between users. Figure 2 illustrates an example of a complete bipartite graph where \(n_{p}=3\) and \(n_{d}=2\). Every user \(p_{i}\) has a preference ranking to every user \(d_{j}\) and vice versa. These preferences are computed through the estimated utility for each ridesharing service. Thus, each edge \(e_{ij}\in E\) can be seen as two directed edges with a different weight according to their directions, where \(e_{ij}\) and \(e_{ji}\) represent the utilities \(\pi_{p_{i}\to d_{j}}\) and \(\pi_{d_{j}\to p_{i}}\), respectively. Figure 3 illustrates an example of a pairwise relationship between the vertices \(p_{i}\) and \(d_{j}\), modeled as two directed edges in the graph. Let \(B_{k}=(U_{k},E_{k})\) be a bipartite graph after \(k\) iterations of the Gale-Shapley algorithm. The matching in the \(k\)-th iteration consists of selecting a set \(M_{k}\subset E_{k-1}\), for \(k>0\), such that no pair of edges have a common vertex in \(E_{k-1}\). In this context, the matching means assigning a user \(p_{i}\) to a user \(d_{j}\) with \(\sigma_{d_{j}}\) available seats. Then, every matched vertex \(d_{j}\) \"hosts\" one vertex of type \(p\), decreasing its available seats by one at each iteration \(k\). Any hosting vertex of type \(d\) in the iteration \(k\) represents a single vertex, called a'supervertex', for the iteration \(k+1\). For each iteration \(k\), a subgraph \(B_{k}\subset B_{k-1}\) is generated. Thus, \(U_{k}\) contains the supervertices and the remaining vertices that were not chosen in \(U_{k-1}\), and \(E_{k}\) contains the edges of \(E_{k-1}-M_{k}\). Iteration matching ends in two cases. The first case occurs when there are no available seats in vertices of type \(d\); in this case, the remaining users of type \(p\) match to the waiting list \(\mu_{d}\) with its \(\sigma_{\mu_{d}}=\delta_{\mathit{seats}}\) seats. The second case occurs when all the vertices of type \(p\) match a user of type \(d\). Notice that this case only occurs when \(N_{\mathit{seats}}=n_{p}\). Figure 4 illustrates an example of a resulting bipartite graph \(B_{1}=(U_{1},E_{1})\) after one iteration of the Gale-Shapley algorithm. Note that for this iteration \(U_{1}=\{p_{2},d_{1},d_{2}\}\) where vertices \(d_{1}\), \(d_{2}\), and \(\mu_{d}\) are supervertices. Algorithm 1 presents the proposed solution for the stable matching problem in ridesharing systems.