PaperlayerView exact revision on arXiv

Source-linked AI summary

From Bilateral Trade to Matching Markets: Sharp Gains from Trade

Zhengyang Liu, Ying Qin, Zihe Wang

arXiv:2609.30702v1cs.GT

TL;DR

The paper asks whether distributional restrictions that improve bilateral trade guarantees continue to help when multiple trades compete. It transfers bilateral bounds to matching markets and derives sharp factors for MHR buyers and limited seller type counts, with the worst cases already approached bilaterally.

  • Problem

    The paper asks whether local restrictions on type distributions that improve bilateral efficiency still yield gains when trades compete in matching markets.

    Source: §1 · p. 3

  • Method

    A bilateral-to-matching reduction transfers bounds at each revenue multiplier, using cap-monotone local rules under downward-closed feasibility.

    Source: §1 · p. 3, §1.1 · pp. 3–4

  • Results

    The reduction preserves bilateral bounds without loss, and the MHR and finite-support applications determine sharp factors that are already tight in bilateral trade.

    Source: §1 · p. 3

  • Takeaways & Limitations

    For these distributional restrictions, competing trades do not worsen the worst-case factors beyond the bilateral setting.

    Source: §1 · p. 3

    The polynomial-size LP computes a uniform factor for given buyer support and seller caps, not a whole market’s second-best value.

    Source: §3.2 · p. 12

Abstract

from arXiv · show

We study gains from trade in matching markets with independent private values and costs, Bayesian incentive compatibility, interim individual rationality, and no expected budget deficit. A second-best guarantee for finite bilateral trade extends without loss to matching markets with independent Borel priors, arbitrary downward-closed feasibility, and finite expected first-best gains. For bounded buyers with monotone hazard rates and arbitrary bounded sellers, we determine the exact worst-case ratio of second-best to first-best gains, approximately $0.72490721$. For binary buyers and sellers with at most $m$ types, we determine the exact ratio for every $m$, including $8/9$ when $m=2$ and a limit of $4/5$ as $m$ grows. Both families of bounds are tight already in bilateral trade.

1 Introduction

The paper asks whether local distribution restrictions that improve bilateral-trade efficiency still help when trades compete in a matching market. It develops a reduction that transfers bilateral bounds and applies it to monotone-hazard buyers and limited seller type counts.

1 Introduction

  • The second-best benchmark maximizes expected gains subject to BIC, IIR, and one ex-ante weak-budget-balance constraint.Types are independent, and payments may be signed; the shared budget constraint is not imposed separately on each trade.Source: §1 · p. 3

1.1 Main Results

  • The reduction transfers bilateral efficiency bounds to matching markets without loss, including for independent Borel priors with finite first-best gains.It applies under downward-closed feasibility; both sharp application bounds are already tight in bilateral trade.Source: §1.1 · p. 4
  • For bounded buyers with monotone hazard rates and arbitrary bounded sellers, the exact second-best guarantee is approximately 0.72490721 and is sharp bilaterally.The application imposes MHR on buyers alone.Source: §1.1 · pp. 4–5
  • With binary buyers and at most m types per seller, the sharp factor is 8/9 for m = 2 and decreases to 4/5 as m grows.Each bound is tight in bilateral trade.Source: §1.1 · p. 5

1.2 Technical Overview

  • The technical obstacle is that applying separate bilateral guarantees at each seller-cost cap can break allocation monotonicity and alter higher types’ information rents.The construction recursively meets typewise bounds with cap-monotone rules, so summing them loses no factor.Source: §1.2 · p. 5

1.3 Related Work

  • The paper distinguishes its reduction from prior half-guarantee results and uses it to obtain sharper factors from distribution shape and support size.The MHR result is framed against earlier bilateral bounds, while the finite-support application determines exact factors beyond the reported numerical grid minimum.Source: §1.3 · p. 6, Table 1 · p. 6

2 Preliminaries

The preliminaries define the matching-market environment and express the second-best problem through implementable allocations and a shared budget constraint. A Lagrangian formulation then provides a fixed-multiplier allocation rule.

