we-solve (beta)

Econ-141 · economics · Economics

Congestion in matching markets

LLM status Open unverified

Statement

Original subject group: Mechanism design and market design

Audit classification: Published research agenda. The verified 2025 paper’s §6 explicitly proposes multiple signaling rounds and richer heterogeneity. The capped-interview BIC frontier is editorial.

Definitions and precise research target

Model and research target. Let $A$ be applicants and $J$ firms in a finite one-to-one matching market. Before interviews, agent $i$'s utility for potential partner $j$ is $v_j+B_{ij}$; interviewing reveals an additional score $C_{ij}$. The joint distribution of these scores and public values $v_j$ is specified. A protocol uses $r$ signaling rounds, at most $d$ outgoing signals per agent per round, and at most $k$ interviews per agent. Signals and interview invitations may depend on earlier messages and revealed scores. Final matches can use only interviewed pairs. An unmatched agent has utility zero. Define interim preferences using revealed total scores for interviewed partners and conditional expected scores for others. A pair blocks if both prefer each other to their final partners under these preferences. Determine the attainable tradeoff between total interviews, signaling rounds, and \[ E[\#\{i:i\text{ belongs to an interim blocking pair}\}], \] subject to Bayesian incentive compatibility of signaling and an explicitly specified invitation rule. Derive sufficient bounds and matching impossibility examples for richer public-quality heterogeneity and multi-round learning. State how correlations and unbalanced market sizes affect guarantees.

Definitions and maintained assumptions (editorial unless a source definition is named). Let $A,J$ be disjoint finite agent sets; a matching is a set of disjoint applicant--firm edges, and $M(i)=\varnothing$ means unmatched. Define both sides’ utilities separately, for example $U_a(j)=v^J_j+B_{aj}+C_{aj}$ and $U_j(a)=v^A_a+\widetilde B_{ja}+\widetilde C_{ja}$, with unmatched utility zero. Specify each agent’s initial information about these scores and the full correlated prior. An interview reveals the designated pair’s scores according to a declared signal kernel; posterior expected scores of un-interviewed partners incorporate information conveyed by signals and refusals. A pair blocks interim if both strictly prefer it under these posterior utilities, whether or not it interviewed; allowing it to form a final match is a distinct feasibility question. Count each agent involved in any blocking pair once. A multi-round signaling protocol includes invitations, acceptance, score revelation, posterior updating and final matching. Bayesian IC requires truthful signaling to be a best response at each reachable information history, under a specified equilibrium concept and off-path beliefs.

Variants and assumption changes

  1. Round--interview frontier (source direction, editorial criterion). In balanced random markets with stated i.i.d. scores and public qualities, let market size grow. Determine $(r,d,k)$ requirements for the expected fraction of agents in blocking pairs to tend to zero.
  2. Heterogeneous and correlated market (source direction, editorial criterion). Allow multiple quality tiers, unequal side sizes and score correlation. Characterize incentive-compatible signaling and distinguish almost stability from absence of every interim blocking pair.

References and source audit

  1. §6 Conclusion, printed p.19. Supports the stated research area; exact displayed specification is editorial. https://web.stanford.edu/~alroth/papers/NSF%20Grand%20Challenge.SBE%202020.%20Market%20Design.pdf
  2. §6 Conclusion, printed p.19. Supports the stated research area; exact displayed specification is editorial. https://arxiv.org/pdf/2501.14159
  1. Alvin E. Roth. 2010. Market Design: Understanding markets well enough to fix them when they’re broken. §1 Fundamental questions, pp.3–4. https://web.stanford.edu/~alroth/papers/NSF%20Grand%20Challenge.SBE%202020.%20Market%20Design.pdf.
  2. Maxwell Allman; Itai Ashlagi; Amin Saberi; Sophie H. Yu. 2025. From signaling to interviews in random matching markets. §6 Conclusion, p.19, October8,2025 revision. https://arxiv.org/pdf/2501.14159.

Common conventions: Source mathematical conventions

These conventions apply to each entry unless explicitly replaced.

Models and identification. A primitive model $m$ specifies all probability laws, feasible choices, information, equilibrium and measurement rules used by its target. The admissible class $\mathcal M$ is fixed independently of outcomes. If $P_O(m)$ is its observable probability law and $\tau(m)$ the target, its identified set at observable law $P$ is \[ \mathcal I_\tau(P)=\{\tau(m):m\in\mathcal M,\ P_O(m)=P\}. \] Point identification means that this set is a singleton. An empty set signals incompatibility of data and assumptions. Coordinate bounds need not describe the joint set. Bounds are sharp only if every retained target is attainable or arbitrarily approachable by compatible models. Finite bounds require explicit restrictions on unobserved quantities; unrestricted confounding, hidden wealth, extrapolation or arbitrary equilibrium selection can yield uninformative sets.

