Regret, stability & fairness in matching markets with bandit learners

Devavrat Shah; Sarah H. Cen

RECORD

Regret, stability & fairness in matching markets with bandit learners

Sarah H. Cen, Devavrat Shah

Machine Learning · Submitted 11 Feb 2021

abstract compiled · 2026-09-23 · no language-model review

The authors' main claim In particular, by modeling two additional components of competition -- namely, costs and transfers -- we prove that it is possible to simultaneously guarantee four desiderata: stability, low optimal regret, fairness in the distribution of regret, and high social welfare.

how it is stated · asserted 0.99 read the record →

Comment (0) Read on arXiv ↗

Cite ▾

Claim paper

The compiled record

The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Open the compiled record

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-09-23: 1 request, 6,130 input tokens.

What the abstract itself states, as probabilities: claims first 0.07 · states limitation 0.12 · human participants 0.06 · controlled comparison 0.05 · randomized assignment 0.02 · states quantitative result 0.11 · compares with prior results 0.90 · mentions code or data availability 0.02.

The abstract, sentence by sentence

arXiv listing abstract v2. Results and the main claim are underlined; show every role.

Making an informed decision -- for example, when choosing a career or housing -- requires knowledge about the available options. Such knowledge is generally acquired through costly trial and error, but this learning process can be disrupted by competition. In this work, we study how competition affects the long-term outcomes of individuals as they learn. We build on a line of work that models this setting as a two-sided matching market with bandit learners. A recent result in this area states that it is impossible to simultaneously guarantee two natural desiderata: stability and low optimal regret for all agents. Resource-allocating platforms can point to this result as a justification for assigning good long-term outcomes to some agents and poor ones to others. We show that this impossibility need not hold true. In particular, by modeling two additional components of competition -- namely, costs and transfers -- we prove that it is possible to simultaneously guarantee four desiderata: stability, low optimal regret, fairness in the distribution of regret, and high social welfare.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#	sentence	role	the authors' own work	states the main conclusion	strength
s0	Making an informed decision -- for example, when choosing a career or housing -- requires knowledge about the available options.	background 1.00	0.03	0.01	asserted 0.98
s1	Such knowledge is generally acquired through costly trial and error, but this learning process can be disrupted by competition.	background 1.00	0.04	0.01	asserted 0.84
s2	In this work, we study how competition affects the long-term outcomes of individuals as they learn.	contribution 0.75	0.47	0.03	asserted 0.77
s3	We build on a line of work that models this setting as a two-sided matching market with bandit learners.	background 0.65	0.57	0.02	asserted 0.96
s4	A recent result in this area states that it is impossible to simultaneously guarantee two natural desiderata: stability and low optimal regret for all agents.	background 0.92	0.03	0.05	asserted 1.00
s5	Resource-allocating platforms can point to this result as a justification for assigning good long-term outcomes to some agents and poor ones to others.	interpretation 0.62	0.05	0.03	hedged possibility 0.79
s6	We show that this impossibility need not hold true.	result 0.71	0.92	0.39	asserted 0.94
s7	In particular, by modeling two additional components of competition -- namely, costs and transfers -- we prove that it is possible to simultaneously guarantee four desiderata: stability, low optimal regret, fairness in the distribution of regret, and high social welfare.	result 0.83	0.96	0.94	asserted 0.99

What kind of paper the classifier reports this is: theoretical result 1.00 · evidence from proof or derivation 1.00.

What was examined, and what was not

sources read

arXiv listing abstract v2

not examined

full text
figures and tables
references and citing sentences
relations to other papers

levels run

P abstract

not run

S sections
T body sentences
C citations
R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

The paper

Original abstract

Making an informed decision -- for example, when choosing a career or housing -- requires knowledge about the available options. Such knowledge is generally acquired through costly trial and error, but this learning process can be disrupted by competition. In this work, we study how competition affects the long-term outcomes of individuals as they learn. We build on a line of work that models this setting as a two-sided matching market with bandit learners. A recent result in this area states that it is impossible to simultaneously guarantee two natural desiderata: stability and low optimal regret for all agents. Resource-allocating platforms can point to this result as a justification for assigning good long-term outcomes to some agents and poor ones to others. We show that this impossibility need not hold true. In particular, by modeling two additional components of competition -- namely, costs and transfers -- we prove that it is possible to simultaneously guarantee four desiderata: stability, low optimal regret, fairness in the distribution of regret, and high social welfare.

Human review

How Pith checks papers → · Full audit of this paper →

How the literature uses it

7 arXiv papers cite this in 7 sentences

Each citing sentence is taken from the citing paper's LaTeX source and typed by Pith's classifier. A label appears at probability 0.8 or more (0.95 for support), a contest at 0.7 or more; the quoted words are the citing authors'. How each label was checked · JSON

Papers citing it · 3 sentences without a confident label

Cites it as background 4 papers

There is an emerging line of research on learning stable matchings with bandit feedback [ref] using the mature tools from the bandit literature.

Learn to Match with No Regret: Reinforcement Learning in Markov Matching Markets · Related Work · 0.93
We would also like to remark about another line of research at the intersection of multiarmed bandits and matching markets [ref] , [ref] , [ref] which consider the problem of learning preferences from the perspective of a platform.

Decentralized, Communication- and Coordination-free Learning in Structured Matching Markets · Related works · 1.00
[ref] , [ref] , [ref] , and [ref] studied the recovery of stable matching when the agents' utilities are given by bandit feedback.

Pessimism meets VCG: Learning Dynamic Mechanism Design via Offline Reinforcement Learning · Introduction · 0.94

What it cites · 3 sentences without a confident label

Cites as background 1 paper

There are related works on how competition for users affects the provider's learning [ref] , bandits with collisions [ref] , and coordinated resource allocation [ref] .

Competing Bandits: The Perils of Exploration Under Competition · Related work · 0.98

Discussion

Know something about this paper? Leave a comment, or highlight any passage above to comment on it.