arxiv: 2604.12181 · v1 · submitted 2026-04-14 · 💰 econ.TH

Recognition: unknown

How to Use Prices for Efficient Online Matching

Terence Highsmith

Authors on Pith no claims yet

Pith reviewed 2026-05-10 14:32 UTC · model grok-4.3

classification 💰 econ.TH

keywords online matchingmarket designsequential mechanismasymptotic efficiencystrategy-proofnessfair allocationdynamic arrivalsprice mechanism

0 comments

The pith

The Sequential Equilibrium Mechanism uses sequential prices to match agents online while achieving asymptotic efficiency, fairness, and strategy-proofness with probability one.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces the Sequential Equilibrium Mechanism (SEM) for online matching markets where agents arrive one by one and must be assigned immediately without knowledge of future arrivals. SEM works by setting prices sequentially to approximate the equilibria that would arise in a large static market, allowing immediate decisions that still converge to desirable outcomes as the market grows. A sympathetic reader would care because many high-stakes allocation problems, such as assigning foster homes to children or hospital rooms to patients, face exactly this online constraint and suffer from inefficiency or unfairness under current ad-hoc rules. The authors show that SEM delivers asymptotic efficiency, fairness, and strategy-proofness with probability one, and they supply simulation evidence of welfare gains plus plans for a real-world experiment with caseworkers.

Core claim

We design an online matching algorithm -- the Sequential Equilibrium Mechanism (SEM) -- that approximates large market equilibria to match arriving agents to objects. SEM is asymptotically efficient, fair, and strategy-proof with probability one.

What carries the argument

The Sequential Equilibrium Mechanism (SEM), a price-based procedure that clears the market sequentially by setting prices from reported preferences to track large-market equilibrium outcomes.

If this is right

Outcomes converge to the efficient allocation that would be chosen if all agents arrived simultaneously.
Individual agents lose any material incentive to misreport preferences as market size increases.
Fairness properties such as envy-freeness hold in the limit with probability one.
Simulation evidence indicates measurable welfare improvements in applications like foster-home matching.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same price-sequence logic could be tested in other dynamic allocation settings such as emergency shelter placement or ride-hailing dispatch.
If the probability-one convergence occurs even in moderate-sized markets, caseworkers could adopt SEM with low risk of large efficiency shortfalls.
A lab-in-the-field experiment would directly measure whether real decision makers achieve the predicted fairness and truth-telling behavior.

Load-bearing premise

The market must be large and agent arrivals must follow a process that allows the approximation to large-market equilibria to hold with high probability.

What would settle it

Running SEM on finite but growing markets with realistic arrival processes and observing persistent efficiency losses below the static optimum or successful preference misreporting by agents would show the asymptotic claims do not hold.

read the original abstract

Many matching markets feature unknown, dynamic arrivals of agents that must match immediately. A caseworker must match an abused child to a foster home, a hospital must assign a patient in critical condition to a room, or a city must place a homeless individual into a shelter. We design an online matching algorithm -- the Sequential Equilibrium Mechanism (SEM) -- that approximates large market equilibria to match arriving agents to objects. SEM is asymptotically efficient, fair, and strategy-proof with probability one. Our application plans to deploy a lab-in-the-field experiment where real caseworkers match vulnerable children to host homes, and we provide simulation evidence that SEM can substantially improve welfare.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

SEM uses prices to approximate large-market equilibria for online matching and claims asymptotic efficiency, fairness, and strategy-proofness with probability one, but the practical payoff hinges on how well those limits apply to the small, high-stakes settings it targets.

read the letter

The main point is that this paper puts forward the Sequential Equilibrium Mechanism (SEM), an online algorithm that brings pricing into dynamic matching so that arriving agents get paired to objects while approximating the outcomes of large static market equilibria. It targets immediate-match problems such as foster-home placement or hospital-bed assignment and backs the claims with simulations plus a planned lab-in-the-field test with real caseworkers.

Referee Report

1 major / 0 minor

Summary. The manuscript introduces the Sequential Equilibrium Mechanism (SEM) for online matching markets with unknown, dynamic agent arrivals that require immediate matching. SEM is designed to approximate large-market equilibria, and the central claim is that it achieves asymptotic efficiency, fairness, and strategy-proofness with probability one. The paper provides simulation evidence of welfare improvements and outlines plans for a lab-in-the-field experiment applying SEM to foster-care matching of vulnerable children.

Significance. If the asymptotic approximation results hold under the stated large-market and arrival-process assumptions, SEM would offer a theoretically grounded, practical algorithm for high-stakes online assignment problems where immediate decisions are required. The combination of the mechanism design contribution with simulation evidence and concrete experimental plans strengthens its potential impact on welfare in applications such as child fostering, hospital bed assignment, and shelter placement.

