PaperlayerView exact revision on arXiv

Source-linked AI summary

The Power of Simple Mechanisms: A Tight $e$-Approximation for Gains from Trade in Matching Markets

Xiaohui Bei, Wenhao Wu, Shengwei Zhou

arXiv:2609.37997v1cs.GT

TL;DR

The paper asks how well GRO approximates first-best GFT in downward-closed matching markets, where private information limits attainable efficiency. It compares first-best edge-selection regions with one-sided posted-price profits and proves GRO’s exact worst-case fraction is 1/e, with a tight construction.

  • Problem

    The worst-case first-best GFT guarantee of GRO in matching markets remained between known lower and upper bounds.

    Source: §1 · p. 2

  • Method

    The proof compares first-best GFT on edge-selection regions with profits from posted prices optimized on their horizontal and vertical sections.

    Source: §1.2 · p. 4

  • Results

    GRO obtains at least a 1/e fraction of first-best GFT in downward-closed matching markets, and this guarantee is tight.

    Source: §1 · p. 2, §5 · p. 21

  • Takeaways & Limitations

    In bilateral trade, the result gives the random-offerer mechanism a 1/e fraction of first-best GFT.

    Source: §5 · p. 21

    The tight construction does not settle GRO’s exact guarantee for ordinary bipartite matching without additional feasibility constraints; the exact bilateral worst-case guarantee also remains unknown.

    Source: §5 · p. 21

Abstract

from arXiv · show

We study how well simple mechanisms approximate gains from trade (GFT) in two-sided matching markets with independent buyer values and seller costs, where feasible outcomes form an arbitrary downward-closed family of matchings. This model includes bilateral trade and double auctions as special cases. We focus on the Generalized Random-Offerer (GRO) mechanism, which is an equal mixture of the Generalized Sellers-Offering Mechanism (GSOM) and the Generalized Buyers-Offering Mechanism (GBOM). We determine GRO's exact worst-case approximation ratio with respect to first-best GFT, showing that it is $e$. This improves the previous $3.15$ approximation guarantee (Babaioff et al. STOC 2026) for the same mechanism. In bilateral trade, the result implies a $1/e$ guarantee for the random-offerer mechanism, improving the previous $1/\pi$ bound (Jo 2026). Our analysis uses a two-dimensional inequality in quantile space to compare first-best GFT with optimal one-sided auction profits. For each potential trade, we identify the region of buyer values and seller costs for which the first-best allocation selects that trade, and then randomly shrink this region in quantile space, yielding posted-price rules whose expected profits can be evaluated exactly. We establish tightness of the $e$ approximation by constructing markets with regular type distributions, pairwise disjoint trading edges, and a single knapsack constraint. On these instances, GRO's expected GFT approaches a $1/e$ fraction of first-best GFT, therefore ruling out any better guarantee even under these restrictions.

1 Introduction

The paper closes the gap in GRO’s worst-case first-best guarantee for downward-closed matching markets, proving the exact fraction is 1/e. It also outlines a quantile-space proof that turns local posted-price profits into feasible one-sided auctions.

1 Introduction

  • First-best GFT is the sum of buyer values minus seller costs, but private information prevents mechanisms from achieving the first-best benchmark while satisfying the stated incentive and budget requirements.Earlier GRO bounds left a gap between its best known lower and upper guarantees in matching markets.Source: §1 · p. 2

1.1 Our Results

  • GRO’s exact worst-case first-best GFT fraction is 1/e in downward-closed matching markets, and the guarantee is tight.The result improves the prior 1/3.15 guarantee.Source: §1 · p. 2, §1.1 · p. 3
  • Tightness holds with regular types on [0, 1], pairwise disjoint trading edges, and a single knapsack constraint.Along the constructed instances, GRO’s expected GFT approaches 1/e of first-best GFT.Source: §1.1 · p. 3, §1.2 · p. 5
  • In bilateral trade, the result gives the random-offerer mechanism a 1/e first-best GFT guarantee, improving the previous 1/π bound.GRO reduces to the random-offerer mechanism in bilateral trade.Source: §1.1 · p. 3