Causal interventions. A potential outcome $Y_i(p)$ is the outcome under a complete policy regime $p$, including timing, financing, information and market spillovers. The target population and units are fixed before treatment. With interference, use the complete assignment vector or a justified exposure mapping; individual no-interference notation alone cannot identify an economy-wide intervention. A difference of mean potential outcomes does not require the cross-world joint distribution. Conditioning on post-treatment migration, survival, enrollment or employment changes the estimand and needs separate justification.

Statistical statements. An estimator, confidence set, forecast or test specifies a sampling law, model class and loss/coverage criterion. Uniform $(1-\alpha)$-coverage means $\inf_{m\in\mathcal M}\Pr_m\{\tau(m)\in C_n\}\geq1-\alpha$, or an explicitly asymptotic version. The whole parameter space trivially has coverage, so informativeness requires a stated width, risk or power objective. A forecasting improvement is relative to a named benchmark, information set and evaluation population.

Equilibrium and optimization. An equilibrium comprises feasible plans, optimality, beliefs where needed, budget constraints and all market/resource clearing. The primitives or a stated benchmark define each correspondence $\mathcal E(p;m)$. Nonemptiness is assumed or proved, never inferred just from compact policy sets. A selected-equilibrium target uses a declared selection rule; a robust target quantifies over all permitted equilibria. Use suprema or infima unless attainment is established. An $\varepsilon$-optimal policy is feasible and within $\varepsilon$ of the finite optimum value. Report an empty feasible set separately.

Welfare and accounting. Normative utility, interpersonal normalization, social weights, numeraire, discounting and the use of public receipts are primitives. Behavioral utility need not coincide with the welfare criterion. Household welfare includes ownership income and rents once; adding profits again to compensating variation generally double-counts them. A monetary equivalent is defined by an explicit transfer and price convention, with monotonicity and range conditions. Average effects, mechanism contributions, transfers and welfare losses are different targets. Infinite sums require convergence and dynamic feasible plans require terminal or no-Ponzi conditions.

Source versions. A working-paper date, revision date and journal publication year are distinguished. A DOI for a journal version is not automatically the DOI of an earlier manuscript. Locators refer to the stated version and printed pages where specified. A metadata-only check does not verify a claim about a full-text conclusion. Every entry's source subsection narrows the provenance claim accordingly.

Statement licence: CC-BY-4.0 · Source file

Contributions 1

Econ-141-A1 · Exploration · LLM-generated · gpt 6 astra ultra ·

GPT 6 Astra Ultra attempt on Econ-141

Interview stability certificates and an exact congestion benchmark

Status: Unresolved. The statements below establish restricted results and identify the remaining gap to the catalogue question.

Abstract

We give a deterministic certificate that localizes every blocking pair to agents dissatisfied with an unobserved alternative. In a fully specified random market, we then compute the exact expected number of agents in blocking pairs after a one-interview protocol. The calculation distinguishes stability of the interviewed market from interim stability in the whole market. It does not solve the strategic information-design problem.

Short target and conventions

The catalogue seeks interview and signaling protocols with few interviews, few agents in interim blocking pairs, and incentives for truthful participation. Fix finite sets $A,F$ of applicants and firms and an interview graph $H\subseteq A\times F$. A final matching $\mu$ uses only edges of $H$ and is individually rational. Each agent has a utility for each potential partner and utility zero for being unmatched. Interviewed utilities are observed; an un-interviewed utility is its conditional expectation given the agent's information at the final history. These numbers specify the interim preference profile used below. A blocking pair strictly improves both utilities, whether or not that pair was interviewed.

An algorithm that finds a stable matching only in $H$ need not produce a stable matching for these full interim preferences. This distinction is substantive even with truthful reports and independent scores.

A deterministic certificate

Let $v_i(\mu(i))=0$ if $i$ is unmatched. For each agent put \[ d_i=\max\left(\{v_i(j):ij\notin H\}\cup\{-\infty\}\right) -v_i(\mu(i)),\qquad U=\{i:d_i>0\}. \] The empty-set convention means an agent who interviewed every possible partner is not in $U$.
Theorem (Localization of blocking agents): Suppose $\mu$ has no blocking pair among interviewed edges. Every blocking pair in the full interim market has both endpoints in $U$. In particular, the number $B(\mu)$ of agents belonging to at least one blocking pair satisfies \[ B(\mu)\le |U|,\qquad {\mathbb{E}} B(\mu)\le\sum_i{\mathbb{P}}(d_i>0). \] If the graph of strictly mutually preferred un-interviewed pairs on $U$ has no edges, $\mu$ is interim stable.
Proof: A blocking pair cannot be an interviewed edge by assumption. For an un-interviewed blocking pair $(i,j)$, strict preference implies $d_i\ge v_i(j)-v_i(\mu(i))>0$ and similarly $d_j>0$. Thus its two endpoints lie in $U$. The deterministic bound follows by taking the union of endpoints. Taking expectations and using linearity for the indicators of membership in $U$ gives the second bound. The last assertion follows from the same necessary condition. ∎
This certificate needs bounds on posterior utilities at the actual history. Replacing them by unconditional means is justified only if the protocol and observations preserve the required conditional independence.

