TY - JOUR AU - Zhao, Boming AU - Xu, Pan AU - Shi, Yexuan AU - Tong, Yongxin AU - Zhou, Zimu AU - Zeng, Yuxiang PY - 2019/07/17 Y2 - 2024/03/28 TI - Preference-Aware Task Assignment in On-Demand Taxi Dispatching: An Online Stable Matching Approach JF - Proceedings of the AAAI Conference on Artificial Intelligence JA - AAAI VL - 33 IS - 01 SE - AAAI Technical Track: Game Theory and Economic Paradigms DO - 10.1609/aaai.v33i01.33012245 UR - https://ojs.aaai.org/index.php/AAAI/article/view/4060 SP - 2245-2252 AB - <p>A central issue in on-demand taxi dispatching platforms is task assignment, which designs matching policies among dynamically arrived drivers (workers) and passengers (tasks). Previous matching policies maximize the profit of the platform without considering the preferences of workers and tasks (<em>e.g.,</em> workers may prefer high-rewarding tasks while tasks may prefer nearby workers). Such ignorance of preferences impairs user experience and will decrease the profit of the platform in the long run. To address this problem, we propose <em>preference-aware</em> task assignment using online stable matching. Specifically, we define a new model, <em>Online Stable Matching under Known Identical Independent Distributions</em> (OSM-KIID). It not only maximizes the expected total profits (OBJ-1), but also tries to satisfy the preferences among workers and tasks by minimizing the expected total number of blocking pairs (OBJ-2). The model also features a practical arrival assumption validated on real-world dataset. Furthermore, we present a linear program based online algorithm LP-ALG, which achieves an online ratio of at least 1−1/<em>e</em> on OBJ-1 and has at most 0<em>.</em>6·|<em>E</em>| blocking pairs expectedly, where |<em>E</em>| is the total number of edges in the compatible graph. We also show that a natural Greedy can have an arbitrarily bad performance on OBJ-1 while maintaining around 0<em>.</em>5·|<em>E</em>| blocking pairs. Evaluations on both synthetic and real datasets confirm our theoretical analysis and demonstrate that LP-ALG strictly dominates all the baselines on both objectives when tasks notably outnumber workers.</p> ER -