2 Preliminaries

  • A market has a bipartite compatibility graph, and feasible outcomes are matchings in a nonempty downward-closed family.Each buyer receives at most one item and values compatible items equally; each seller supplies one item.Source: §2 · p. 7
  • The second-best benchmark is the maximum expected gains from trade among mechanisms satisfying BIC, IIR, and ex-ante weak budget balance.The benchmark depends on the allocation; suitable payments implement it when the allocation is monotone in interim trade probabilities.Source: §2 · pp. 7–8
  • Budget feasibility is characterized by a linear inequality on allocations, and the second-best value is obtained by minimizing over a revenue-weight multiplier.At a common minimizing multiplier, some optimum is a mixture of at most two Lagrangian maximizers.Source: §2 · p. 8
  • For a fixed multiplier, the rule maximizes ironed buyer and seller scores over feasible matchings while preserving interim monotonicity.It is deterministic, trades only when buyer value exceeds seller cost, and can be evaluated using one maximum-weight matching oracle call for rational inputs.Source: §2 · p. 8

3 The Bilateral-to-Matching Reduction

The reduction separates the bilateral efficiency bound from the task of combining trades: cap-monotone local allocation rules let bilateral guarantees add across a first-best matching. Finite bilateral value bounds can construct such rules, and seller regularization extends the construction to arbitrary finite sellers.

3.1 Composing Local Allocation Rules

  • Under downward-closed feasibility, cap-monotone local rules satisfying typewise Lagrangian targets compose across first-best edges; surplus targets of β times each edge’s expected gains sum to β FB.The local rules must also be nondecreasing in buyer reports and nonincreasing in seller reports.Source: §3.1 · p. 10

3.2 Constructing the Local Rules

  • For finite types, bilateral bounds across every buyer prior and seller cap are equivalent to one typewise-bounded rule family consistent across caps.The construction meets targets by choosing the smallest seller mass that satisfies the current target and rents already required at lower buyer types.Source: §3.2 · pp. 11–12
  • For rational finite local inputs and targets, the cap-consistent family is constructible in polynomial time in the explicit input and output size.The largest uniform factor over buyer distributions and seller caps is attained and computable by a polynomial-size LP, but this LP does not compute a whole market’s second best.Source: §3.2 · pp. 11–12

3.3 Regularizing Sellers Before Choosing Caps

  • Regularizing each full seller prior before conditioning preserves its type masses and optimized Lagrangian value, while weakly increasing first-best gains.The replacement depends only on the full seller prior and α; restricted applications must allow support points to change.Source: §3.3 · p. 13

4 Sharp Bounds for MHR Buyers

This section establishes sharp MHR-buyer efficiency bounds at every budget multiplier and extends the results from bilateral trade to matching markets. It proves tightness using bilateral instances and shows the tight ratio can be approached by bounded, absolutely continuous buyers without an endpoint atom.

4 Sharp Bounds for MHR Buyers

  • The exact infimum ratio c_alpha holds for bounded bilateral trade and matching markets with MHR buyers and arbitrary sellers; the minimum is attained in the interior.The bound is unchanged for bounded absolutely continuous buyers and extends to common finite lower bounds when expected first-best gains are finite.Source: §4 · p. 14

4.1 An Exponential Comparison for Reflected MHR CDFs

  • Matching weighted exponential averages yields a derivative comparison for concave log F, with affine log F as the worst case.This comparison supplies the derivative inequality used to bound information rents; it is not a pointwise tangent bound.Source: §4.1 · p. 15, §4.2 · p. 17

4.2 Typewise Bilateral Rules and Bounds

  • The bilateral rule trades at the seller’s bottom atom or below a value-dependent cutoff, yielding a typewise bound for any independent buyer prior.Its allocation is monotone in both agents’ types, and the resulting payments make the conditional Lagrangian at least beta times first-best surplus, including for buyer priors with atoms or singular parts.Source: §4.2 · pp. 16–18

