Adaptive Matching for Expert Systems with Uncertain Task Types

• 成果类型: Article
• 署名作者: Shah, Virag; Gulikers, Lennart; Massoulie, Laurent; Vojnovic, Milan
• 署名单位: Uber Technologies, Inc.; University of London; London School Economics & Political Science
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2019.1954
• 发表日期: 2020
• 页码: 1403-1424
• 关键词: Asymptotic Optimality; parallel servers; STABILITY; allocation; networks

摘要

A matching in a two-sided market often incurs an externality: a matched resource may become unavailable to the other side of the market, at least for a while. This is especially an issue in online platforms involving human experts, as the expert resources are often scarce. The efficient utilization of experts in these platforms is made challenging by the fact that the information available about the parties involved is usually limited. To address this challenge, we develop a model of a task-expert matching system where a task is matched to an expert using not only the prior information about the task but also the feedback obtained from the past matches. In our model, the tasks arrive online while the experts are fixed and constrained by a finite service capacity. For this model, we characterize the maximum task resolution throughput a platform can achieve. We show that the natural greedy approach where each expert is assigned a task most suitable to his or her skill is suboptimal, as it does not internalize the aforementioned externality. We develop a throughput-optimal backpressure algorithm which does so by accounting for the congestion among different task types. Finally, we validate our model and confirm our theoretical findings with data-driven simulations via logs of Math.StackExchange.com, a Stack Overflow forum dedicated to mathematics.