Stability magnifies attention costs in matching markets: when each agent inspects d partners on average, stable clearing leaves an unmatched share that falls like e^{-√d}, far slower than the e^{-d} rate achievable by maximum matching. Platforms that retain off‑screen authorizations and use limited‑attention DA can reclaim much of the lost matches, but doing so requires explicit authorization state (bits) and additional discovery/implementation complexity.

Main Finding

Stable clearing on markets with limited attention (where each agent can evaluate only a small number of partners) imposes a large allocation cost relative to the maximum feasible matching on the same set of discovered opportunities. When the cumulative executable opportunity graph has average degree d, the fraction unmatched under any stable rule falls like exp(−√d) (up to lower-order terms), while a maximum matching on the same graph leaves only about exp(−d) unmatched. Separately, maintaining “off‑screen” valid authorizations (memory/state) is necessary to implement deferred-acceptance–style clearing without re-querying users; an algorithm (LA-DA) that preserves authorizations and updates tentative holdings as eligibility changes restores proposer-optimal stability on the current on-screen graph and reengages dormant pairs. Adaptive discovery rules (with access to exact next-best information and persistent execution rights) can save a logarithmic factor in reached proposals versus independent exposure.

Key Points

• The core comparison fixes the realized cumulative executable opportunity graph (edges are pairs that became mutually executable) and compares:

  • any ex post stable allocation (i.e., any stable matching on that graph), and
  • a maximum-cardinality matching on the same graph. Because every stable matching has the same matched set, differences isolate the cost of imposing stability (not discovery or information).

• Asymptotic loss formulas (balanced independent-preference random graph with edge probability d/n):

  • Stable unmatched share ε_stab(d) satisfies ε_stab(d) ≍ exp(−√d) as d → ∞.
  • Maximum-matching unmatched share ε_max(d) ≍ exp(−d) as d → ∞.
  • Intuition: stability imposes two-sided ranking constraints that reduce effective usable depth from d to order √d.

• Practical implications of the exponent gap:

  • To achieve the same high match rate (e.g., 99%), stability requires many more discovered opportunities per person than feasibility alone (table in paper: ~21 opportunities per person under stability vs ~5 under feasibility for 99% matching).

• Dynamic/implementation problem: nonmonotone consideration breaks the “rejection is final” property of classical DA.

  • If an earlier rejected proposal becomes relevant later because the active set changed, re-submission consumes scarce attention.
  • Theorem (authorization-state lower bound): if k off‑screen authorizations can affect the final DA assignment, any deterministic, zero-error, query-neutral implementation must distinguish 2^k histories — i.e., requires at least k bits of retained authorization state. Forgetting pivotal authorizations forces re-querying users or yields incorrect outcomes.

• LA-DA (Limited-Attention Deferred Acceptance):

  • Preserves retained authorizations (ledger); treats rejected proposals as potentially dormant rather than permanently irrelevant.
  • Updates tentative holders online as eligibility changes.
  • Theorem: LA-DA terminates, respects capacity constraints, and produces proposer-optimal stable and Pareto-efficient outcomes on the final consideration graph.
  • Optional off-screen settlement: if the institution permits execution of any retained pair regardless of current eligibility, LA-DA can clear the cumulative ledger instead (this is a distinct extension).

• Discovery and proposal-efficiency:

  • With persistent execution rights and access to an exact next-best preference oracle, revealing only the next proposal reached by DA reproduces the full-information stable matching with expected O(n log n) proposals.
  • Homogeneous static exposure (independent random discovery) typically requires Θ(n log^2 n) edges to support a complete stable matching — the adaptive rule saves a logarithmic factor in reached proposals (conditional on correct next-best info).
  • Learning next-best choices is a separate information cost; choosing which columns to process under heterogeneous attention is NP-complete (budget-allocation hardness).

• Empirical evidence:

  • Speed-dating dataset replay:
  • On a stricter graph (pairs who both requested another date): proposal-directed discovery uses 1.14 executable opportunities/proposer and matches 60.8% of the short side. Random exposure with same budget yields 51.0% stable match; maximum matching on the same random edges reaches 56.2% — separating discovery inefficiency from same-graph stability loss.
  • On the broader graph (every observed date treated as acceptable): proposal path matches the short side completely using 3.65 opportunities/proposer; random stable clearing at the same budget matches 85.9%, while feasibility reaches 95.3%.
  • Chilean school choice (2024 admissions): among 117,409 applicants carried into wait-list allocation, 9,502 accepted a higher-ranked or new placement from the original ranking — illustrating that earlier applications/authorizations remained consequential at scale.