One interview per agent: an exact calculation

Consider $n\ge2$ applicants and $n$ firms. For every pair, the applicant's score and the firm's score are independent Bernoulli$(p)$ variables, with $0<p<1$; all $2n^2$ scores are mutually independent. Agents have no additional private information before interviewing. Select a perfect pairing uniformly, independently of scores. Interview exactly those $n$ pairs. Reveal the two scores of each interviewed pair publicly. Match an interviewed pair if and only if both scores are one; otherwise leave its two members unmatched. Unmatched utility is zero.

Every un-interviewed score still has posterior mean $p$: conditioning on the random pairing and its revealed scores has not conditioned on any un-interviewed score. A failed pair has at least one endpoint that values its partner at zero. A matched agent values its partner at one.

Theorem (Exact number of blocking agents): Let $q=1-p^2$. The protocol is individually rational and stable in the interviewed graph. If $B_n$ is the number of agents in full interim blocking pairs, then \[ {\mathbb{E}} B_n=2nq\left(1-(p^2)^{n-1}\right). \] Consequently ${\mathbb{E}} B_n/(2n)\to1-p^2$ at fixed $p$. Allowing $p=p_n$, the expected fraction tends to zero if and only if $p_n\to1$.
Proof: There are no cross edges in the interviewed graph. A failed interviewed pair is not a strict block, and successful pairs are matched. Thus stability in that graph holds. A matched agent cannot strictly prefer another partner: its utility is one and an un-interviewed utility is $p<1$. Let $F$ count the failed interviewed pairs. Independence gives $F\sim\operatorname{Bin}(n,q)$.

If $F=0$, there are no unmatched agents. If $F=1$, the sole unmatched applicant and firm form the one failed interview, which is not a block. If $F\ge2$, every unmatched applicant can pair with the unmatched firm of a different failed pair. That edge is un-interviewed, so both endpoints strictly prefer its positive posterior utility $p$ to zero. The symmetric statement holds for every unmatched firm. Hence $B_n=2F{\mathbf{1}}\{F\ge2\}$ and \[ {\mathbb{E}} B_n=2\{{\mathbb{E}} F-{\mathbb{P}}(F=1)\} =2nq-2nq(1-q)^{n-1}. \] The fixed-$p$ limit follows immediately. If $q_n\to0$, the fraction is at most $q_n$. Conversely, any subsequence with $q_n\ge c>0$ has fraction at least $c[1-(1-c)^{n-1}]$, so a zero limit requires $q_n\to0$. ∎

Corollary (Unmatched fraction and blocking fraction): The expected unmatched fraction is $q$, whereas the expected blocking fraction is $q[1-(1-q)^{n-1}]$. Their difference is exactly $q(1-q)^{n-1}$. Thus unmatched agents and blocking agents are different statistics even in this simple market.
Proof: There are exactly $2F$ unmatched agents. Subtract the theorem's expression after dividing by $2n$. ∎
The absence of reports makes Bayesian truthfulness vacuous in this benchmark. It supplies no strategic-reporting theorem for a model with privately known types. Revealing both scores publicly is part of the mechanism, not an inference from private interviews.

What this rules out, and what it does not

One interview per agent together with stability in the interviewed graph is insufficient for asymptotically vanishing blocking fractions in this protocol. The result is not a lower bound for every protocol using one interview. Information before matching, correlation of match values, adaptive reassignment, or nontrivial signaling can change the law. The certificate suggests a precise goal for a richer protocol: control the number of agents whose posterior best un-interviewed option exceeds their assignment, while retaining incentive compatibility. Proving such control for a protocol with private types is the remaining catalogue problem.

References

  • [AASY] M. Allman, I. Ashlagi, A. Saberi, and S. H. Yu, From signaling to interviews in random matching markets, arXiv:2501.14159 (2025; version 2, 8 October 2025). https://arxiv.org/abs/2501.14159. Source for the signaling/interview research problem; the Bernoulli pairing calculation here is a separate restricted model.
  • [GS] D. Gale and L. S. Shapley (1962), College admissions and the stability of marriage, American Mathematical Monthly 69, 9--15. https://doi.org/10.2307/2312726. Background definition of pairwise stability.

Completion Estimate

15%

Go to contribution →