How to Use Prices for Efficient Online Matching
Terence Highsmith II · 2026
Read How to Use Prices for Efficient Online Matching by Terence Highsmith II (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-12181.txt.
Introduction
Highsmith designs an online matching algorithm for markets where agents arrive over time and must match at once, such as placing children with foster homes or patients with rooms. His Sequential Equilibrium Mechanism approximates large-market equilibria to pair arrivals with objects, and is efficient in the limit, fair, and strategy-proof with probability one. Simulations show it can substantially improve welfare, and a lab-in-the-field experiment with real caseworkers is planned.
Catalog record
| CREATOR | Terence Highsmith II |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 98253 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.12181
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
How to Use Prices for Efficient Online Matching Terence Highsmith II 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. (JEL C78, D47, D71) 1 Introduction Many matching markets feature stochastic, dynamic (”online”) arrivals of agents or objects that a market designer (e.g. firm or government) must allocate. 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. Unlike traditional online matching problems where the organization can discard arrivals, the settings referenced above feature arrivals that must be matched immediately upon arrival whenever possible. This constraint is known as greedy allocation . Greedy allocation problems may appear to be trivial: if an agent arrives, she must be matched, and allocating her most preferred object to her is constrained-efficient within the set of greedy allocations. In reality, agents often have indifferences in their preferences: two foster homes might be equally suitable for a child, two heterogeneous hospital rooms might be equally adequate for patient care, or two shelters might provide similar services to a homeless individual. Moreover, these preferences are often ordinal in lieu of a clear numeric objective. In these cases, randomly allocating one of the agent’s most preferred objects to her can unnecessarily jeopardize the welfare of future arrivals. Our online matching problem faces two core constraints: (1) greedy allocation and (2) coarse, ordinal preferences. Agents reveal their preferences upon arrival, and the goal is to find a matching that is greedy, fair (subject to the constraints), and ex-post efficient. Surprisingly, there is no online matching mechanism that satisfies any version of Pareto efficiency for ordinal preferences. We design a novel, randomized online matching mechanism that satisfies these constraints: the Sequential Equilibrium Mechanism (SEM). Our design is in two stages: (i) we solve a large market competitive equilibrium using a new equilibrium concept. We allot fake, token money to agents and solve for a competitive equilibrium that uses random prices to smooth agent demand. In stage (ii), SEM opens spot markets in each period. The spot markets solve a large market equilibrium for the realized arrivals and expected future demand, and we allocate objects according to the equilibrium allocation. SEM is a randomized mechanism that allocates lotteries to arrivals and immediately realizes the lottery at the end of each time period. We refer to the realized lotteries as ex-post lottieres and the realized allocations as ex-post allocations. Under careful use of token money, SEM is greedy. It ensures that arriving agents are allocated lotteries containing their most preferred objects whenever possible. Equivalently, every ex-post allocation within a time period is efficient with respect to the current arrivals and object supply. Moreover, SEM’s lotteries are equal-type envy-free. Agents arriving at the same time period do not envy each other’s lotteries. SEM is strategyproof with probability one : an agent’s strategic incentives to manipulate vanish as the number of arrivals per period grows large. Finally, our main result is that SEM is asymptotically efficient . SEM’s ex-post lottery is ordinally efficient with probability one as the number of arrivals per period grows. In contrast, it is impossible to design a greedy mechanism that achieves ex-post ordinal efficiency when the market is finite. Our results for SEM are very encouraging, but they are not definitive. That is, although SEM is asymptotically efficient, its finite sample performance is unknown. To test SEM’s empirical effects, we apply our theoretical results in the context of a U.S.-based nonprofit (henceforth, the Firm) that places children into temporary homes. The Firm is a national organization that contracts with state child welfare departments to find temporary, emergency homes for children that are at risk of abuse or neglect. In addition, the Firm offers pro-bono services to parents that voluntarily request emergency hosting for their children. In the Firm’s problem, children stochastically arrive over time and must be matched to a host home. Their current matching process is rudimentary: upon an child’s arrival, every host home receives a text message about the child, and the first home to respond can host the child. The Firm’s objective is to efficiently allocate children to homes, but this process was unable to accomplish their goal because even homes that are perfectly aligned with the Firm’s objective can fail to coordinate on efficient allocations. We present simulation results that compare Serial Dictatorship with Random Tie-Breaking (SD-RTB) to SEM. Upon arrival of children, SD-RTB selects a random priority order over the arrivals. In order, SD-RTB allocates to a child a random home among her most preferred homes. Since we have not yet obtained data on observed matches from the Firm, we use SD-RTB as a simplification to represent their existing matching process and simulate a simple market to compare the mechanisms. Thus, our simulations only compare two theoretical mechanisms. They do not provide counterfactuals relative to the ground truth. Our ongoing work with the Firm hopes to implement an experimental approach to assess the empirical effects of SEM. Our simulations analyzes the number of matches while varying the number of arrivals to assess SEM’s rate of convergence to efficiency. The simulations show that SEM delivers approximately 10% more matches than SD-RTB, a finding that is steady regardless of the market size. In line with our theoretical predicts, both mechanisms’ performance experience less variance as the arrival rate increases, demonstrating that aggregate uncertainty smooths out in large markets. Overall, our simulations suggest that SEM can substantially improve welfare in practice. The success of SEM relies on a careful solution to the large market problem. Pseudomarkets, originating with [ 22 ] ( [ 22 ] ), constitute the foundational approach to allocate indivisible objects to agents using competitive equilibria. In our case, agent preferences are ordinal with indifferences, making it technically challenging to prove equilibrium existence. An agent’s demand is a correspondence when agents have indifferences. Particularly, it is an ill-behaved correspondence that is fully discontinuous. However, restricting to prices that are not exactly equal to the budget constraint, the demand correspondence is upper hemicontinuous, suggesting that ”smoothing” over such prices could create upper hemicontinuous demand and allow the market designer to find prices that clear the market: \mathcal{D}=\mathcal{S} . Briefly, our technique is to solve a large-market allocation problem with random prices . Our equilibrium concept then focuses on setting expected demand equal to supply. Expected demand is the Aumann integral: integration over selections from the demand correspondence. Expected demand is convex-valued and upper hemicontinuous. We leverage this to apply Kakutani’s Fixed Point Theorem ala traditional existence arguments. Combining this with asymmetric budgets–larger for