1.2 Technical overview

  • For each edge, first-best selection defines a down-set in independent buyer and seller quantile ranks; the proof compares its GFT with section-specific posted-price profits.The buyer and seller ranks become correlated conditional on first-best selecting the edge, so an independent bilateral-trade guarantee does not directly apply.Source: §1.2 · pp. 3–4
  • Randomly contracting the region yields horizontal and vertical posted-price rules whose expected local profit is exactly 1/e of the region’s GFT.The proof evaluates buyer and seller contributions separately, and the argument also applies to integrable quantiles with point masses.Source: §1.2 · p. 4, Figure 1 · p. 4
  • Stable partners let the local prices become truthful one-sided auctions; downward closedness keeps accepted edges feasible, allowing the local bounds to sum to a market-wide guarantee.Each agent has at most one active offer, independent of that agent’s own report.Source: §1.2 · pp. 3, 5

1.3 Other related work

  • Unlike Jo’s Lagrangian comparison, this analysis constructs posted prices on contracted trade regions and evaluates buyer and seller contributions separately.The proof builds on rank-space edge decomposition and down-set contractions, with a different local objective and choice of scales.Source: §1.3 · p. 7

2 Preliminaries

The preliminaries define a matching market with independent private buyer values and seller costs, then set out one-sided auction-profit benchmarks for comparing mechanisms with first-best gains from trade.

2.1 Model and notation

  • The market has buyers and sellers trading one item along feasible matching edges, with independent nonnegative types and downward-closed feasibility.First-best GFT is the maximum feasible surplus for a realized type profile; the model assumes finite first moments.Source: §2.1 · p. 7, §2 · p. 7
  • Independent uniform ranks represent buyer values and seller costs, with smaller buyer ranks indicating higher values and smaller seller ranks indicating lower costs.Thresholds can serve a chosen buyer quantile mass or procure from a chosen seller quantile mass; boundary types are randomized at atoms.Source: §2.1 · p. 8

2.2 One-sided benchmarks

  • The proof compares first-best GFT with seller-side buyer-auction profit and buyer-side procurement-auction profit, each optimized subject to BIC and interim IR.Seller costs are parameters in the seller-side problem; buyer values are parameters in the buyer-side problem.Source: §2.2 · p. 8
  • GSOM and GBOM implement the corresponding one-sided optima while satisfying DSIC, ex-post IR, and ex-ante WBB.One-sided profit relates to GFT by subtracting the strategic side’s utility.Source: §2.2 · p. 9

3 An 𝑒-Approximation for Matching Markets

This section proves that GRO obtains at least a 1/e fraction of first-best GFT in downward-closed matching markets and outlines why the guarantee is attainable through feasible one-sided auctions. Its proof builds on first-best edge-selection regions, section-level posted-price bounds, and a random contraction argument.

3 An 𝑒-Approximation for Matching Markets

  • GRO obtains at least a 1/e fraction of first-best GFT in the stated independent-type, downward-closed matching-market setting.GRO mixes GSOM and GBOM with equal probability and is DSIC, ex-post IR, and ex-ante WBB.Source: §3 · p. 10

3.1 First-best edge-selection regions

  • First-best edge-selection regions are down-sets in endpoint quantiles, and the same monotonicity yields a stable partner for each agent when matched.These regions can be nonrectangular because selecting an edge may depend jointly on buyer and seller ranks; first-best GFT decomposes across edges.Source: §3.1 · pp. 11–12

3.2 A local bound on GFT

  • On each horizontal or vertical section of a down-set, the best admissible posted-price profit is compared with that section’s contribution to first-best GFT.In the uniform triangular example, first-best GFT is 1/6 and each of the two section benchmarks is 1/12.Source: §3.2 · pp. 12–13

3.3 From local bounds to the approximation guarantee

  • Stable partners let the construction offer each buyer at most one report-independent threshold, while accepted edges remain within the realized first-best matching.Downward closedness therefore makes the accepted edges feasible; the symmetric procurement construction realizes the seller-side benchmarks as well.Source: §3.3 · pp. 13–14