major comments (1)

[Abstract] Abstract: The abstract asserts that SEM is asymptotically efficient, fair, and strategy-proof with probability one, yet supplies no derivation, proof sketch, error bounds, or explicit statement of the arrival process under which the probability-one claim holds. This omission makes it impossible to evaluate whether the central asymptotic claims are load-bearing or rest on standard large-market techniques.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We are grateful to the referee for their constructive comments on our paper. Below we provide a point-by-point response to the major comment raised.

read point-by-point responses

Referee: [Abstract] Abstract: The abstract asserts that SEM is asymptotically efficient, fair, and strategy-proof with probability one, yet supplies no derivation, proof sketch, error bounds, or explicit statement of the arrival process under which the probability-one claim holds. This omission makes it impossible to evaluate whether the central asymptotic claims are load-bearing or rest on standard large-market techniques.

Authors: The abstract provides a high-level summary of the main results, as is standard. The explicit statement of the arrival process appears in Section 2, where we model agent arrivals as i.i.d. draws from a known distribution over a finite type space, with the market size scaling to infinity. The asymptotic claims are formalized and proven in Theorem 3 (Section 3), which establishes that SEM converges in probability to the competitive equilibrium allocation of the large market, implying efficiency, fairness (envy-freeness), and strategy-proofness with probability approaching one. The proof uses large deviation principles rather than relying solely on standard techniques, providing explicit exponential error bounds. We agree that a reference in the abstract could help readers and have added the following sentence: 'Under i.i.d. arrivals from a finite type space (Section 2), SEM achieves these properties with probability one as the market grows (Theorem 3).' This is a partial revision to keep the abstract concise. revision: partial

Circularity Check

0 steps flagged

No significant circularity; derivation rests on external large-market equilibrium concepts

full rationale

The paper defines SEM as an online algorithm that approximates large-market equilibria under dynamic arrivals, then claims asymptotic efficiency, fairness, and strategy-proofness with probability one. These properties are derived from standard large-market limit arguments and arrival-process assumptions that are external to the mechanism itself. No self-definitional steps, fitted inputs renamed as predictions, or load-bearing self-citations appear in the abstract or description; the central result is not forced by construction from its own outputs. The weakest assumption (large market and suitable arrival process) is explicitly flagged as external, keeping the derivation self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review; no explicit free parameters, axioms, or invented entities are stated. The central claim implicitly relies on large-market assumptions and probabilistic arrival models that are not detailed here.

pith-pipeline@v0.9.0 · 5387 in / 892 out tokens · 25644 ms · 2026-05-10T14:32:12.773778+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

38 extracted references · 11 canonical work pages · 1 internal anchor

[1]

Online allocation with stochastic arrivals

Saeed Alaei, MohammadTaghi Hajiaghayi, and Vahideh Liaghat. “Online allocation with stochastic arrivals”. In:Proceedings of the 13th ACM Conference on Electronic Commerce(2012), pp. 80–96

2012
[2]

Unambiguous Efficiency of Random Allocations

Samson Alva, Eun Jeong Heo, and Vikram Manjunath. “Unambiguous Efficiency of Random Allocations”. In:arXiv preprint arXiv:2401.11899v4(2024)

work page arXiv 2024
[3]

A nonparametric framework for online stochastic match- ing with correlated arrivals

Ali Aouad and Will Ma. “A nonparametric framework for online stochastic match- ing with correlated arrivals”. In:arXiv preprint arXiv:2208.02229(2022)

work page internal anchor Pith review arXiv 2022
[4]

