Constant-competitive online matching for incentive-compatible random arrivals
Arrival-Time Incentive Compatibility in Random Order Online Bipartite Matching
Computer Science and Game TheoryData Structures and Algorithms
Summary
Matching users to resources online is tricky when users want to get served quickly but don’t care who serves them, and the system wants to maximize overall rewards. The authors study a problem like this, where arrivals come in random order and users might try to game the system by choosing when to arrive. They develop an algorithm that fairly treats all arrival times and still matches users well. Their method guarantees a steady fraction of the best possible matching, even as the number of users and resources changes.
What this means in practice
- •For ride-sharing platform operators: Assign rides to passengers in real time ensuring users have no incentive to delay arrival and improving overall matching efficiency.
- •For cloud resource managers: Route and match service requests to servers with varying capabilities, maintaining fairness and maximizing utilization online.
Authors
Arghya Chakraborty, Varun Gupta
Abstract
In this work we initiate the study of competitive algorithms with arrival-time incentive compatibility for random-order online bipartite matching in settings where the users care only about receiving service (matched vs. unmatched) and not which offline resource serves them, while the platform's objective is to maximize total matching reward. This captures applications such as ride-sharing where the users primarily care about being matched to a ride while the platform internalizes the cost of dispatching a distant driver; dispatching homogeneous service requests to heterogeneous servers (cloud/edge routing); and assigning customer requests to a pool of providers with different flexibility (e.g., English-only vs. bilingual agents). Our main question is: \textit{Is constant-competitive matching possible for incentive-compatible, random-order edge-weighted matching on complete bipartite graphs?} Motivated by the LP-based treatment of incentive compatibility in the classical secretary problem by Buchbinder et al., we impose a constraint that the ex ante probability of selection is equalized across all arrival positions. We answer our main question in the affirmative and propose the first constant-competitive algorithm for incentive compatible edge-weighted random-order online matching on complete bipartite graphs. The competitive ratio of our algorithm is parameterized by the imbalance factor $k := n/m$ -- where $n$ and $m$ are the numbers of online and offline nodes, respectively, and $k$ is a positive integer. In particular, we obtain a competitive guarantee of the form $c_k - O(1/\sqrt{m})$ where $c_1 \approx 0.162$ and $c_k \to 0.02308\ldots$ as $k \to \infty$. We also present algorithms with strictly improved competitive ratio of $\approx 0.07 + O(1/m)$ for the binary-weighted case ($0$-$1$ rewards).