3.4 Proof of the local bound on GFT

  • Randomly contracting the down-set and mixing horizontal and vertical price rules lets the proof evaluate buyer and seller contributions separately.An exponential-scale integral identity is used in the local-bound proof, and equal expected weights on the two rules complete the bound.Source: §3.4 · p. 15

4 Tight 𝑒-Approximation Upper Bound

The section constructs markets where GRO’s expected GFT approaches a 1/e fraction of first-best GFT, establishing tightness. The construction uses regular distributions, disjoint trading edges, and a single knapsack constraint.

4 Tight 𝑒-Approximation Upper Bound

  • The tightness instance has regular type distributions on [0, 1], pairwise disjoint trading edges, and one knapsack constraint.Positive scaling preserves allocations, regularity, and approximation ratios while placing every type in [0, 1].Source: §4 · p. 17, §4.2 · p. 21

4.2 A tight example with a knapsack constraint

  • The proof first builds a bounded regular bilateral instance with an asymptotically tight local inequality, then adds a deterministic knapsack alternative.The alternative places deterministic-edge GFT above the random edges’ expected maximum virtual surplus but below their expected maximum GFT.Source: §4 · p. 17, §4.2 · p. 19

4 Tight 𝑒-Approximation Upper Bound

  • GRO’s expected GFT approaches a 1/e fraction of first-best GFT, making the approximation tight.The construction turns tightness of the local profit inequality into tightness for actual GFT.Source: §4 · p. 17

4.1 A bilateral building block

  • The bilateral building block uses capped exponential buyer and mirrored seller distributions, with caps preserving bounded support and regularity.Away from the caps, buyer virtual value is one below value and seller virtual cost is one above cost.Source: §4.1 · p. 17
  • The local inequality’s e/2 coefficient is sharp for bounded regular bilateral distributions.This bilateral building block controls the one-sided profit benchmarks used in the construction.Source: §4 · p. 17, §4.1 · p. 19

4.2 A tight example with a knapsack constraint

  • One-sided profit alone does not determine actual GFT, because the strategic side may receive substantial information rents.The proof adds a deterministic alternative under a knapsack constraint to make both GRO components exhibit the asymptotic GFT gap.Source: §4.2 · p. 19

5 Conclusion

The paper characterizes GRO’s exact worst-case guarantee as 1/e for downward-closed matching markets. The conclusion identifies settings where this tight result does not determine the exact guarantee.

5 Conclusion

  • GRO obtains at least a 1/e fraction of first-best GFT, and this guarantee is tight for downward-closed matching markets.The tightness holds even with regular types on [0, 1], disjoint trading edges, and a single knapsack constraint.Source: §5 · p. 21
  • The same 1/e fraction applies to the random-offerer mechanism in bilateral trade.The conclusion gives this as a consequence of the matching-market result.Source: §5 · p. 21
  • The construction does not settle GRO’s exact guarantee for ordinary bipartite matching without extra feasibility constraints or the random-offerer’s exact bilateral guarantee.The analysis relies on down-set edge-selection regions and the stable-partner property of single-parameter matching markets.Source: §5 · p. 21

A Quantiles, endpoints, and atoms

The appendix fixes quantile conventions at atoms and endpoints and specifies how regularity is defined for distributions with atoms. It also records the threshold rules and payment identities used in the construction.

A Quantiles, endpoints, and atoms

  • Buyer values use a nonincreasing upper-quantile representation, while seller costs use a nondecreasing lower-quantile representation.Generalized inverses provide these versions after changing only countably many points.Source: A Quantiles, endpoints, and atoms · p. 24
  • A top-x buyer threshold allocates to the top x probability mass and charges the corresponding quantile value, yielding expected payment R(x).The rule is DSIC and IR; the bottom-y seller threshold symmetrically yields expected payment K(y).Source: A Quantiles, endpoints, and atoms · p. 24
  • For bounded distributions, endpoint quantiles at 1 are defined by finite left limits, and using the endpoint does not increase the relevant supremum.The seller endpoint identity follows from monotonicity of the lower-quantile function.Source: A Quantiles, endpoints, and atoms · p. 24
  • Regularity for buyers means concavity of the interpolated revenue curve, while seller regularity means convexity of the interpolated cost curve.Interpolation is across quantile intervals corresponding to atoms; degenerate distributions are regular because their curves are linear.Source: A Quantiles, endpoints, and atoms · p. 24

