Dynamic Matching and Allocation of Tasks

Kartik Ahuja, Mihaela van der SchaarACM Trans. Economics and Comput 2020 · OpenReview

TL;DR

This paper introduces a novel dynamic matching mechanism for two-sided markets where participants have incomplete information and face moral hazard. The mechanism facilitates learning about participants' true characteristics before making long-term matches, ensuring both efficiency and stability.

What Problem Does This Paper Address?

In many real-world scenarios, like job markets or freelancing platforms, matching workers to tasks (or clients to workers) involves significant uncertainty. Both sides have incomplete information about each other's true capabilities and costs. Furthermore, workers can strategically adjust their effort (moral hazard), which is not directly observable by clients, making it difficult for clients to accurately assess worker productivity. This lack of information and the presence of moral hazard can lead to suboptimal matches and inefficient outcomes. The paper addresses the challenge of designing a system that allows participants to learn about each other over time, encourages truthful revelation of information, and ultimately leads to stable, high-revenue matches in the long run.

Methods

The authors propose a dynamic matching mechanism called "First Impression is the Last Impression" (FILI). This mechanism operates in three phases:

  1. Assessment Phase: Workers are matched with each task exactly once over an initial period. During these interactions, both parties observe the worker's output and the associated revenue. This phase is crucial for initial learning.
  2. Reporting Phase: Workers submit their ranked preferences for tasks based on their learned expected long-run utilities.
  3. Operational Phase: A stable matching is computed using the Gale-Shapley algorithm, with workers as proposers. This final matching is fixed for all future interactions.

The core of their approach involves defining and achieving "long-run coalitional stability," a concept that ensures no group of participants can benefit by deviating from the proposed strategy. They also introduce a "bang-bang equilibrium" strategy for workers, where they exert maximum effort during the assessment phase and then either maximum or zero effort in the operational phase, depending on their expected utility.

Datasets

Not discussed in the paper. The paper focuses on theoretical modeling and proposes a mechanism, with numerical experiments described in Section III, but no specific external datasets are mentioned.

Key Insights and Ideas

  • Learning is Key: The mechanism's success hinges on facilitating learning about participants' true characteristics through repeated interactions, even in the presence of moral hazard.
  • "First Impression" Matters: The initial assessment phase, where workers are evaluated on all tasks, is critical for establishing a reliable basis for long-term matching.
  • Incentivizing Truthfulness: By using a worker-optimal Gale-Shapley matching in the operational phase and structuring the assessment phase, the mechanism incentivizes workers to reveal their true preferences and exert effort truthfully.
  • Long-Run Stability: The proposed mechanism achieves "long-run coalitional stability," meaning that no coalition of workers and clients can improve their long-term outcomes by deviating. This is a strong form of stability in dynamic matching.
  • Optimal Revenue: Under certain assumptions (homogeneous tasks with bimodal quality distribution), the mechanism is shown to achieve the optimal total long-run revenue.

Key Results

  • The proposed FILI mechanism is shown to be long-run coalitionally stable.
  • The "bang-bang equilibrium" strategy is proven to be a weakly dominant strategy for workers, leading to an equilibrium.
  • Under specific assumptions (Assumptions 1 and 2), the equilibrium payoff is unique.
  • Under Assumptions 2 and 3, the FILI mechanism achieves the optimal total long-run revenue.
  • Numerical experiments show the proposed mechanism can lead to large gains (over 75%) in total long-run revenue and profit compared to other approaches, and is always long-run stable.

Limitations and Future Work

  • Assumptions: The theoretical results rely on specific assumptions, such as task homogeneity (Assumption 2) and a bimodal task quality distribution (Assumption 3) for optimal revenue. Relaxing these assumptions could be a direction for future work.
  • Computational Intractability: The paper acknowledges that the space of possible matching rules and strategies is vast, making the problem computationally intractable in its most general form.
  • Extensions: The paper discusses extensions to general payment and cost functions, client-selected payment rules, and learning by doing, suggesting these are areas for further research. The authors also mention that their analysis extends to discounted utilities.

Summary updated

Abstract

In many two-sided markets, the parties to be matched have incomplete information about their characteristics. We consider the settings where the parties engaged are extremely patient and are interested in long-term partnerships. Hence, once the final matches are determined, they persist for a long time. Each side has an opportunity to learn (some) relevant information about the other before final matches are made. For instance, clients seeking workers to perform tasks often conduct interviews that require the workers to perform some tasks and thereby provide information to both sides. The performance of a worker in such an interview- and hence the information revealed—depends both on the inherent characteristics of the worker and the task and also on the actions taken by the worker (e.g., the effort expended), which are not observed by the client. Thus, there is moral hazard. Our goal is to derive a dynamic matching mechanism that facilitates learning on both sides before final matches are achieved and ensures that the worker side does not have incentive to obscure learning of their characteristics through their actions. We derive such a mechanism that leads to final matching that achieves optimal performance (revenue) in equilibrium. We show that the equilibrium strategy is long-run coalitionally stable, which means there is no subset of workers and clients that can gain by deviating from the equilibrium strategy. We derive all the results under the modeling assumption that the utilities of the agents are defined as limit of means of the utility obtained in each interaction.
BibTeX
@article{ahuja2020dynamic,
  author = {Kartik Ahuja and Mihaela van der Schaar},
  title = {{Dynamic Matching and Allocation of Tasks}},
  journal = {ACM Trans. Economics and Comput.},
  year = {2020},
  url = {https://openreview.net/forum?id=1K1rvYofIY},
}
Figure