YASH KANORIA, Columbia Business School is paper considers a central operational challenge faced by platforms that serve as matchmakers between supply and demand. Such platforms face a fundamental exploration-exploitation trade-o : on the one hand, e cient operation involves making matches that generate the most value ("exploitation"); on the other hand, the platform must continuously learn about newly arriving participants, so that they can be e ciently matched ("exploration"). In this paper, we develop a structurally simple and nearly optimal approach to resolving this trade-o . We consider a model with two groups of participants: workers and jobs. Time is discrete, and new workers and jobs arrive at the beginning of every time period. Each worker departs a er performing a speci ed number of jobs. Every time a worker and job are matched, a (random) payo is generated and observed by the platform, where the payo distribution depends on the type of the worker and the job. We consider the following learning challenge: in most platforms, more is known about one side of the platform than the other; accordingly, we assume job types are known, while the type of a new worker is unknown. e platform learns about workers' types through the payo s obtained when they are matched to jobs. However, because the supply of jobs is limited, using jobs to learn can reduce immediate payo s, as well as deplete the supply of jobs available to the rest of the marketplace. us the presence of capacity constraints presents a new challenge in the optimal resolution of the exploration vs. exploitation tradeo . Our main contribution in this paper is the development of a matching policy that is nearly payo optimal. We nd that the platform should estimate a shadow price for each job type, and use the payo s adjusted by these prices, rst, to determine its learning goals and then, for each worker, (i) to balance learning with payo s during the "exploration phase", and (ii) to myopically match a er it has achieved its learning goals during the "exploitation phase. " We refer to our policy as DEEM: Decentralized Explore-then-Exploit for Matching. Our main result shows that DEEM achieves essentially optimal regret as the number of jobs N performed by each worker during their lifetime grows, where regret is the loss in payo relative to the maximum achievable with known worker types. In our se ing, a lower bound on the regret is C log N /N (1 + o(1)) for some C ∈ [0, ∞) that is a function of system parameters. DEEM achieves this level of regret to leading order when C > 0, while it achieves a regret of O (log log N /N ) if C = 0. Our theory is complemented by implementation and simulation that demonstrate a natural and implementable heuristic that translates our work into practice. In particular, our simulations reveal substantial bene t from jointly managing capacity constraints and learning, as we do in DEEM.
The work in REF considers a model where the job types are known but the expert types are unknown.