# Stable Matching of Users in a Ridesharing Model
A blocking pair \((p_{1},d_{1})\) exists with respect to \(M\) if \(p_{1}\) prefers to \(d_{1}\) more than \(d_{2}\), and \(d_{1}\) prefers to \(p_{1}\) more than \(p_{2}\). Formally, a stable matching exists if there is no blocking pairs. The concept of stability can be applied to different matching models such as one-to-one [28], many-to-one [29], and many-to-many [30]. However, finding a stable matching (in any of its variants) of maximum cardinality is NP-hard [31]. In particular, the ride-matching problem can be studied through the well-known hospital/resident problem proposed in [31], in which a set of medical residents seek a position in a set of hospitals. While each resident ranks hospitals according to their preferences, each hospital ranks the applicant residents for its available positions. If the number of available hospital resident positions and the number of medical applicants is different, the problem is the stable matching with incomplete lists. Stability is not possible for different cardinalities in the matching sets [31]. A variety of matching models explore the concept of stability for dynamic ridesharing considering relationships of one-to-one or many-to-one. While one-to-one matching applies to a simple setting with unit vehicle capacity [32, 33, 34, 35, 36], many-to-one matching allows multi-capacity settings. Regarding the many-to-one matching, where one vehicle can serve multiple passengers simultaneously, some research efforts have been proposed [37, 38, 39]. For example, a recent taxi-sharing model considering many-to-one matching is proposedin [37]. The passenger's preference depends on the taxi and the co-riders in their model, which is reformulated to a scheme-based set partitioning model that a branch-and-price algorithm can solve. The proposed branch-and-price algorithm achieves stable matchings and, in some cases, nearly stable matchings. In [38], a many-to-one matching model involving shared autonomous vehicles (SAV) is proposed. Their model characterizes the waiting times of an SAV and multiple passengers who share rides in the SAV during online matching. A new multimodal autonomous ridesharing user equilibrium is introduced in their work in order to characterize the SAV traveler flow while considering seat capacity utilization. Passengers, dedicated drivers, and SAV have different behaviors impacting the matching decisions regarding these works. On the other hand, from the game-theoretical perspective, a many-to-one matching game is proposed to address stable solutions focused on the route-cost-assignment in [39]. Their model outputs a stable payoff space for the post-evaluation of cost allocation mechanisms. A current comprehensive review of all these topics can be found in [40]. However, most many-to-one matching models providing stable solutions do not consider diverse types of trips between users. This paper addresses the stable matching of users in ridesharing systems. The contribution of this work is twofold. First, a new ridesharing system model is introduced. This model considers users' preferences based on two fundamental aspects of the service: travel savings and the reputation of users (both passengers and drivers). Travel savings consider three types of trips (identical, inclusive, and partial), where one of them is novel in the literature. The reputation of users is computed through a modified version of the EigenTrust algorithm [41] for peer-to-peer systems. In the proposed model, a driver may pick up more than one passenger during the trip while respecting timing and capacity constraints, such as the slack time and the number of available seats. To address these constraints, the model assumes that the driver-passenger utility evaluation is independent of interacting with other users. Second, a new stable matching algorithm for the ridesharing system services is presented. This algorithm consists of a new iterated version of the Gale-Shapley algorithm [28].