PaperlayerView exact revision on arXiv

Source-linked AI summary

The Exact Approximation Ratio of the Optimal Fixed-Price Mechanism in Bilateral Trade

Tao Jiang, Minbo Gao, Shaowei Cai

arXiv:2609.27878v1cs.DS

TL;DR

Myerson and Satterthwaite’s impossibility theorem shows that full efficiency is incompatible with the standard incentive and budget requirements in general. Wronskian saturation reduces the distributional problem to a one-dimensional inverse-call control problem whose logarithmic formulation is strictly convex and has an interior arc followed by q=1. 0.7380243357… is the exact worst-case welfare ratio, characterized by a unique root r⋆∈(1, 3).

  • Problem

    Myerson and Satterthwaite’s impossibility theorem shows that full efficiency is incompatible with the standard incentive and budget requirements in general.

    Source: §1 · p. 3

  • Method

    Wronskian saturation reduces the distributional problem to a one-dimensional inverse-call control problem whose logarithmic formulation is strictly convex and has an interior arc followed by q=1.

    Source: §1.4 · p. 6, §5.2 · p. 12

  • Results

    0.7380243357… is the exact worst-case welfare ratio, characterized by a unique root r⋆∈(1, 3).

    Source: §1.1 · p. 3, §5.5 · p. 17

  • Takeaways & Limitations

    A bounded seller and buyer body with a vanishing buyer mass at an escaping value yields a family whose welfare ratios converge to the bound.

    Source: §1.4 · p. 6

    No admissible pair of finite-mean distributions attains the worst-case ratio.

    Source: §7.3 · p. 23

Abstract

from arXiv · show

Prior work placed the worst-case welfare ratio of the optimal fixed-price mechanism for bilateral trade in the interval [0.7292,0.73805]. We determine the ratio exactly as \[ α_{\mathrm{FP}}=0.7380243357\ldots, \] characterized by the unique root of an explicit one-dimensional equation. The proof first saturates a Wronskian constraint on the seller put and buyer call transforms. In inverse-call coordinates, the resulting extremal problem becomes a control problem whose logarithmic formulation is strictly convex. Its optimizer has one interior arc followed by the boundary \(q=1\), and the trajectory can be integrated explicitly. We then realize this optimizer by a bounded seller and buyer body together with a vanishing buyer mass at an escaping value, obtaining a matching limiting family. Every fixed instance admits an optimal price, but the worst-case distributional infimum is not attained. The proof applies to arbitrary Borel distributions with finite first moment, including atomic and unbounded distributions.

1 Introduction

The section studies fixed-price trade when efficiency is constrained by incentive and budget requirements, and gives an exact worst-case welfare ratio. It outlines a transform reduction, a convex control problem, and a limiting family that approaches the bound.

1 Introduction

  • Bilateral trade pits the seller’s value for retaining an item against the buyer’s value for receiving it; a fixed price is the canonical robust class under the stated incentive and budget requirements.The first-best allocation trades exactly when B≥S, while the Myerson–Satterthwaite impossibility result rules out full efficiency in general.Source: §1 · p. 3

1.1 Main theorem

  • 0.7380243357… is the exact worst-case fixed-price welfare ratio, characterized by a unique r⋆∈(1, 3); the infimum is approached but not attained.An explicit bounded seller distribution and a family of finite-mean buyer distributions converge to the ratio.Source: §1.1 · p. 3

1.2 Conceptual contributions

  • Wronskian saturation replaces the seller transform with a canonical extremal one, increasing first-best gains while decreasing the seller baseline mean and preserving the normalized fixed-price cap.The reduction is performed directly at the transform level.Source: §1.2 · p. 4
  • In inverse-call coordinates, logarithmic control makes the action strictly convex, and a crossing argument yields one interior arc followed by the boundary q=1.The paper uses this convexity to make the KKT conditions globally sufficient.Source: §1.2 · p. 4
  • A bounded seller and buyer body plus buyer mass ε at value 1/ε realize the optimizer in the limit; the vanishing mass still contributes one unit to the first moment.This construction continuously explains remote buyer support points observed in finite mathematical programs.Source: §1.2 · p. 4

