Asymptotic Optimality in Large Market Mechanisms

This direction is split into other directions: uncertainty-induced equilibrium stabilization, large-market efficiency convergence. Its last version stays readable and citable here.

Version 1 of 192 papers121 conceptsfrozen 2026-10-04

In mechanism design, there is a fundamental "trilemma" between three desirable properties: efficiency (maximizing total social welfare), budget balance (ensuring no external subsidies are needed and no money is wasted), and strategyproofness (ensuring participants have no incentive to lie). Classic results, such as the Myerson-Satterthwaite theorem, prove that for small-scale bilateral trades, you often cannot have all three.

However, a recurring insight across recent research is that these "impossibility" barriers are not brick walls, but rather hurdles that shrink as the number of participants grows. In large-scale systems, the inefficiencies and strategic distortions that plague small markets tend to vanish, a phenomenon known as asymptotic optimality.

The Power of Large Numbers

The core intuition behind this research direction is the "Law of Large Numbers" applied to economics. In a small auction, a single bidder with a high valuation can significantly influence the final price, creating an incentive to shade their bid. In a large market, however, the influence of any single participant becomes negligible.

Swaprava Nath demonstrates this in Efficiency and Budget Balance in General Quasi-linear Domains, proving that the "waste" required to maintain a balanced budget in strategyproof systems diminishes at a rate of $1/n$. As the number of participants $n$ increases, the social welfare cost of maintaining a balanced budget becomes mathematically negligible.

This transition from discrete, high-impact individuals to a "continuum" of agents is what allows complex systems to stabilize. Rahul Jain 0002 and Pravin Varaiya show that in bandwidth allocation, the "indivisibility" of goods—which usually causes market friction—becomes irrelevant in large-scale markets, allowing stable competitive prices to emerge naturally Combination Exchange Mechanisms for Efficient Bandwidth Allocation.

Vanishing Market Power in Double Auctions

Double auctions, where multiple buyers and sellers trade simultaneously, are notoriously difficult to balance. The MIDA (Multi Item-kind Double-Auction) and MUDA mechanisms, developed by researchers like Erel Segal-Halevi and Yonatan Aumann, use "random market halving" to achieve truthfulness.

By splitting the market and using one half to set prices for the other, these mechanisms sacrifice a small amount of efficiency to ensure no one can manipulate the price. Crucially, as shown in A Random-Sampling Double-Auction Mechanism, this efficiency loss approaches zero as the number of participants increases. The mechanism becomes "asymptotically efficient" because the statistical representative power of each market half improves with scale.

Budget Feasibility and the Large Market Assumption

In procurement auctions (where a buyer has a fixed budget to hire workers), the "Large Market Assumption" is a critical tool. This assumption states that the cost of any individual participant is negligible compared to the total budget.

Under this condition, the complexity of the problem collapses. Eric Balkanski and Jason Hartline demonstrate in Bayesian Budget Feasibility with Posted Pricing that simple "take-it-or-leave-it" posted prices—like those used on Amazon Mechanical Turk—perform just as well as the most complex, theoretically optimal auctions when the budget is large.

Similarly, Weiwei Wu and colleagues show in Budget Feasible Mechanisms Over Graphs that without this large-market property, a single high-cost participant can "break" the mechanism's efficiency. Scale acts as a buffer that protects the system from individual outliers.

Overcoming Impossibility in Bilateral Trade

Perhaps the most striking application of this principle is in group-based bilateral trade. While it is impossible for two individuals to trade efficiently without a subsidy, Yixuan Even Xu and Vincent Conitzer prove that trade between two groups (like countries) can reach perfect efficiency in the limit Non-Excludable Bilateral Trade Between Groups.

As long as the average valuation of the buyers exceeds the average cost of the sellers, the collective benefit of the trade eventually outweighs the individual incentives to misreport. The "impossibility" of trade is a small-sample artifact that dissolves in the face of statistical convergence.

From Complex Auctions to Simple Prices

The ultimate destination of this research is the "Law of One Price." In An Approximate "Law of One Price" in Random Assignment Games, Assaf Romm shows that in large matching markets, the range of possible stable wages shrinks toward zero.

This suggests that for large-scale systems, we don't need the heavy machinery of complex mechanism design. As markets grow:

  1. Strategic advantages vanish: Sincere behavior becomes a viable strategy, as seen in the Boston school choice mechanism Playing on a Level Field.
  2. Simple pricing wins: The revenue gap between dynamic and static pricing disappears Paul Dütting.
  3. Information gaps close: The cost of not knowing participant traits vanishes as competition increases Ningning Ding.

In essence, scale is a clarifying force. It transforms the chaotic, strategic interactions of a few players into the predictable, efficient behavior of a competitive market.

Papers in this version

Showing 60 of 92 papers.

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_asymptotic_optimality_in_large_market_me_d7273e97,
  title = {Asymptotic Optimality in Large Market Mechanisms},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/asymptotic-optimality-in-large-market-mechanisms/rdr_d7273e97528b4fa686129b82a979ddff},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_asymptotic_optimality_in_large_market_me_d7273e97_v1,
  title = {Asymptotic Optimality in Large Market Mechanisms},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/asymptotic-optimality-in-large-market-mechanisms/rdr_d7273e97528b4fa686129b82a979ddff/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}