Balancing Efficiency and Stability in Multi-Rider Ridesharing Systems

Most ridesharing research focuses on enhancing overall efficiency, such as reducing total travel distance or increasing platform profits. However, an efficient solution may not be ideal for every group of riders. In shared rides, a rider's experience is shaped not only by cost but also by the composition of co-riders, which affects pickup delays, detours, and overall ride quality. As a result, certain groups of riders may envy alternative feasible ride arrangements that could have matched them together and offered a better experience in terms of cost, travel time, or convenience. These groups, who collectively have an incentive to prefer a different feasible match over the one assigned, are referred to as blocking coalitions. The presence of such coalitions leads to instability, making the platform vulnerable to losing riders to competing services that offer more attractive ride options. We propose two optimization paradigms to address stability in multi-rider ridesharing systems. The first approach develops optimization models that directly incorporate stability requirements into the matching process. The second approach introduces a novel side-payment scheme that takes an efficient matching as input and allocates side-payments to selected market participants to reduce or eliminate instability. Our numerical analyses highlight the effectiveness of our proposed approaches to balance efficiency and stability across a variety of scenarios and instability metrics.