Learning Equilibria in Matching Markets from Bandit Feedback
Authors: Meena Jagadeesan, Alexander Wei, Yixin Wang, Michael Jordan, Jacob Steinhardt
NeurIPS 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We design an incentive-aware learning objective that captures the distance of a market outcome from equilibrium. Using this objective, we analyze the complexity of learning as a stochastic multi-armed bandit problem. Algorithmically, we show that optimism in the face of uncertainty, the principle underlying many bandit algorithms, applies to a primal-dual formulation of matching with transfers and leads to near-optimal regret bounds. Our work takes a first step toward elucidating when and how stable matchings arise in large, data-driven marketplaces. |
| Researcher Affiliation | Academia | Meena Jagadeesan UC Berkeley mjagadeesan@berkeley.edu Alexander Wei UC Berkeley awei@eecs.berkeley.edu Yixin Wang UC Berkeley ywang@eecs.berkeley.edu Michael I. Jordan UC Berkeley jordan@cs.berkeley.edu Jacob Steinhardt UC Berkeley jsteinhardt@berkeley.edu |
| Pseudocode | Yes | Algorithm 1 COMPUTEMATCH: Compute matching with transfers from confidence sets. Algorithm 2 MATCHUCB: A bandit algorithm for matching with transferable utilities for unstructured preferences. |
| Open Source Code | No | The paper does not provide an explicit statement about releasing source code for the methodology or a direct link to a code repository. The provided arXiv link is for a full version of the paper itself. |
| Open Datasets | No | The paper is theoretical and does not describe experiments run on a dataset, thus no dataset access information is provided. |
| Dataset Splits | No | The paper is theoretical and does not describe experiments run on a dataset, thus no dataset split information is provided. |
| Hardware Specification | No | The paper is theoretical and does not describe experiments or their execution, therefore no hardware specifications are provided. |
| Software Dependencies | No | The paper is theoretical and does not describe experiments or their implementation, therefore no specific software dependencies with version numbers are listed. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup with specific hyperparameters or training configurations. |