1.3 Related work and positioning

  • Earlier guarantees narrowed the ratio to [0.7292, 0.73805]; unlike Cai and Wu’s distribution-level formulation, this paper derives the control problem through Wronskian saturation and inverse-call coordinates.The paper also notes that buyer-offering mechanisms with a reserve can guarantee 0.746 of first-best welfare [DS26].Source: §1.3 · pp. 4–5

1.4 Proof overview

  • The proof saturates the seller constraint, relaxes the buyer control to measurable 0<q≤1, solves the resulting one-dimensional action, and reconstructs a tight family.The relaxed control is itself nondecreasing, and the matching family approaches the universal bound.Source: §1.4 · p. 6

2 Welfare identities and transform geometry

The section decomposes welfare into the seller’s baseline and gains from trade, then uses seller-put and buyer-call transforms to study fixed-price gains. It also constructs a saturated seller transform that preserves the normalized fixed-price cap while strengthening the comparison used in the universal bound.

2 Welfare identities and transform geometry

  • Every admissible pair has first-best welfare m + I and optimal fixed-price welfare m + M, with 0 ≤ M ≤ I < ∞.Here m is the seller’s expected value, I is the first-best expected gain from trade, and M is the largest gain captured by a fixed price.Source: §2 · p. 7
  • The fixed-price gain function is upper semicontinuous, tends to zero as price tends to infinity, and therefore attains its maximum.This holds for every admissible pair, so each fixed instance has an optimal price.Source: §2 · p. 7
  • At differentiability points, the fixed-price gain is expressed through the seller put and buyer call transforms and their derivatives.The passages also specify right-continuous distribution conventions and treat endpoint atoms explicitly.Source: §2 · pp. 6–8

3 Wronskian saturation

  • The saturation reduction replaces the seller transform while increasing first-best gains, decreasing the seller baseline mean, and preserving the normalized fixed-price cap.The resulting slope-one extension is the put transform of a nonnegative seller value supported on a bounded interval.Source: §3 · p. 9

4 Reduction to a one-dimensional variational problem

After saturating the seller transform, the paper changes to inverse-call coordinates and represents the universal bound as a one-dimensional control problem. It relaxes the buyer-generated controls to measurable controls, while establishing that the optimizer itself remains realizable by a buyer distribution.

4 Reduction to a one-dimensional variational problem

  • Buyer-generated controls are nondecreasing in c, but the reduction enlarges the admissible class to all measurable controls with 0 < q ≤ 1.This is the only relaxation; the optimizing control is itself nondecreasing and is reconstructed as a genuine buyer distribution.Source: §4 · p. 10
  • The universal reduction normalizes the maximum fixed-price gain to one and bounds I − hm by 1 + V(h).The control class is defined by measurable q with 0 < q ≤ 1 and finite action.Source: §4 · p. 11
  • The universal inequality follows from the control value together with the saturated seller representation.The bound applies under the normalization M = 1.Source: §4 · p. 11

5 Global solution of the variational problem

The variational problem has an optimizer, and strict logarithmic convexity and KKT conditions establish global optimality. Its free-endpoint solution has a unique switch, satisfies a terminal condition, and can be reconstructed and integrated explicitly to obtain the exact variational value.

5.1 Existence

  • For every h > 0 and b > 1, the fixed-endpoint action has a minimizer, and the free-endpoint supremum is attained.Compactness and lower-semicontinuity arguments establish existence when endpoints vary as well as when they are fixed.Source: §5.1 · p. 12

5.2 Logarithmic convexity and global sufficiency

  • The action is strictly convex in the logarithmic control, so the fixed-endpoint minimizing control is unique almost everywhere.Feasible controls satisfying the KKT conditions are global fixed-endpoint minimizers.Source: §5.2 · pp. 12–13

5.3 Regularity and the one-switch structure

  • Every free-endpoint maximizer has one switch: q < 1 on the interior arc and q = 1 from the switch to the endpoint.The switching function crosses zero once, which determines this control structure.Source: §5.3 · p. 14

