Sharp Second-Best Welfare in Bilateral and Matching Markets

1 Introduction

• The second-best welfare problem differs from gains from trade because sellers’ endowment is part of the benchmark and relates to the trade sacrificed for budget balance.The model assumes independent nonnegative types and uses BIC, interim IR, and ex ante weak budget balance; transfers may be signed and occur without trade.Source: §1 · p. 3, §1.1 · p. 3

1.1 Main Results

• Both welfare ratios are sharp already in bilateral trade; the unrestricted guarantee covers downward-closed feasibility, while the MHR guarantee concerns ordinary matching markets.The results use BIC, interim IR, and weak budget balance, and the same guarantees hold under pointwise strong budget balance.Source: §1.1 · pp. 3–4, Table 1 · p. 4

1.2 Technical Overview

• For arbitrary priors, simultaneous score decomposition yields power-law layers whose seller means and dual values add exactly, while efficient gains are subadditive.The MHR reduction instead transforms buyer and seller scores together to preserve the dual value and seller mean while reducing buyers to shifted capped exponentials.Source: §1.2 · p. 5
• For MHR buyers, a typewise allocation certificate and an explicit seller use a shared boundary condition to establish both sides of the sharp bound.The allocation serves a continuous buyer tail, then randomizes within the buyer’s top atom; interval certificates verify the global numerical minima.Source: §1.2 · p. 5
• The bilateral affine inequalities extend to matching markets by charging seller endowment; unrestricted priors allow downward-closed feasibility, while the MHR extension uses rectangle packing for ordinary matching.The unrestricted charge counts a seller’s prior mean at most once, and the MHR argument conditions on upper-buyer/lower-seller rectangles whose upper tails preserve MHR.Source: §1 · p. 3, §1.2 · p. 5

1.3 Related Work

• Prior work establishes gains-from-trade guarantees and fixed-price welfare bounds, whereas this paper studies welfare over all BIC, interim-IR mechanisms with no expected deficit and signed transfers.The paper assumes known independent private-value distributions; correlated and interdependent values are outside its stated scope.Source: §1.3 · p. 6

2 Preliminaries

• The model uses independent nonnegative types on a bipartite compatibility graph, with feasible allocations drawn from a downward-closed family of matchings.Ordinary matching markets allow every matching of the graph; first-best welfare is the sellers’ endowment value plus gains from trade.Source: §2 · p. 7

2.2 Continuous Buyers and Budget Duality

• A budget-surplus multiplier turns welfare optimization into maximizing gains plus α times payment surplus, and compact separation establishes the corresponding dual formula.A universal lower guarantee must hold for every multiplier; the duality argument also covers bounded MHR buyers with finite sellers.Source: §2 · p. 7, §2.2 · p. 9

2.1 Envelope Payments

• BIC and interim IR reduce to monotone interim service probabilities and envelope payments, while budget feasibility requires expected buyer payments to cover seller receipts.With integrable signed transfers, ex ante WBB, pointwise WBB, and pointwise SBB permit the same feasible allocations and welfare values.Source: §2.1 · p. 8
• For independent Borel bilateral types, a common-transfer reconstruction preserves interim allocations and converts ex ante WBB into pointwise SBB.The replacement also weakly increases the buyer’s interim utility.Source: §2.1 · p. 8

3 Sharp Welfare for Unrestricted Priors

• The sharp unrestricted bilateral welfare ratio equals ρU, attained at a unique normalized parameter triple with the corresponding power-law priors and boundary-lottery mechanism.The certified enclosure is 0.8882516903 < ρU < 0.8882516904.Source: §3 · p. 10, §3.5 · p. 16

3.1 Budget-Dual Ironing

• Budget-dual ironing replaces raw buyer and seller coefficients with monotone ironed scores, yielding an exact positive-part expression for the fixed-multiplier dual value.The buyer score is nonincreasing and the seller score is nondecreasing.Source: §3.1 · pp. 10–11

3.2 Positive Reconstruction

• Positive reconstruction maps the ironed scores back to valid quantiles while preserving the dual value, lowering the seller mean, and increasing efficient gains.The reconstruction operator preserves bounds and monotonicity; independence permits the buyer and seller comparisons to be integrated.Source: §3.2 · p. 12

3.3 Common Power-Law Layers

• A common threshold decomposition splits both monotone scores into layers, each represented by power-law priors with seller atom p at zero and buyer atom r at one.Layer quantities add exactly for the seller mean and dual value, while efficient gains satisfy the corresponding subadditive comparison.Source: §3.3 · p. 13

3.4 Extremal Priors and the Boundary Lottery