• Formal verification: controller, authorization-state lower bound, ledger settlement, and blocking-directed recommendation results were checked in Lean; large-market probability theorems are proved analytically.

Data & Methods

• Theoretical methods:

  • Random-graph asymptotics: consider balanced markets with n agents per side; cumulative executable edges independently included with probability d/n, yielding asymptotic expected degree d.
  • Combine local fixed-point analysis (Poisson thinning, uniform rank marks) and correlation decay on marked Poisson trees to derive the stable-match limit (Arnosti 2015 specialized).
  • Use maximum-matching limits (Bordenave et al. 2013) for the feasibility benchmark.
  • Prove lower bounds on authorization-state via combinatorial constructions showing 2^k indistinguishable histories unless k bits retained.
  • Define and analyze LA-DA (online algorithm) proving termination and stability properties.
  • Proposal count bounds: mix classical DA proposal analysis and random-graph degree results to derive O(n log n) vs Θ(n log^2 n) comparisons.

• Complexity results:

  • Selecting which receiver columns (which locations/sets to reveal/process) under heterogeneous attention costs is NP-complete; isolated-pair restriction remains weakly NP-complete.

• Empirical methods:

  • Speed-dating: replay experiments on 21 finite markets with nearly complete bilateral ratings and approval decisions. The study hides edges to simulate limited attention and replays different clearing/discovery procedures on the realized graph to separate discovery vs stability losses. Tests for order effects (ratings drift) use observed encounter order.
  • Chilean administrative data: track applicants carried into wait-list stage and observe whether retained earlier applications resulted in accepted better/new placements.

• Verification: several algorithmic and state distinctions were machine-checked in Lean to avoid subtle state/memory specification errors.

Implications for AI Economics

• Attention as an economic constraint in two-sided matching:

  • Platforms that control visibility/recommendations materially shape the feasible graph of executable opportunities. Limited attention is not only a consumer-choice friction but changes matchability and aggregate allocation when stability is required.
  • Stability magnifies attention scarcity: to reach the same match rates, platforms need substantially more discovered opportunities per user than a feasibility-only benchmark suggests.

• Design implications for recommender systems and platform state:

  • Memory (retaining authorizations/applications off-screen) is an economic state variable: forgetting valid authorizations imposes re-querying costs and reduces allocation quality or correctness. Platform architecture should explicitly support persistent authorizations or an off‑screen ledger when DA-style clearing is used under changing visibility.
  • Stateless/reactive designs that drop prior authorizations will either need to re-engage users (consuming attention) or risk incorrect match outcomes.

• Algorithmic policy and operational trade-offs:

  • Investing in smarter, adaptive discovery (e.g., proposer-directed or blocker-directed recommendations, next-best oracles) can substantially improve proposal efficiency and match rates, relieving attention requirements. However, adaptive algorithms may need richer preference information (next-best choices), which itself carries elicitation costs.
  • There is a computational/design boundary: optimal allocation of limited attention across many receiver columns is NP-hard; platforms will need heuristics or approximate/adaptive policies rather than global optimal planning.

• Welfare and policy for centralized matching institutions:

  • Centralized systems (e.g., school choice) should preserve earlier authorizations and ranking state across multi-stage processes (waitlists, reallocation) because retained preferences/applications can lead to higher-ranked acceptances without re-elicitation.
  • Policymakers and platform designers must account for the joint effect of attention limits and stability constraints when setting visibility, recommendation budgets, and rules for preserving or executing off-screen authorizations.

• Implications for modeling AI-enabled attention interfaces:

  • Models of platform influence and attention should incorporate (i) the graph-forming (discovery) stage separately from clearing, (ii) the possibility of dormant/retained links, and (iii) the cost of re-querying users. Mechanism design and evaluation of matching platforms powered by AI recommenders must treat memory/state and attention as endogenous design choices with welfare consequences.

Overall, the paper shows that limited attention substantially increases the opportunity cost of imposing stability, that persistent authorization is necessary to avoid re-query costs, and that adaptive discovery plus persistent execution rights can yield large efficiency gains — but at the expense of information elicitation and algorithmic complexity.