Matching while learning
From MaRDI portal
Abstract: We consider the problem faced by a service platform that needs to match limited supply with demand but also to learn the attributes of new users in order to match them better in the future. We introduce a benchmark model with heterogeneous "workers" (demand) and a limited supply of "jobs" that arrive over time. Job types are known to the platform, but worker types are unknown and must be learned by observing match outcomes. Workers depart after performing a certain number of jobs. The expected payoff from a match depends on the pair of types and the goal is to maximize the steady-state rate of accumulation of payoff. Though we use terminology inspired by labor markets, our framework applies more broadly to platforms where a limited supply of heterogeneous products is matched to users over time. Our main contribution is a complete characterization of the structure of the optimal policy in the limit that each worker performs many jobs. The platform faces a trade-off for each worker between myopically maximizing payoffs (exploitation) and learning the type of the worker (exploration). This creates a multitude of multi-armed bandit problems, one for each worker, coupled together by the constraint on availability of jobs of different types (capacity constraints). We find that the platform should estimate a shadow price for each job type, and use the payoffs adjusted by these prices, first, to determine its learning goals and then, for each worker, (i) to balance learning with payoffs during the "exploration phase," and (ii) to myopically match after it has achieved its learning goals during the "exploitation phase."
Recommendations
- Adaptive matching for expert systems with uncertain task types
- Integrated online learning and adaptive control in queueing systems with uncertain payoffs
- Technical note -- Assortment planning for two-sided sequential matching markets
- Bandits with knapsacks
- Reward maximization in general dynamic matching systems
Cites work
- A dynamic model of barter exchange
- An information-theoretic analysis of Thompson sampling
- Asymptotically efficient adaptive allocation rules
- Asymptotically efficient adaptive allocation schemes for controlled i.i.d. processes: finite parameter space
- Bandit algorithms
- Bandits with global convex constraints and objective
- Blind network revenue management
- Close the gaps: a learning-while-doing algorithm for single-product revenue management problems
- Dynamic Pricing and Learning with Finite Inventories
- Dynamic matching for real-time ride sharing
- Dynamic pricing without knowing the demand function: risk bounds and near-optimal algorithms
- Estimating the Parameters of Mixtures of Binomial Distributions
- Finite-time analysis of the multiarmed bandit problem
- Heavy traffic analysis of open processing networks with complete resource pooling: asymptotic optimality of discrete review policies
- Learning Mixtures of Product Distributions over Discrete Domains
- Learning in combinatorial optimization: what and how to explore
- Multi-armed bandit allocation indices. With a foreword by Peter Whittle.
- Network Optimization and Control
- On the capacity of information processing systems
- Online Network Revenue Management Using Thompson Sampling
- Online matching and ad allocation
- Optimal dynamic matching
- Regret analysis of stochastic and nonstochastic multi-armed bandit problems
- Stability in dynamic matching markets
- The assignment game. I: The core
- The exact law of large numbers via Fubini extension and characterization of insurable risks
Cited in
(6)- Fine-grained job salary benchmarking with a nonparametric Dirichlet process-based latent factor model
- Adaptive matching for expert systems with uncertain task types
- Integrated online learning and adaptive control in queueing systems with uncertain payoffs
- Complexity analysis of a countable-armed bandit problem
- Learning equilibria in matching markets with bandit feedback
- scientific article; zbMATH DE number 7626726 (Why is no real title available?)
This page was built for publication: Matching while learning
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4994180)