• Each layer’s gains are bounded by pr/(1 −a), and when the stated feasibility condition holds, a boundary lottery attains that bound and is second-best optimal.It trades surely at (S, B) = (0, 1), randomizes with probability θ on the other supported endpoint profiles, and never trades at interior profiles.Source: §3.4 · p. 14

3.5 Global Evaluation and Attainment

• The scalar objective has a unique global minimizer, and the interval certificate verifies both the sharp ratio and feasibility of the boundary lottery there.The minimizing parameters are approximately (0.3231442122, 0.6544790312, 0.3251658297).Source: §3.5 · p. 16

4 Sharp Welfare for MHR Buyers

• For a bounded MHR buyer, seller reconstruction preserves Vα, lowers the seller mean, and does not reduce efficient gains.The reconstructed seller has a nondecreasing normalized score.Source: §4 · p. 16

4.1 MHR-Preserving Decomposition

• Common transformations of buyer and seller scores preserve the dual value and seller mean, reducing the buyer to shifted capped exponentials.The buyer-only power-law decomposition does not preserve MHR.Source: §4.1 · p. 16, §4 · p. 16

4.2 Typewise Welfare Certificates

• Serving the buyer’s top probability mass according to a nonincreasing service function gives a feasible Lagrangian lower bound against every seller prior.When seller support ends before the service function’s support, this expression need not be the maximal payment surplus.Source: §4.2 · p. 18

4.3 The Common Residual Equation

• For each capped-exponential buyer, the residual has a unique zero, and an explicit seller attains the infimum used in the sharp characterization.The residual is positive below its zero and negative above it.Source: §4.3 · pp. 18–19

4.4 The Positive Buyer Floor

• At ℓ = 0, the deficit derivative is negative when A > 0 and ρ < 1, so raising the buyer floor strictly improves an unshifted capped exponential.Thus the minimization cannot be restricted to unshifted capped exponentials.Source: §4.4 · p. 20
• The unique MHR minimum lies in (0.911389368124, 0.911389368127), and the corresponding buyer and seller attain the second-best welfare ratio.The minimizing parameters solve R(θ; ρ) = 0 and ∇θR(θ; ρ) = 0.Source: §4.4 · p. 21

4 Sharp Welfare for MHR Buyers

• The analysis retains the seller’s endowment term when extending bilateral affine inequalities to markets.The section identifies preserving that term as necessary for the market extension.Source: §4.4 · p. 21

5 Welfare Transfer via Bilateral Lifting

• The matching extension combines the bilateral inequalities with an endowment charge and, for MHR buyers, a separate distribution-preserving packing argument.The MHR construction does not establish the downward-closed feasibility extension proved for unrestricted priors.Source: §5 · p. 21, §5.3 · p. 24, §5.2 · p. 24

5.1 Unrestricted Priors and Endowment Charges

• For unrestricted priors, cap-monotone local rules compose edge by edge, with each seller’s endowment charged at most once across nonempty first-best caps.Conservative rounding extends the implication to bounded Borel priors using downward closure.Source: §5.1 · p. 22

5.2 MHR Buyers and Rectangle Packing

• For MHR buyers, upper-buyer/lower-seller rectangles support conditional bilateral rules that preserve MHR and keep the assembled welfare charge bounded by total endowment.The argument requires every matching of the compatibility graph to be feasible.Source: §5.2 · pp. 23–24

5.3 Sharp Welfare Ratios

• The bilateral affine bounds transfer to matching markets without changing their coefficients, and single-edge markets establish sharpness in both classes.The unrestricted guarantee applies to downward-closed feasibility; the MHR guarantee applies to ordinary matching markets.Source: §5.3 · p. 24

6 Conclusion

• Retaining sellers’ initial endowment in the affine budget comparison lets the reductions derive lower certificates and worst-case distributions together.The unrestricted constant transfers to downward-closed matching feasibility; the MHR constant transfers to ordinary matching markets.Source: §6 · p. 25
• The matching-market transfers use a full-prior endowment charge for unrestricted priors and MHR-preserving rectangle conditioning for ordinary matching markets.Both methods transfer their respective constants to the stated feasibility classes.Source: §6 · p. 25

A.1 Bounded Priors

• For unrestricted priors, rounding buyers down and sellers up preserves interim payments, BIC, interim IR, and budget feasibility while weakly increasing actual gains.Taking the grid mesh to zero proves the unrestricted extensions without assuming strong duality for arbitrary Borel priors.Source: §A.1 · p. 28
• For MHR buyers, rounding only seller costs upward preserves seller payments and buyer interim allocations and payments, so expected budget feasibility is preserved.Vanishing rounding errors establish the MHR extensions without leaving the MHR class or invoking duality for arbitrary Borel sellers.Source: §A.1 · p. 28