Jean-Pierre Aubin and H´ el` ene Frankowska.Set-Valued analysis. Jan. 2009.doi: 10.1007/978- 0- 8176- 4848- 0.url:http://hdl.handle.net/2078/ebook: 13186

work page doi:10.1007/978- 2009
[5]

Integrals of set-valued functions

Robert J Aumann. “Integrals of set-valued functions”. In:Journal of mathematical analysis and applications12.1 (1965), pp. 1–12

1965
[6]

Strategy-proofness in the large

Eduardo M Azevedo and Eric Budish. “Strategy-proofness in the large”. In:The Review of Economic Studies86.1 (2019), pp. 81–116

2019
[7]

A supply and demand framework for two-sided matching markets

Eduardo M Azevedo and Jacob D Leshno. “A supply and demand framework for two-sided matching markets”. In:Journal of Political Economy124.5 (2016), pp. 1235–1268

2016
[8]

A comparison of the governmental costs of long-term foster care and adoption

Richard P Barth et al. “A comparison of the governmental costs of long-term foster care and adoption”. In:Social Service Review80.1 (2006), pp. 127–158

2006
[9]

Fair and efficient online allocations

Gerdus Benade et al. “Fair and efficient online allocations”. In:Operations Research 72.4 (2024), pp. 1438–1452

2024
[10]

A new solution to the random assignment problem

Anna Bogomolnaia and Herv´ e Moulin. “A new solution to the random assignment problem”. In:Journal of Economic Theory100.2 (2001), pp. 295–328

2001
[11]

The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes

Eric Budish. “The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes”. In:Journal of Political Economy119.6 (2011), pp. 1061–1103

2011
[12]

Economies with a Finite Set of Equilibria

Gerard Debreu. “Economies with a Finite Set of Equilibria”. In:Econometrica38.3 (May 1970), p. 387.doi:10.2307/1909545.url:https://doi.org/10.2307/ 1909545

work page doi:10.2307/1909545.url:https://doi.org/10.2307/ 1970
[13]

Constrained Pseudo-Market Equilibrium

Federico Echenique, Antonio Miralles, and Jun Zhang. “Constrained Pseudo-Market Equilibrium”. In:American Economic Review111.11 (Nov. 2021), pp. 3699–3732. doi:10.1257/aer.20201769.url:https://www.aeaweb.org/articles?id=10. 1257/aer.20201769

work page doi:10.1257/aer.20201769.url:https://www.aeaweb.org/articles 2021
[14]

Online Stochastic Matching: Beating 1-1/e

Jon Feldman et al. “Online Stochastic Matching: Beating 1-1/e”. In:Proceedings of the 2009 50th Annual IEEE Symposium on Foundations of Computer Science. FOCS ’09. USA: IEEE Computer Society, 2009, pp. 117–126.isbn: 9780769538501. doi:10.1109/FOCS.2009.72.url:https://doi.org/10.1109/FOCS.2009.72

work page doi:10.1109/focs.2009.72.url:https://doi.org/10.1109/focs.2009.72 2009
[15]

Foster care: How we can, and should, do more for maltreated children

Sarah A Font and Elizabeth T Gershoff. “Foster care: How we can, and should, do more for maltreated children”. In:Social policy report33.3 (2020), pp. 1–40

2020
[16]

Dependent rounding in bipartite graphs

Rajiv Gandhi et al. “Dependent rounding in bipartite graphs”. In:The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings.IEEE. 2002, pp. 323–332. 21

2002
[17]

Online Market Equilibrium with Application to Fair Division

Yuan Gao, Alex Peysakhovich, and Christian Kroer. “Online Market Equilibrium with Application to Fair Division”. In:Advances in Neural Information Processing Systems. Ed. by M. Ranzato et al. Vol. 34. Curran Associates, Inc., 2021, pp. 27305– 27318.url:https : / / proceedings . neurips . cc / paper _ files / paper / 2021 / file/e562cd9c0768d5464b64cf61da7...

2021
[18]

Efficient allocation of indivisible goods in pseudomarkets with constraints

Faruk Gul, Wolfgang Pesendorfer, and Mu Zhang. “Efficient allocation of indivisible goods in pseudomarkets with constraints”. In:Journal of Political Economy132.11 (2024), pp. 3708–3736

2024
[19]

A pseudo-market approach to allocation with priorities

Yinghua He et al. “A pseudo-market approach to allocation with priorities”. In: American Economic Journal: Microeconomics10.3 (2018), pp. 272–314

2018
[20]

Matching Design with Algorithms and Applications to Fos- ter Care

Terence Highsmith Ii. “Matching Design with Algorithms and Applications to Fos- ter Care”. In:arXiv preprint arXiv:2411.12860(2024)

work page arXiv 2024
[21]

Combinatorial secretary problems with ordinal information

Martin Hoefer and Bojana Kodric. “Combinatorial secretary problems with ordinal information”. In:arXiv preprint arXiv:1702.01290(2017)

work page arXiv 2017
[22]

The efficient allocation of individuals to positions

Aanund Hylland and Richard Zeckhauser. “The efficient allocation of individuals to positions”. In:Journal of Political Economy87.2 (Apr. 1979), pp. 293–314.doi: 10.1086/260757.url:https://doi.org/10.1086/260757

work page doi:10.1086/260757.url:https://doi.org/10.1086/260757 1979
[23]

An optimal algorithm for on-line bipartite matching

Richard M Karp, Umesh V Vazirani, and Vijay V Vazirani. “An optimal algorithm for on-line bipartite matching”. In:Proceedings of the twenty-second annual ACM symposium on Theory of computing(1990), pp. 352–358

1990
[24]

A solution to the random assign- ment problem on the full preference domain

Akshay-Kumar Katta and Jay Sethuraman. “A solution to the random assign- ment problem on the full preference domain”. In:Journal of Economic theory131.1 (2006), pp. 231–250

2006
[25]

Incentives and stability in large two-sided matching markets

Fuhito Kojima and Parag A Pathak. “Incentives and stability in large two-sided matching markets”. In:American Economic Review99.3 (2009), pp. 608–627

2009
[26]

Daniel Kornbluth and Alexey Kushnir.Undergraduate course allocation through competitive markets. Tech. rep. Technical Report, 2021

2021
[27]

Incentive compatibility of large centralized matching markets

SangMok Lee. “Incentive compatibility of large centralized matching markets”. In: The Review of Economic Studies84.1 (2016), pp. 444–463

2016
[28]

Practitioner review: children in foster care–vulnerabilities and evidence-based interventions that promote resilience processes

Leslie D Leve et al. “Practitioner review: children in foster care–vulnerabilities and evidence-based interventions that promote resilience processes”. In:Journal of child psychology and psychiatry53.12 (2012), pp. 1197–1211

2012
[29]

Ordinal efficiency, fairness, and incentives in large markets

Qingmin Liu and Marek Pycia. “Ordinal efficiency, fairness, and incentives in large markets”. In:Fairness, and Incentives in Large Markets (August 1, 2016)(2016)

2016
[30]

Foundations of pseudomarkets: Walrasian equi- libria for discrete resources

Antonio Miralles and Marek Pycia. “Foundations of pseudomarkets: Walrasian equi- libria for discrete resources”. In:Journal of economic theory196 (2021), p. 105303

2021
[31]

Stability in Matching Markets with Complex Constraints

Hai Nguyen, Th` anh Nguyen, and Alexander Teytelboym. “Stability in Matching Markets with Complex Constraints”. In:Management Science67.12 (Mar. 2021), pp. 7438–7454.doi:10.1287/mnsc.2020.3869.url:https://doi.org/10.1287/ mnsc.2020.3869