4.3 From Bilateral Rules to Matching Markets

  • Cap-monotone bilateral rules compose across first-best edges to give the matching-market bound and budget-feasible gains approaching the guarantee.The extension also covers finite expected first-best gains with unbounded upper supports; the budget conversion preserves BIC and IIR and gives profilewise strong budget balance.Source: §4.3 · pp. 18–19

4.4 Tight Bilateral Instances

  • Bilateral instances establish tightness at every fixed multiplier, and a single-edge market is an allowed matching market.The construction uses a truncated exponential reflected seller distribution and a buyer prior whose Lagrangian score makes the comparison step tight.Source: §4.4 · pp. 19–20
  • Choosing z = z_t and k = z_t/(1−t)−1 makes the fixed-multiplier lower bound tight in bounded bilateral instances.The balance equation gives the ratio as 1/M_t(z_t) = c_α; at α = 0, V_0 = FB.Source: §4.4 · p. 20
  • The minimum of c_α is attained, and a minimizing multiplier makes the second-best upper bound match the lower bound, proving both equalities in Theorem 4.1.A bilateral instance is itself a matching market.Source: §4.4 · p. 20
  • Replacing the endpoint atom with a short uniform tail preserves MHR and changes the ratio arbitrarily little, yielding atom-free tight instances.For fixed H and δ, the replacement buyer is bounded and absolutely continuous; letting the tail length ϵ decrease to zero preserves the ratio of any fixed positive-first-best instance.Source: §4.4 · p. 21

5 Sharp Bounds for Binary Buyers

With binary buyers and sellers limited to m types, the paper derives sharp second-best guarantees for matching markets from bilateral bounds. The worst-case guarantee is already approached in bilateral trade, and decreases to 4/5 as the seller support bound grows.

5.2 Tight Instances and the Resulting Constants

  • The bilateral upper bounds are approached by finite rational instances with values in [0, 1], and the same statements hold after exchanging buyers and sellers.The construction matches the lower bound as its parameters tend to zero.Source: §5 · p. 21, §5.2 · p. 24

5.1 The Bilateral Lower Bound and Its Matching Extension

  • The proof bounds seller cutoff values against efficient surplus, then controls the information-rent term using the binary buyer's incentive constraint.With two buyer types, only the high type can gain by reporting a lower value, so one information-rent term suffices.Source: §5.1 · p. 22
  • A buyer with at most two types and an independent seller with at most m types satisfies Vα ≥ Dm(α/(1 + α))^-1 FB for every α ≥ 0.The matching-market guarantee follows by applying the finite-support reduction to this bilateral bound.Source: §5.1 · pp. 22–23

5.2 Tight Instances and the Resulting Constants

  • Geometrically spaced cumulative seller probabilities make only one buyer–seller type pair carry positive Lagrangian weight in the tight bilateral family.The construction approaches equality in both the seller recurrence and the buyer information-rent bound.Source: §5.2 · pp. 23–24
  • 8/9 is the exact worst-case ratio with two types on each side; as the seller-type bound grows without limit, the ratio decreases to 4/5.The worst-case ratio decreases strictly with m.Source: §5.2 · pp. 24–25
  • For the m = 2 finite example with FB = 37/15625 and SB = 33/15625, the exact ratio is 33/37, while the worst-case 8/9 is approached as parameters tend to zero.The example agrees with the reported grid minimum of 0.89189.Source: §5.2 · p. 25

6 Conclusion

The conclusion gathers the paper’s sharp bounds and extensions, and identifies further questions about bilateral inequalities and matching-market mechanisms. The appendix material explains how payment identities reduce budget feasibility to a single constraint and how budget duality yields an implementable optimum.

6 Conclusion

  • The binary-support and MHR applications use the same composition step but require different bilateral bounds; the reduction also extends to independent Borel priors under the stated conditions.The Borel extension assumes finite expected first-best gains and mechanisms with integrable transfers and truthful utilities.Source: §6 · p. 25
  • The binary-support bounds also apply when each compatible edge has a binary endpoint, even if binary agents are not all on the same side.The sharp constants remain those of the corresponding bilateral classes.Source: §6 · p. 25
  • For specified offering mechanisms, the uniform mixture of generalized seller- and buyer-offering rules satisfies 2Goffer ≥ V1, but the paper makes no sharpness claim for these factors.The reduction alone does not preserve a supplied bilateral mechanism.Source: §6 · pp. 25–26
  • The paper leaves open sharp factors when both sides have more than two types, continuous cap-monotone constructions, and comparisons for other matching-market mechanisms.The stated directions include seeking mechanism inequalities of the form λG ≥ Vα.Source: §6 · p. 26