5.4 The free-endpoint equation; 5.5 Integration of the interior trajectory

  • The free-endpoint solution satisfies the terminal condition N(b) = b, and its interior trajectory is integrated using a uniquely determined parameter r(h).H− decreases continuously from infinity to zero, giving a unique r(h) for each h > 0; the trajectory and endpoint are then uniquely reconstructed.Source: §5.4 · p. 15, §5.5 · p. 17

5.6 Exact value of the control problem

  • For every h > 0, the exact variational value is given by Theorem 5.10, and both the free-endpoint maximizer and each fixed-endpoint minimizing control are unique.The theorem’s value applies to the full measurable-control problem.Source: §5.6 · pp. 18–19

6 The fixed point and the universal guarantee

The universal guarantee is determined by a unique fixed point where H− and H+ agree. Their monotonicity establishes uniqueness, and the resulting bound applies to every pair of independent, nonnegative finite-mean distributions.

6 The fixed point and the universal guarantee

  • There is a unique r⋆ in (1, 3) satisfying H−(r⋆) = H+(r⋆), because H− decreases from infinity to zero while H+ increases from zero to infinity.The crossing determines the parameter used in the universal fixed-price guarantee.Source: §6 · pp. 19–20
  • For every pair of independent, nonnegative finite-mean distributions, the fixed-price welfare guarantee follows from the fixed-point bound m + I ≤ (1 + h⋆)(m + M).The proof applies the welfare decomposition after normalizing by M and then undoing the scaling.Source: §6 · p. 20

7 A matching extremal family

The section reconstructs the unique extremal control as genuine seller and buyer distributions, then uses a limiting family to match the worst-case bound. The infimum is not attained by any admissible finite-mean pair.

7 A matching extremal family

  • The reconstructed control is the unique free-endpoint maximizer, continuous and nondecreasing from q⋆(1) = 0 to q⋆(s) = q⋆(b) = 1.It increases strictly on [1, s] and remains one through b.Source: §7 · p. 21

7.1 The bounded buyer component

  • The bounded buyer component is defined by a survival function on [0, L] with no endpoint atoms, and its call transform is recovered from the extremal trajectory.The survival function is continuous and nonincreasing, with Q0(0) = 1 and Q0(L) = 0.Source: §7.1 · p. 21

7.2 The bounded seller

  • The bounded seller distribution is supported on [0, L], with an atom of mass 1/b at zero and no atom at L.The construction verifies that the slope-one extension is convex and its right derivative is a CDF.Source: §7.2 · p. 22

7.3 The escaping buyer tail

  • The limiting buyer family completes the extremal construction, with each Bε nonnegative and of finite first moment.For L ≤ p ≤ 1/ε, the bounded buyer cannot trade and all sellers lie below p; the resulting calculation establishes the extremal side.Source: §7.3 · p. 23
  • The lower bound holds for every admissible pair, while an explicit bounded seller and finite-mean buyer family approach the same ratio; no admissible pair attains the infimum.The exact equality follows by matching the lower bound with the limiting family.Source: §7.3 · p. 24

8 Certified numerical value

The paper gives a certified decimal enclosure for the exact ratio, evaluating its analytic characterization with interval arithmetic. Numerical computation is not used to prove the exact characterization.

8 Certified numerical value

  • The ratio’s characterization in Eqs. (86) and (89) is analytic.The decimal enclosure evaluates that closed-form characterization.Source: §8 · p. 24
  • 0.73802433573449 < αFP < 0.73802433573450.This interval enclosure is obtained by evaluating the closed form with interval arithmetic.Source: §8 · p. 24
  • Numerical computation is not used in the proof of the exact characterization.A longer enclosure and the arctangent form of Θ appear in Appendix E.Source: §8 · p. 24

9 Conclusion

The paper determines the exact worst-case welfare ratio of the optimal fixed-price mechanism in bilateral trade. Its proof reduces arbitrary instances to a convex control problem and identifies a limiting family that approaches the bound without attaining it.