B Measurability of the posted-price construction

The appendix establishes measurability for the posted-price construction by showing that selection-section lengths are measurable and that measurable approximate thresholds exist. It also addresses atom boundaries in the first-best allocation.

B Measurability of the posted-price construction

  • For a fixed edge, the buyer- and seller-quantile selection-interval lengths are measurable functions of the other reports.The first-best allocation indicator is jointly measurable, and integrating it gives measurable section lengths.Source: B Measurability of the posted-price… · p. 25
  • For any positive tolerance, a measurable threshold below the section boundary can approximate the best restricted buyer objective within that tolerance.A symmetric statement holds for the seller objective.Source: B Measurability of the posted-price… · p. 25
  • Quantile ranks representing the same reported type either both select an edge in the first-best matching or neither does, so a selection interval cannot end inside an atom interval.These facts support the measurable posted-price construction, including threshold atoms.Source: B Measurability of the posted-price… · pp. 25–26

C One-sided optimality of GSOM and GBOM

This section recalls a one-sided virtual-surplus characterization and notes related implementation properties and ironing intervals.

C One-sided optimality of GSOM and GBOM

C.1 Seller-side auction

The seller-side argument uses buyer quantiles and ironing to show that GSOM is one-sided optimal.

C.1 Seller-side auction

  • Buyer values are represented by independent uniform upper-tail ranks, with the revenue curve's concave majorant defining the nonincreasing virtual-surplus derivative.The type-space function agrees almost surely with that derivative under the quantile representation.Source: §C.1 · p. 26
  • For fixed seller costs, BIC makes each buyer's interim allocation probability nonincreasing in upper-tail rank, enabling payment bounds from the payment identity and Myerson's ironing inequality.Source: §C.1 · p. 26
  • For irregular distributions, the payment bounds are tight when the lowest buyer type's utility is zero and allocations are constant on buyer ironing intervals.Summing the buyer payment bounds and subtracting realized seller costs yields a bound for feasible BIC, interim-IR seller-side auctions.Source: §C.1 · p. 26
  • The GSOM allocation is one-sided optimal, with normalized threshold payments making the seller-side payment bounds tight.The pointwise maximizing allocation is monotone in each buyer's rank and constant on buyer ironing intervals under fixed tie-breaking.Source: §C.1 · p. 26

C.2 Buyer-side procurement auction

The buyer-side procurement argument uses seller quantiles and convex ironing to establish that GBOM is one-sided optimal.

C.2 Buyer-side procurement auction

  • Seller costs are represented by independent uniform lower-tail ranks, with the cost curve's convex minorant defining a nondecreasing virtual-cost derivative.The type-space function agrees almost surely with that derivative under the quantile representation.Source: §C.2 · p. 27
  • For fixed buyer values, BIC makes each seller's interim allocation probability nonincreasing in cost and lower-tail rank, supporting bounds from the procurement payment identity and convex ironing.Source: §C.2 · p. 27
  • For irregular costs, equality holds when allocations are constant on seller ironing intervals and utility at the upper cost-support endpoint is normalized to zero.For an unattained or infinite endpoint, the normalization is interpreted as a limiting utility; this yields bounds for feasible BIC, interim-IR buyer-side procurement auctions.Source: §C.2 · p. 27
  • GBOM is one-sided optimal, with normalized procurement payments making the buyer-side inequalities tight.The pointwise maximizing allocation is monotone and constant on seller ironing intervals.Source: §C.2 · p. 27

Related papers

Loading 2609.37997v1…