A.1 Finite Payment Identities and Budget Duality

  • Payment identities reduce ex-ante weak budget balance to the single linear constraint Λ(x) ≥ 0 for an allocation x.For finite types, budget duality implements a second-best optimum by mixing at most two Lagrangian maximizers.Source: §A.1 · p. 29

A.2 Fixed-Multiplier Optimization

For a fixed budget multiplier, the appendix shows that weighted ironing and a canonical matching rule optimize the Lagrangian. The rule is implementable because its allocations are monotone in each agent’s report.

A.2 Fixed-Multiplier Optimization

  • Weighted ironing pools adjacent blocks by their probability-weighted mean, and each resulting block coefficient equals that mean.The buyer and seller block bounds help ensure selected edges have positive actual surplus.Source: §A.2 · pp. 30–31
  • For monotone allocations, pooling adjacent buyer coefficients by ironing weakly increases the objective.The increase at one merge is proportional to the coefficient gap times the increase in interim service probability.Source: §A.2 · pp. 30–31
  • The canonical rule is implementable because buyer service is nondecreasing in value and seller service is nonincreasing in cost.As the report-dependent score changes, the chosen outcome switches at most once between serving and not serving an agent.Source: §A.2 · p. 31
  • The canonical matching rule attains the upper bound on the ironed objective, establishing optimality for the fixed-multiplier problem.The oracle rule attains the relevant inequality profilewise.Source: §A.2 · p. 31

A.3 Seller Regularization

Seller regularization replaces seller costs with reconstructed costs that make the combined scores weakly regular while preserving the Lagrangian optimum and weakly increasing first-best gains. The appendix also extends finite-prior guarantees to independent Borel priors under stated integrability and gain conditions.

A.3 Seller Regularization

  • For α > 0, reconstructed seller costs yield strictly increasing costs and combined scores equal to the ironed scores; at α = 0, no transformation is needed.The replacement preserves the Lagrangian optimum and weakly increases first-best gains.Source: §A.3 · pp. 32, 34
  • The regularization keeps seller probability masses but changes support points, preserving the indexed feasibility and interim-monotonicity polytope.Only seller coefficients in the Lagrangian change.Source: §A.3 · p. 32
  • Replacing a seller with its ironed seller distribution weakly increases first-best gains under every downward-closed family of matchings.The argument applies conditionally on the other agents’ types, then replaces sellers one at a time while preserving independence.Source: §A.3 · p. 33

B Extensions to General Priors

  • For independent Borel priors with finite expected first-best gains, one-sided rounding and interval projection transfer uniform finite-prior second-best guarantees.The separate MHR extension uses clipping under its stated lower-support condition.Source: B Extensions to General Priors · p. 34

B.1 General Borel Priors and the Half Guarantee

The section extends finite-market efficiency guarantees to general independent Borel priors by projection, rounding, and envelope-payment extensions. In particular, the finite half guarantee carries to arbitrary downward-closed matching feasibility when first-best gains have finite expectation, and remains tight in bilateral trade.