9 Conclusion

  • The paper determines the exact worst-case welfare ratio of the optimal fixed-price mechanism in bilateral trade.The conclusion summarizes the result as applying to the optimal fixed-price mechanism.Source: §9 · p. 24
  • Wronskian saturation reduces arbitrary instances to a logarithmically convex control problem with one interior arc and one boundary arc.The boundary arc is q = 1.Source: §9 · p. 24
  • Every fixed instance has an optimal price, but the worst-case distributional ratio is approached only through escape of first moment to infinity.The matching family separates instance-level price attainment from attainment of the distributional infimum.Source: §9 · p. 24

A Direct-method details

The appendix establishes existence for the control problems using a weak-star compact closure and an integral perspective representation. It handles the reciprocal singularity by extending the action and proving lower semicontinuity.

A Direct-method details

  • The direct-method proof addresses the admissible closure q = 0 despite the action’s reciprocal singularity.It supplies the compactness and lower-semicontinuity details needed for this setting.Source: A Direct-method details · p. 24
  • The integral perspective representation treats a/v as +∞ wherever a > 0 and v = 0.It expresses the integral as a supremum over bounded nonnegative measurable functions.Source: A Direct-method details · pp. 24–25
  • For every h > 0 and b > 1, the minimum of Ah,b over Qb is attained.The proof works in the weak-star compact closure of controls with 0 ≤ Y′ ≤ 1 almost everywhere.Source: A Direct-method details · p. 25
  • A minimizing sequence yields a limit in Yb, and the integral perspective representation establishes lower semicontinuity of the extended action.Finite action forces Y′ > 0 almost everywhere, so q = Y′ belongs to Qb.Source: A Direct-method details · p. 25
  • For every h > 0, the supremum defining V(h) is attained by some pair (b, q) with b > 1 and q ∈ Qb.The argument excludes endpoints approaching 1 or infinity before treating endpoints in a compact subinterval.Source: A Direct-method details · pp. 25–26
  • After reparameterization, lower semicontinuity and convergence of log bn make the objective upper semicontinuous along a maximizing sequence.The limit pair therefore attains V(h).Source: A Direct-method details · p. 26

B Threshold equivalence

The threshold argument proves the guarantee when V(h) ≤ h and shows it fails when V(h) > h. Its converse uses an optimizing control and a buyer tail mass to construct a limiting family.

B Threshold equivalence

  • For V(h) ≤ h, normalize instances with M > 0 to M = 1, then undo the scaling to obtain the bound; M = 0 has ratio one.Source: B Threshold equivalence · p. 26
  • The converse realizes the optimizing control with bounded buyer and seller components, then appends buyer mass ε at value 1/ε to obtain a limiting welfare ratio.The construction’s bounds give M_h,ε → 1 and I_h,ε → 1 + G_h.Source: B Threshold equivalence · p. 26
  • When V(h) > h, the limiting family has ratio below 1/(1 + h) for all sufficiently small ε, so the proposed bound fails.The comparison uses the family’s finite-ε members.Source: B Threshold equivalence · p. 26

C Put and call transform characterizations

The appendix characterizes seller and buyer distributions through put and call transforms, gives an explicit extremal-distribution construction, and distinguishes the exact root characterization from its numerical evaluation.

C Put and call transform characterizations

  • For a convex put transform A with A(0) = 0, its derivative F characterizes a seller CDF, and A is represented by integrating F.The characterization also requires the stated CDF and finite-integral conditions.Source: C Put and call transform… · pp. 26–27
  • A buyer call transform C is convex, nonincreasing, and vanishes at infinity; its negative derivative is the buyer survival function and C(p) = E[(B − p)+].The call transform also has an integrated-survival representation.Source: C Put and call transform… · p. 27

D Closed-form extremal distributions

E Certified numerical evaluation

  • The exact characterization defines r⋆ as the unique root of Eq. (86), with α_FP given by Eq. (89); interval arithmetic evaluates the analytic formulas.The interval bounds are numerical evaluation, not the theorem’s exact characterization.Source: E Certified numerical evaluation · p. 28
Loading 2609.27878v1…