A.2 Unbounded Supports

• Clipping active types at K and extending the mechanism to original reports preserves incentives and expected budget while weakly increasing gains.Letting approximation error vanish and then K grow proves welfare lower bounds when 0 < WFB < ∞; the paper makes no attainment claim for arbitrary unbounded priors.Source: §A.2 · pp. 28–29

A.3 Atomless Buyers and Balanced Transfers

• Capped MHR buyers can be approximated by atomless MHR buyers while their normalized scores converge in L1.For each fixed hard seller with a monotone normalized score, efficient gains and the score expression for Vα converge, preserving strict upper bounds and tight infima.Source: §A.3 · p. 29
• A signed-transfer conversion preserves interim payments, allocations, BIC, and interim IR while reconstructing profilewise balanced transfers.The conversion supports pointwise strong budget balance, but does not assert ex post IR or payments only at trade.Source: §A.3 · p. 29

B.1 Certificate Structure

• The certificate confines candidate minima to a compact box and uses local convexity to prove sharpness and uniqueness.The proof combines boundary checks, a finite global cover, and local point bounds.Source: §B.1 · p. 29, §B.1.1 · p. 30

B.1.1 Verification Algorithm

• The verifier checks a finite subdivision using interval arithmetic, rejecting the certificate if any proposed containment, sign, or derivative test fails.Its termination depends on finite input rather than convergence of numerical optimization.Source: §B.1.1 · p. 30

B.1.2 Verified Bounds

• The accepted global subdivision contains 167,505 leaves, and its least signed margin in nonlocal tests exceeds 1.62 · 10^-8.The table summarizes the finite certificate; the accompanying programs implement the tests with mpmath interval arithmetic and an independent MPFR implementation.Source: Table 3 · p. 31, §B.1.2 · p. 31

B.2 Enclosure Bounds

• The global certificate uses positive-series integral bounds truncated at N = 40 with explicit remainders, while local Hessian bounds use 256 intervals.The point evaluation uses M = 700 terms; interval arithmetic encloses elementary operations and series remainders.Source: §B.1.2 · p. 31, §B.2 · p. 31

B.2.1 Boundary Exclusion

• For ρ = ρ, the exterior inequalities certify D > 0 outside the interior of K0 for all (a, p, r) ∈ (0, 1)3, and D is also positive on K0’s face r = 1.Source: §B.2.1 · p. 31

B.2.2 Finite Global Coverage

• A finite cover of K0 excludes nonlocal minima using positive value bounds or strictly signed partial derivatives on each leaf.With positivity on ∂K and the boundary of K0, the cover implies D > 0 on K0 outside K.Source: §B.2.2 · pp. 33–34

B.2.3 Integral Enclosures

• Incomplete beta values are enclosed with a positive binomial series and explicit remainder bounds; symmetry handles arguments above 1/2.The global verification truncates after N = 40 and includes every remainder as a nonnegative interval.Source: §B.2.3 · p. 34

B.2.4 Local Strong Convexity

• On K, the interval Hessian satisfies ∇2D(ρ, z) ⪰ 0.01I3 for ρ ∈ [0.8882516, 0.8882517].The verification checks 512 rational boxes covering K.Source: §B.2.4 · p. 35

B.2.5 Point Bounds and Uniqueness

• The certificate places the minimizer inside the stated box and verifies the local inequalities using interval bounds on the function and its gradient.The gradient bounds use coordinatewise endpoint bounds over the ratio interval.Source: §B.2.5 · p. 36
• Strict convexity and exterior positivity rule out any second solution of the minimizing equation in the certified box.A zero gradient identifies the unique minimum inside the box, while positivity outside excludes another global minimizer.Source: §B.2.5 · p. 36

B.3 Derivative Formulas

• The derivative appendix supplies formulas for layer integrals, including moving-support endpoints, and identifies them as inputs to the local verifier.The formulas include derivatives of the seller mean and first-best gains with respect to the parameters.Source: §B.3 · pp. 37–38

C Proof of Theorem 4.3

• The appendix reduces the global MHR welfare proof to a compact-domain certificate after bounding extreme budget multipliers.A fixed-multiplier gains bound supplies an endpoint estimate used to exclude multipliers approaching zero or infinity.Source: C Proof of Theorem 4.3 · p. 38, §C.1 · p. 38, In particular · p. 38

C.1 Multiplier Bounds

• The endpoint lower bound applies to bounded MHR-buyer instances for every multiplier parameter in the stated range.The proof uses a convexity estimate to bound the auxiliary expression and exclude extreme multipliers.Source: §C.1 · p. 38, In particular · p. 38