B.1 General Borel Priors and the Half Guarantee

  • Rounding buyers down and sellers up extends a finite allocation to full report domains while preserving generalized expected revenue and weakly increasing actual gains from trade.The extension uses interim-monotone allocations and normalized envelope payments; revenue preservation holds for either sign of the discrete revenue functional.Source: §B.1 · pp. 34–35
  • Finite-prior second best is attained by an interim-monotone allocation that trades only on positive-surplus edges and has nonnegative normalized expected revenue.Restricting the allocation to positive-surplus edges leaves every Lagrangian value unchanged, so finite LP duality preserves the budget-feasible optimum.Source: §B.1 · pp. 35–36
  • Projecting reports to a bounded interval extends a positive-surplus mechanism to the original market while preserving payments and expected revenue and weakly increasing gains from trade.With finite expected first-best gains, the extended transfers and truthful utilities are integrable.Source: §B.1 · pp. 36–37
  • For Borel priors, projected first-best gains converge to first best, enabling finite-market guarantees to pass to the unbounded-prior limit.Downward-closedness permits deletion of negative edges; monotone convergence then gives the benchmark limit.Source: §B.1 · p. 37
  • 1/2 of first-best gains is guaranteed for independent Borel priors with finite expected first-best gains and downward-closed matching feasibility, and the factor is tight.The extension proceeds from finite-prior guarantees; finite bilateral instances establish tightness.Source: §B.1 · p. 37

B.2 Unbounded MHR Priors via Clipping

Clipping extends bounded MHR guarantees to unbounded types under a common finite lower bound and finite expected first-best gains. The refinements section then develops stronger local efficiency targets that can vary with seller caps.

B.2 Unbounded MHR Priors via Clipping

  • Clipping each type at K extends a bounded-market mechanism to original type domains while preserving BIC, IIR, expected budget, and payment distribution, with weakly larger gains from trade.Positive clipped surplus ensures sellers above K are never served.Source: §B.2 · p. 38
  • Finite expected first-best gains ensure clipped mechanisms have integrable payments and utilities, while clipped first-best gains converge to the original benchmark for types with a common finite lower bound.The convergence follows from downward-closedness and monotone convergence.Source: §B.2 · pp. 38–39

C Refinements of the Efficiency Bounds

  • The refinements characterize uniform local factors and cap-dependent targets, then strengthen binary-buyer guarantees using the probability of the lowest seller cost.These refinements follow from the main reduction rather than serving as assumptions for either sharp bound.Source: C Refinements of the Efficiency Bounds · p. 39

C.1 The Best Uniform Local Factor

This section identifies the largest factor that can be guaranteed uniformly across seller caps for a fixed local instance. The factor is attained and can be computed by a polynomial-size linear program on rational inputs.

C.1 The Best Uniform Local Factor

  • The best uniform factor is the largest coefficient for which a cap-monotone family meets the local targets across seller caps.The construction uses the buyer support, a weakly regular seller, and unnormalized masses.Source: §C.1 · p. 39
  • On rational inputs, the largest coefficient is attained and is the value of a polynomial-size linear program.The program has O(nm^2) allocation variables.Source: §C.1 · p. 39

C.2 Bounds That Depend on Seller Caps

This section replaces a single worst-case local factor with targets that can vary across seller caps, then sums local targets over first-best edges. The resulting bounds preserve cap-dependent and edge-dependent differences, with stated limits on their scope.

C.2 Bounds That Depend on Seller Caps

  • Cap-dependent targets are the componentwise largest targets that increase with the cap while remaining below each cap's local factor times its buyer-type benchmark.A uniform factor takes the worst value over caps; the increasing target table preserves stronger bounds available at some caps.Source: §C.2 · pp. 39–40
  • The cap-dependent maximality claim does not establish optimality among all matching mechanisms or all attainable target tables.The construction ensures cumulative targets increase with the cap, as required by the composition theorem.Source: §C.2 · p. 40
  • Summing local targets over first-best edges yields a market-level benchmark that can retain differences across edges and seller caps.Seller masses are included in the local targets, so the formula applies no additional seller-probability factor.Source: §C.2 · pp. 40–41
  • The fixed-multiplier allocation need not have nonnegative revenue; regular sellers at every multiplier permit a budget-dual bound, while irregular sellers require full-distribution ironing.For the irregular-seller bound, the benchmark is evaluated in the transformed market; no efficient global minimization is claimed.Source: §C.2 · p. 41

C.3 Binary Buyers and the Lowest-Cost Probability

With binary buyers and a lowest-cost seller atom of probability at least p, the paper gives exact second-best guarantees even without a bound on seller support size. The guarantee is strictly above 4/5 for p > 0, with tight examples already in bilateral trade.

