Dynamic Matching with Impatient Agents: A Study for Ride-Sharing Systems

Ride-sharing systems have emerged as a popular and cost-effective urban transportation solution, allowing private car drivers to offer rides to passengers traveling in the same direction. This paper delves into the market design problem, where agents, i.e., drivers and riders, dynamically enter the system over time, each requiring transportation to specific destinations. To get an important insight, we focus on a fundamental case where all participants share a common origin but have distinct destinations that define their types. Given matching agents of the same type generates higher utility than matching different types, we explore how the matching of agents can enhance the overall utility generated by the market. Moreover, we assume agents exhibit impatience and will exit the system after waiting for a given time window. This introduces interesting incentive issues, whether an agent will accept a matching proposed by the platform. Initially, we tackle scenarios where agents are constrained to accept such a matching. We introduce a straightforward heuristic that matches a different-type pair only when one agent is about to leave immediately and the other cannot wait beyond a threshold number of time periods. We establish a theoretical lower bound on the heuristic mechanism's performance and demonstrate its near-optimality. Subsequently, we shift focus to the incentive dynamics within the system, particularly when self-interested agents can be non-cooperative with the platform, i.e., reject low-value different-type matchings hoping to get better ones in the future. We study the incentive compatibility of the heuristic mechanism regarding cooperation and propose a strategy to foster cooperation by compensating appropriately agents who agree to accept different-type matching.