Matching riders to drivers is the major and core tax of riding platforms like Uber and lift. The mechanism of mach is extremely important. Unmatched riders bear a cost of waiting and the drivers bear the cost of moving to the rider whom they are being assigned to. The waiting time for riders should be as short as possible and the drivers should be as close to the rider as possible. The simplest matching mechanism is greedy match. In this mechanism as the new riders arrive randomly in different locations, the platform matches it to the nearest available driver. However, there are simple examples, which shows greed matching can be far away from optimum with minimum costs. Assume a one dimensional road, where rivers arrive randomly on location x. Suppose we have two drivers in the system one on point 0, the other on point 5 along the axis. Now, the first rider arrives at point 3. The greedy matching mechanism matches the driver at location 5 to this rider. Then, the second rider arrives at location 6. The greedy matching mechanism is forced to assign the driver at location zero to the rider. However an omniscient system, which knows which rider arrives when, will assign the driver on location 0 to the first rider and the driver on location 5 to the next rider. Professor Akbarpur of Stanford university and his colleagues showed in an interesting paper, that the cost of a greedy matching can be sufficiently close to omniscient matching, if there are enough drivers on the system. According to their paper results, when there are (1+e) drivers on the system per every rider, the cost of a greedy match is bounded by a function of Alog3(n), where n is the number of riders. On the other hand, the optimal match performed by an omniscient planner will have a cost no less than a function of Bn. A and B are real bounded, positive numbers. The result indicates that the greedy match is close to optimal, when there are enough drivers on the system. The results indicate why Uber and Lyft do not spend large sums of money to develop sophisticated matching algorithms. Instead, they keep the matching mechanism as simple as possible and focus on finding more drivers.
Source: Akbarpour, Mohammad, et al. “The value of excess supply in spatial matching markets.” arXiv preprint arXiv:2104.03219 (2021).