C.3 Binary Buyers and the Lowest-Cost Probability

  • The lowest-cost probability restriction improves the guarantee even when seller support size is unbounded, and no regularity hypothesis is required.The finite tight examples approach the uniform guarantee as the number of seller types grows.Source: §C.3 · pp. 41–43
  • γ(p) > 4/5 for every p > 0, tends to 4/5 as p ↓ 0, and tends to 1 as p ↑ 1.Both infima are approached bilaterally with rational data satisfying the probability restriction.Source: §C.3 · pp. 41, 43
  • For at most m seller types, the exact worst-case second-best coefficient is 1 / max_{0≤q≤1} Dm,p(q), and the same infimum holds bilaterally.The endpoint values are defined by continuity.Source: §C.3 · p. 42
  • The bound uses a stronger cutoff recurrence that retains cumulative probabilities and the lower bound on the seller’s lowest-cost atom.The probability restriction survives seller transformations and conditioning in the reduction, so the bilateral bound extends with the same coefficient.Source: §C.3 · p. 42

D Public Values and Offering Mechanisms

  • The next section extends the reduction to match-specific public values and gives a separate comparison for offering mechanisms.Public values specific to a match can be incorporated in local problems.Source: D Public Values and Offering Mechanisms · p. 43

D.1 Public Match-Specific Values

The reduction accommodates public additive values that vary by match when only scalar values are private. With a binary endpoint on every singleton-feasible edge, the second-best guarantee is at least 4/5 even without a uniform bound on the other endpoint’s types.

D.1 Public Match-Specific Values

  • Public offsets preserve the reduction’s structural properties, and full seller replacement preserves Vα while weakly increasing FB.The scalar private value enters as vi + aij, with surplus vi − cj + aij.Source: §D.1 · pp. 43–44
  • Each singleton-feasible edge must have one endpoint with at most two types, while the other has at most m types.The priors are independent and finite.Source: §D.1 · p. 44
  • With no finite uniform bound on the other endpoint, SB ≥ 4/5 FB; the coefficient is tight already with zero public offsets and one edge.The theorem allows arbitrary public additive values and downward-closed matching feasibility.Source: §D.1 · p. 44
  • The binary-endpoint argument preserves support bounds, local premises, and the rent correction before edge-by-edge composition and duality establish the result.The argument also permits swapping and reflecting the two sides when the binary endpoint is the seller.Source: §D.1 · p. 44

D.2 Generalized Offering Mechanisms

The paper compares two generalized offering mechanisms with Lagrangian bounds to obtain gains-from-trade guarantees for those rules. The resulting guarantees include FB/2 for binary types on both sides and 2FB/5 for binary buyers with arbitrary finite seller supports.

D.2 Generalized Offering Mechanisms

  • The reduction preserves a value bound rather than a chosen bilateral mechanism; the additional comparison is what yields guarantees for these specified rules.The comparison applies at α = 1.Source: §D.2 · pp. 44–45
  • GSOM maximizes the sum of buyer ironed virtual values minus seller costs, while GBOM maximizes buyer values minus seller ironed virtual costs.Goffer is expected GFT when choosing between the two rules with equal probability, independently of reports.Source: §D.2 · p. 44
  • Both rules are DSIC, ex-post IR, and ex-ante WBB, and their comparison bounds Goffer using the optimized Lagrangian objective.Any factor β satisfying the reduction premise at α = 1 implies Goffer ≥ (β/2) FB.Source: §D.2 · pp. 44–45
  • For independent finite priors and downward-closed feasibility, Goffer ≥ FB/π.This unrestricted guarantee uses the fixed-multiplier bound at α = 1 and the comparison with offering mechanisms.Source: §D.2 · p. 45
  • Binary types on both sides give Goffer ≥ FB/2, while binary buyers with arbitrary finite seller supports give Goffer ≥ 2FB/5.The statements also hold with the two sides exchanged; the paper makes no tightness claim for these mechanism guarantees.Source: §D.2 · p. 45

Related papers

Loading 2609.30702v1…