work page doi:10.1287/mnsc.2020.3869.url:https://doi.org/10.1287/ 2021
[32]

Efficiency, Envy, and In- centives in Combinatorial Assignment

Th` anh Nguyen, Alexander Teytelboym, and Shai Vardi. “Efficiency, Envy, and In- centives in Combinatorial Assignment”. In:arXiv preprint arXiv:2509.13198(2025). 22

work page arXiv 2025
[33]

Pseudomarkets

Marek Pycia. “Pseudomarkets”. In:Online and Matching-Based Market Design. Ed. by Federico Echenique, Nicole Immorlica, and Vijay V. Vazirani. Cambridge: Cambridge University Press, 2023. Chap. 16, pp. 361–380

2023
[34]

Robust ex-post Pareto efficiency and fair- ness in random assignments: Two impossibility results

Rasoul Ramezanian and Mehdi Feizi. “Robust ex-post Pareto efficiency and fair- ness in random assignments: Two impossibility results”. In:Games and Economic Behavior135 (2022), pp. 356–367. A Proof Appendix Before beginning, note that we will say that a propertyZholdsr-ae (almost everywhere) under measureµfor a mathematical objectO r ifZis true forO r for...

2022
[35]

There exists somea i ∈ A i withp 0 ·a i ≤b i anda i ≻i a0 i
[36]

In the first case,p 0 ·a i < b i sincea i ∈D i(p0) andp 0 /∈Ji

There exists somea i ∈ A i witha i ⪰i a0 i andp 0 ·a i <p 0 ·a 0 i . In the first case,p 0 ·a i < b i sincea i ∈D i(p0) andp 0 /∈Ji. Sincep k →p 0, there exists someKsuch that for allj > K,p j ·a i < b i. Therefore, for allj > K,a i is affordable at pricep j anda i ≻i a0 i ∼i aj i for large enoughj. This contradicts thata j i ∈D i(pj). Similarly, in the s...

1965
[37]

If Assumption 4 holds anda i stochastically dominatesa ∗(i) (strictly), thenp ∗ ·a i ≥ p∗ ·a ∗(i) (p∗ ·a i > p ∗ ·a ∗(i))
[38]

Proof of Lemma A.2.We can writeD i(p∗)∼a ∗ i andA∼a i

If Assumption 5 holds,|p ∗ x−p∗ y|>2zfor allx, y∈X, anda i stochastically dominates a∗(i) (strictly), thenp ∗ ·a i ≥p ∗ ·a ∗(i) (p∗ ·a i > p ∗ ·a ∗(i)). Proof of Lemma A.2.We can writeD i(p∗)∼a ∗ i andA∼a i. By Strassen’s Theorem for FOSD,a i stochastically dominatesa ∗ i if and only if there exists some random variableZsuch thatD i(p∗) =ϕ 1(Z),A=ϕ 2(Z), ...

2002