C.2 Residual Identities and Endpoint Variations

• At a residual zero, the matching seller's optimized dual value yields the exact welfare ratio, making a Newton update an explicit seller welfare certificate.The residual identity is derived for trial ratios using the score flow and seller endpoint.Source: §C.2 · p. 39
• The proof distinguishes residual normalizations away from their zeros and uses endpoint-direction tests to support global exclusions.The normalizations share the residual's zeros and signs, but their off-root derivative tests are not interchangeable.Source: §C.2 · pp. 39–40

C.3 Global Certification

• The finite-domain reduction limits verification to a compact set of buyer parameters and a bounded ratio interval after excluding extreme cases.The reduced domain includes boundary limits through a continuous extension.Source: §C.3 · pp. 41–42
• 0.9113893680 is a global lower bound, while the explicit seller gives an upper bound below 0.9113893683; the matched pair attains the minimum.The proof confines minimizers to a certified neighborhood and establishes uniqueness there.Source: §C.3 · pp. 42–43

C.4 Interval Verification

• The interval verification specifies outward enclosures and a replay procedure, with proposed search labels never accepted as proof of a sign.The elementary interval operations enlarge rounded results outward, and nonfinite final enclosures are rejected.Source: §C.4 · p. 43, §C.4.1 · p. 43

C.4.2 Exterior Comparison

• The exterior comparison verifies a complete binary tree of 47,273,387 nodes with no failures at the exact target ratio.Leaves are accepted only by the stated bounds or when wholly contained in the interior region.Source: §C.4.2 · p. 44

C.4.3 Head Flow and Integral Derivatives

• The head-flow and integral checks enclose the seller endpoint and its derivatives, using validated flow steps and integral remainder bounds.At the floor crossing, the verifier uses a first-order step with an enclosed second-order remainder.Source: §C.4.3 · pp. 45–46

C.4.4 Interior Coverage and Stationary Exclusions

• The interior replay covers 64,175 checked leaves with zero failures, accepting boxes only after a positive bound or stationary-point exclusion.The coverage includes boundaries, and negative values alone do not constitute acceptance.Source: §C.4.4 · p. 46

C.4.5 Local Convexity and Sign Bounds

• The checked Hessian has a scaled Gershgorin lower bound above 0.59908114, certifying strong convexity on the local region.Positive interval LDLT pivots provide an additional consistency check.Source: §C.4.5 · p. 46
• Positive lower bounds at two rational targets and negative upper bounds at nearby center evaluations bracket the minimizing ratio.The exact targets are 0.9113893680 and 0.911389368124; the center evaluations are at 0.9113893683 and 0.911389368127.Source: §C.4.5 · p. 47
• The local verifier's conservative sign checks complete the analytic acceptance rules for both constants.The final appendix identifies the certificate inputs and replay commands.Source: §C.4.5 · p. 47

• The preceding appendices give the acceptance rules, while this section describes the finite inputs and replay procedure.Source: D Certificate Data and Reproduction · p. 47
• The numerical proof uses the accompanying sharp-welfare-certificates repository.Source: D Certificate Data and Reproduction · p. 47
• The repository contains subdivision data, verifier sources, and recorded acceptance runs; the finite inputs and independently enclosing tests—not the logs—are the mathematical proof objects.The manuscript and bibliography compile without downloading or executing the repository.Source: D Certificate Data and Reproduction · p. 47

D.1 Obtaining the Certificate Data

• The repository commits the finite inputs directly, and verify.py compiles the verifiers, expands the exterior proof tree, and runs both certificates’ checks.Replay requires Python 3 with NumPy, a C++17 compiler, and MPFR/GMP; optional Python interval implementations additionally use mpmath.Source: §D.1 · p. 47

D.2 Unrestricted-Prior Certificate

• The unrestricted-prior checks verify subdivision coverage and its byte-for-byte binary export, then test nonlocal, exterior, local Hessian, point, boundary, and localization inequalities.Alternative Python interval implementations are also supplied.Source: §D.2 · p. 47

D.3 MHR Certificate

• The MHR certificate is computer-assisted: analytic reductions, acceptance inequalities, and remainder bounds are in the manuscript, while the repository supplies finite inputs and implementations.A local PASS LOCAL CHECKS ONLY result covers only the local component; the global claim also requires both covers. The worker count does not change acceptance tests.Source: §D.3 · p. 48

D.4 Reproducing Every Certificate at Once

• Running python3 verify.py --jobs 8 replays both certificates; FULL CERTIFICATE REPLAY PASSED: all marks success, whereas --check-only does not run interval proofs.Source: §D.4 · p. 48