Efficient and stable ride-pooling through a multi-level coalition formation game
Yaotian Tan, Shuyue Qian, Aoyong Li, Haiyang Yu, Jie Gao
Abstract
Ride-pooling has the potential to offer a sustainable solution for urban mobility by reducing vehicle use and emissions through shared trips. However, its adoption remains limited due to poor matching performance. Many requests fail to form feasible pools, and even successful matches often involve long detours or minimal cost savings. These inefficiencies largely arise from fragmented market structures: most operators act independently, restricting matching to their own request pools and limiting the formation of beneficial coalitions. Aggregation platforms improve efficiency by integrating regional operators through unified dispatch systems, but raise concerns over long-term stability. Differences in operator cost structures and market shares may incentivize deviation, at the same time, passengers may reject assigned payments if more attractive alternatives exist. To address these challenges, we propose a multi-level coalition formation game that jointly models operator and passenger collaboration. At the upper level, operators play a non-cooperative game to decide coalition partners. At the lower level, passengers are grouped into shared trips through a cooperative game that ensures individually rational payments. The two layers are coupled via constraint propagation, forming a unified decision-making process. We evaluate our framework using real-world data from three Chinese regions—Chengdu, Haikou, and the Ningxia Hui Autonomous Region—chosen to reflect diverse urban and regional contexts. Compared to independent operations, our approach increases vehicle occupancy by 14%–28%, reduces total costs by 10%–15%, and shortens average travel distances by 4%–5%. The system maintains stable coalition structures with operator deviation rates below 6.81% and near-zero passenger deviation rates.