# Stable Matching of Users in a Ridesharing Model
## 3 Stable Matching
An important assumption of this algorithm is that the evaluation of the utilities does not change during each iteration. Therefore, every output matching \(M_{1},M_{2},\ldots,M_{k}\) maintains their original utility values. Figure 4: Example of a bipartite graph \(B_{1}=(U_{1},E_{1})\) after an iteration of the Gale–Shapley algorithm. Figure 3: Example of a pairwise relationship between a vertex of type \(p\) and other one of type \(d\). Figure 2: Example of a complete bipartite graph \(B=(U,E)\). Let \(\pi_{M_{k}}\) be the sum of the utilities of each vertex incident to an edge of \(M_{k}\). Equation (9) shows this expression. \[\pi_{M_{k}}=\sum_{\forall\text{ edges }(p,d)\in M_{k}}(\pi_{p\to d}+\pi_{d \to p}). \tag{9}\]  
The _social welfare_ of the ridesharing system is the sum of the individual utilities of the final sequence of matchings. Equation (10) describes the social welfare function SW, where \(K\) is the total matching iterations of \(B=(U,E)\). \[\text{SW}(B_{M_{k}})=\sum_{k=1}^{K}\pi_{M_{k}}. \tag{10}\]  
The following lemma proves that the proposed algorithm reaches a stable matching. Lemma 1: _Algorithm 1 always generates a stable matching._  
Proof: The proof is by mathematical induction in the number of iterations \(k\) of the algorithm. Base case. : Let \(M_{1}=\{(p_{1}^{1},d_{1}^{1}),\ldots,(p_{k_{1}}^{1},d_{k_{1}}^{1})\}\) be the set of pairs matched at the first round. There exists a blocking pair in any of the following two cases. The first case would occur when \(n_{d}<k_{1}\). In this case, the users \(p_{n_{d+1}}^{1}\ldots p_{k_{1}}^{1}\) are assigned to the waiting list \(\mu_{d}\). The second case would occur if any \(p_{i}^{1}\) and \(d_{i}^{1}\) both prefer to match with another user rather than with their current one assigned in \(M_{1}\). However, this is not possible, because after the execution of Gale-Shapley algorithm, all users in \(\{p_{1}^{1},\ldots,p_{1}^{k_{1}}\}\) match with their corresponding user \(d_{j}^{1}\) of their highest preference. Inductive hypothesis. : Assume that after \(k=r\) iterations there are no blocking pairs in the matching \(M_{1},\ldots,M_{r}\). Inductive step. : Consider the iteration \(k=r+1\). Let \(B_{r}=(U_{r},E_{r})\) be the bipartite graph obtained after the \(r\)-th iteration. Let \(M_{r+1}=\{(p_{1}^{r+1},d_{1}^{r+1},\ldots,(p_{k_{r}+1}^{r+1},d_{k_{r+1}}^{r+1}))\) be the set of pairs matched at the round \(r+1\). There exists a blocking pair in any of the following two cases. The first case would occur if the number of available seats at iteration \(r\) is less than the remaining users of type \(p\) for that iteration, i.e., \(N_{\text{sests}}^{r}<k_{r+1}\). In this case, the remaining users of type \(p\) are assigned to the waiting list \(\mu_{d}\). The second case would occur if any \(p_{i}^{r+1}\) and \(d_{j}^{r+1}\) both preferred to match with another user rather than their current one assigned in \(M_{r+1}\). Notice that this is not possible because, by inductive hypothesis and by Gale-Shapley algorithm, all users in \(\{p_{1}^{r+1},\ldots,p_{k_{r+1}}^{r+1}\}\) match with the user \(d_{j}^{r+1}\) with their highest preference. Therefore, Algorithm 1 always generates a stable matching. Algorithm 1 requires \(O(kn^{2})\) time to generate a stable matching. Proof. : The result follows that each iteration of Gale-Shapley requires \(O(n^{2})\), and there exist \(k\) iterations.