PaperlayerView exact revision on arXiv

Source-linked AI summary

Approximately Efficient Multidimensional Bilateral Trade

Aviad Rubinstein, Xizhi Tan, Zixin Zhou

arXiv:2609.02872v1cs.GT

TL;DR

The paper targets the gap in constant-factor truthful mechanisms for multidimensional bilateral trade. It develops simple mechanisms for XOS buyers and an additive seller under independent items, extending from one buyer to n buyers, and obtains constant fractions of first-best GFT while satisfying BIC, IIR, and ex-ante WBB.

  • Problem

    Existing constant-factor GFT mechanisms largely concern single-dimensional agents, leaving multidimensional bilateral trade insufficiently addressed.

  • Method

    The paper uses decompositions, dimensionality reduction, posted-price mechanisms, and delegation to construct simple mechanisms for XOS buyers and an additive seller.

  • Results

    Constant fractions of first-best expected GFT are achieved in both one-buyer and n-buyer settings by mechanisms satisfying BIC, IIR, and ex-ante WBB.

  • Takeaways & Limitations

    Multidimensional bilateral trade admits simple truthful, individually rational, and ex-ante budget-balanced mechanisms with constant-factor first-best GFT under independent items.

  • Takeaways & Limitations

    The results assume independent items; in the multi-buyer setting, unrestricted buyers’ profit maximization with VCG is not always ex-ante WBB.

Abstract

from arXiv · show

A central challenge in mechanism design is to develop truthful trade mechanisms that maximize the expected gains-from-trade (GFT) in two-sided markets. Because achieving the full GFT is generally impossible, the literature has focused on constant-factor approximations---a notoriously difficult problem even in simple settings. It was only recently that a breakthrough result by [DMSW22] achieved a constant-factor approximation for single-item bilateral trade. The same guarantee was later extended to single-dimensional matching markets with general downward-closed constraints [BRTW26]. Most existing results, however, are limited to single-dimensional agents. A notable multi-dimensional exception is [CGMZ21]. They considered a market with one constrained-additive buyer and $n$ single-dimensional sellers and provided a mechanism that achieves a $\log^2(n)$ approximation to the second-best GFT, i.e., the maximum expected GFT theoretically achievable by any mechanism satisfying Bayesian Incentive Compatibility (BIC), Interim Individual Rationality (IIR), and ex-ante Weak Budget Balance (WBB). In this paper, we study multi-dimensional bilateral trade problem where both sides of the market are multi-dimensional. We start with one buyer with XOS valuation and one seller with an additive cost function. We then generalize to a market with $n$ XOS buyers and one additive seller. Assuming independent items' values and costs, in both settings we propose simple mechanisms that are BIC, IIR, and ex-ante WBB, while achieving a constant fraction of the optimal (first-best) expected GFT.

1 Introduction

The paper addresses multidimensional bilateral trade with simple truthful mechanisms under independent item values and costs. It obtains constant-factor first-best GFT guarantees for one XOS buyer with an additive seller and for multiple XOS buyers with one additive seller.

  • Motivation: Multidimensional bilateral trade combines difficult multidimensional mechanism design with bilateral trade, where exact efficient mechanisms are impossible under incentive and budget constraints.The paper motivates approximation as the appropriate approach to these challenges.
  • Model: XOS valuations are the paper’s combinatorial-valuation focus, positioned between submodular and subadditive valuations in generality.The paper studies XOS buyers rather than arbitrary combinatorial valuations.
  • Single buyer: Under independent item values and costs, an adapted random offerer mechanism is BIC, IIR, and ex-ante WBB for one XOS buyer and one additive seller.The mechanism achieves a constant-factor approximation of GFT.
  • Single buyer: 1/44 of first-best expected GFT is guaranteed by equal-probability randomization between seller-optimal and buyer-optimal mechanisms.This is the informal theorem’s quantitative guarantee for the single-buyer setting.
  • Contribution: The paper presents its single-buyer result as the first constant-factor approximation to first-best GFT in multidimensional bilateral trade.This novelty claim is explicitly qualified by “to the best of our knowledge.”
  • Multiple buyers: The multi-buyer extension uses item pricing with probability 16/43 and otherwise permits an arbitrary optimal buyers-facing mechanism, preserving budget balance and constant-factor first-best GFT.The setting has n XOS buyers, one additive seller, and independent items.

2 Preliminaries

The preliminaries define the multidimensional buyer and additive-seller environment, feasibility and GFT notions, incentive and rationality requirements, and a unit-demand reduction to single-dimensional copies markets.

  • Environment: The seller has additive costs across m heterogeneous items, while buyer types are independently distributed across buyers and items and are independent of seller costs.For each buyer, correlations among clause values for a fixed buyer-item pair may remain arbitrary.
  • Valuations: XOS over independent items requires no externalities, monotonicity, and a finite maximum-of-sums representation over item-level functions.The valuation is represented as vi(ti,S) = max_k ∑j∈S v^(k)_ij.
  • Valuation examples: Additive, unit-demand, and constrained-additive valuations are included as special cases of the valuation class considered.The constrained-additive case uses a downward-closed set system.
  • Allocations and GFT: A feasible allocation assigns disjoint buyer bundles, leaves unallocated items with the seller, and measures GFT as value minus seller cost on transferred items.Randomized allocations use transfer probabilities, while first-best maximizes GFT over feasible allocations.
  • Mechanisms: The mechanism framework uses reported buyer types and seller costs, randomized feasible allocations, buyer payments, and seller payments.Utilities are defined from expected allocated value or seller payment minus the relevant cost or buyer payment.
  • Mechanism requirements: BIC, IIR, and ex-ante WBB impose truthful-reporting, participation, and expected-budget requirements, while second-best GFT optimizes over mechanisms satisfying all three.The text also distinguishes DSIC, ex-post IR, and ex-post SBB.
  • Unit-demand reduction: Unit-demand buyers value a bundle by its highest item value, and a downward-closed feasibility constraint restricts feasible trades.Singleton values are independently drawn across items under the item-independence assumption.
  • Copies instance: The copies instance replaces each buyer-item pair with a single-dimensional pseudo-buyer interested only in that item, with feasible allocations represented by matchings.Its GFT sums value minus cost over matched buyer-item pairs.

3 Technical Overview

The paper obtains a constant-factor approximation to first-best GFT through a core–tail decomposition and reductions to simpler profit benchmarks. Its mechanisms combine seller-side entry fees, posted prices, and buyer-side reductions while addressing the failure of standard VCG-based implementation with multiple buyers.

  • Overview: The main result achieves a constant-factor approximation to first-best GFT for multidimensional XOS buyers and an additive seller.The proof uses decompositions and mechanism-design reductions.
  • Core–tail decomposition: The proof decomposes realized GFT pointwise into core and tail components around a unit-demand benchmark.The threshold is chosen from the optimal one-trade or unit-demand matching benchmark.
  • Core approximation: Core truncation gives bounded differences and concentrates buyers’ utilities, enabling entry fees to extract a constant fraction of core GFT.The threshold balances core concentration against tail coverage.
  • Tail approximation: Tail GFT is bounded by the unit-demand benchmark and reduced to single-dimensional copies instances whose profit benchmarks cover the tail up to a constant factor.The reduction uses independent singleton values and existing single-dimensional matching results.
  • Mechanism implementation: For a single mechanism-running agent, explicit posted-price mechanisms are truthful, individually rational, and strictly budget-balanced while approximating the target benchmarks.These mechanisms can be used as advice auctions for delegated pricing power.
  • Multiple-buyer difficulty: With multiple buyers, maximizing unrestricted total buyer profit followed by VCG payments can violate ex-ante WBB because buyer profit is superadditive.The resulting positive externality makes VCG payments exceed total profit.

4 The Multi-Dimensional Bilateral Trade

The bilateral-trade warm-up studies one XOS buyer and one additive seller with independent item values and costs. It combines a core–tail decomposition with simple delegated mechanisms, obtaining 1/44 of first-best GFT for the optimal randomized protocol and 1/88 for the explicit protocol.

  • Setting: The setting has one buyer with an XOS valuation and one additive seller over independent items.Values may be correlated across XOS clauses, while different items and seller costs are independent.
  • Main guarantee: Theorem 4.1 gives a 1/44 fraction of first-best GFT while satisfying BIC, IIR, and ex-ante WBB.The mechanism randomizes equally between the seller-optimal and buyer-optimal mechanisms.
  • Explicit protocol: The explicit randomized protocol achieves a 1/88 fraction of first-best expected GFT.It delegates pricing to the seller or buyer with equal probability and uses the corresponding simple mechanisms.
  • Core–tail decomposition: The proof splits first-best GFT into core and tail components using a threshold defined by the optimal one-item benchmark.The decomposition upper-bounds GFT by the sum of the two components.
  • Core mechanism: A cost-price two-part tariff transfers GFT into buyer utility and uses an entry fee to extract a constant fraction of concentrated core GFT.When the buyer enters, seller profit equals the entry fee.
  • Tail mechanism: The tail is bounded through buyer- and seller-side one-item posted-price menus based on single-dimensional copies-instance profit benchmarks.Their average profit bounds the tail GFT.

5 Multiple XOS Buyers

The paper extends the approach to n XOS buyers and one additive seller using a unit-demand matching benchmark, ASPE for the core, and a new buyer-side truthful mechanism for the tail. The resulting mechanism satisfies BIC, interim IR, and ex-ante WBB while achieving a constant-factor approximation to first-best GFT.

  • 5 Multiple XOS Buyers: The general setting has n multidimensional XOS buyers, one additive seller, and independent item values and costs.The paper achieves a constant-factor first-best GFT approximation in this setting.
  • Final guarantee: The final mechanism is BIC, interim IR, and ex-ante WBB, and achieves a constant-factor approximation to first-best GFT.It randomizes pricing delegation between the seller and a buyer-side mechanism.
  • Benchmark and decomposition: The proof replaces the one-trade benchmark with a unit-demand matching benchmark and extends the core–tail decomposition.The matching feasibility constraint allows each item to be allocated to at most one buyer.
  • Mechanisms: The ASPE mechanism approximates core GFT, while copies-instance reductions and a new buyer-side truthful mechanism approximate tail GFT.The proof combines these components with the extended decomposition.
  • Dimensionality reduction: Under the unit-demand restriction, each XOS buyer reduces to independent singleton item values in a standard unit-demand market.The relevant value is the singleton value for each buyer–item pair.
  • Core–tail construction: The global threshold is set relative to the matching benchmark, and truncated clause-wise surpluses define core and tail objectives.The expected core contribution is denoted by µ.

6 Approximating the Core via an ASPE Mechanism

The section adapts ASPE to extract the core benchmark in a multi-buyer market. It combines supporting-price markups, inventory-dependent entry fees, and truncation to obtain truthful mechanisms whose losses are controlled by a unit-demand matching benchmark.

  • The fixed-cost core can be represented as welfare in a one-sided XOS instance with capped net gains from trade.This representation enables the paper to apply the ASPE framework after fixing the seller’s cost vector.
  • The mechanism derives anonymous markups Q_j from supporting prices and offers each item at cost plus markup, c_j + Q_j.The seller earns Q_j when item j sells.
  • Inventory-dependent entry fees δ_i(S), calibrated to median residual surplus, extract surplus that remains after posted prices.The remaining-item set S matters because buyers arrive sequentially and their utilities depend on which items remain.
  • ASPE(c) is buyer-DSIC and buyer ex-post IR, and its expected profit captures a constant fraction of μ(c) up to loss controlled by fixed-cost unit-demand matching GFT.The seller’s conditional optimal profit is therefore bounded by the same guarantee, and averaging over costs yields the seller-side core guarantee.
  • Final truncation concentrates residual surplus around its median, while pointwise attainability makes the auxiliary entry fees feasible under true valuations.This supports acceptance of the actual cost-plus-markup menu with probability at least one half.

7 Approximating the Tail via the Unit-Demand benchmark

The section reduces the tail of multidimensional gains from trade to a unit-demand matching benchmark and constructs truthful, budget-balanced mechanisms for the resulting profit benchmarks. A sequential posted-price mechanism achieves a 6.75-approximation in the single-dimensional copies instance.

  • Tail reduction: E[GFT^T(t,c)] ≤ 1/(1 − ln 2) GFT*_ud,F_m, reducing tail GFT to the unit-demand matching benchmark.The bound follows by comparing the expected sum of independent excesses with their expected maximum.
  • Benchmark decomposition: The copies reduction relates the unit-demand benchmark to buyer-side and seller-side profit benchmarks, which are approximated by truthful mechanisms.The resulting mechanisms are assembled from these two sides.
  • Tail reduction: The tail is itemwise and sparse: independent item-level excesses make simultaneous large tail events uncommon.For each item, X_j is the excess of the largest singleton GFT above the truncation threshold.
  • Buyer-side benchmark: Randomized procurement menus designate each item to at most one buyer and offer the seller posted prices, producing seller-truthful, ex-post individually rational matching trades.A half-capacity condition yields at least one half of the relaxation’s relevant contribution when a designated item is profitable.
  • Buyer-side benchmark: VCG over restricted procurement menus makes buyers truthful without additional approximation loss, while the complete mechanism is BIC, interim IR, DSIC for the seller, ex-post IR, and ex-post WBB.Buyer-exclusion invariance supports the truthfulness argument.
  • Seller-side benchmark: 6.75-approximation: M_svq is DSIC for buyers and strongly budget balanced in the single-dimensional copies instance.It is implemented as a sequential posted-price mechanism with prices independent of each buyer’s reported valuation.

8 Final Assembly

The final mechanism randomizes between seller- and buyer-side mechanisms, inheriting BIC, IIR, and ex-ante WBB while combining core and tail analyses to obtain a constant-factor first-best GFT guarantee.

  • Mfinal is a randomized delegation protocol that delegates pricing power to the seller with probability p and deploys Mcopy with probability 1 − p.
  • The mechanism is BIC, interim IR, and ex-ante WBB because its component mechanisms satisfy these properties and the independent coin flip preserves them.
  • 27/43 is the probability assigned to the seller-side mechanism when ηS = 1/6.75 and ηB = 1/4 balance the tail contributions.
  • The proof handles either a core-dominated case or a tail-dominated case, using corresponding profit and benchmark bounds.
  • In both cases, Mfinal achieves at least an α fraction of the first-best GFT.
  • The analysis uses ironed virtual values and expected virtual surplus to relate BIC and IR mechanisms’ profits to virtual-surplus maximization.

B Missing Proof from Section 3

This section constructs a two-buyer, two-item example showing that a VCG-based mechanism can run an ex-ante deficit and therefore fail weak budget balance.

  • The example has two unit-demand buyers and an additive seller with two independently uniform costs on [0, 1].
  • Each buyer values only one corresponding item at 1, and the seller’s costs are independently distributed.
  • 0.25 is the optimal expected profit when representing either buyer alone through a single posted procurement price of 0.5.
  • A joint mechanism can offer a bundle price P in [1, 2], accepted when the seller’s total cost is at most P.
  • The VCG payment identities yield an ex-ante net budget of Π∗(1) + Π∗(2) − Π∗(1, 2).
  • Because the expected net budget is strictly negative, the mechanism runs an ex-ante deficit and fails to be weakly budget balanced.

C Missing Proofs from Section 4

The proofs establish pointwise and expectation bounds using independence, then construct posted-price mechanisms from threshold rules and virtual-cost analysis.

  • The proof first establishes a pointwise inequality for sums of nonnegative variables by separating the maximum variable from the remaining sum.
  • The inequality is verified separately when zero, one, or multiple variables are strictly positive.
  • Independence allows the expectation of a product to factor, while the union bound controls the probability that another variable is positive.
  • For each singleton-value vector, a common threshold and procurement-price vector define an order-oblivious posted-price mechanism in the copies instance.
  • The prophet inequality supplies the threshold, and Myerson’s procurement identity converts the resulting ironed virtual-cost surplus into expected buyer profit.
  • The reduction applies after viewing the original seller as a unit-supply agent choosing which item, if any, to trade.

D Missing Proofs from Section 6

The section connects the multi-buyer analysis to Cai–Zhao’s one-sided XOS framework and verifies the fixed-cost welfare and baseline-threshold identities used in that reduction.

  • After fixing costs, the buyer valuations form a one-sided XOS instance over independent item coordinates.
  • The proof imports Cai–Zhao components for truncation, supporting prices, concentration, and entry-fee analysis, while adding market-specific comparisons.
  • The fixed-cost welfare identity equates each buyer’s capped core contribution maximized over feasible allocations with welfare under the allocation rule σC.
  • The baseline-threshold lemma establishes the threshold identities and the second claim follows by dropping buyer i’s term.

D.2 Charging the First-Truncation Loss

The section decomposes buyer contributions into favorite and nonfavorite parts, charging the first-truncation loss against unit-demand and posted-price benchmarks. This connects the auxiliary revenue benchmark to fixed-cost GFT, rather than establishing a general revenue comparison.

  • Favorite contribution: The favorite contribution is bounded by the optimal unit-demand matching GFT.The decomposition satisfies µ(c) ≤ Fav(c) + NonFav(c), with Fav(c) ≤ GFTud.
  • Auxiliary benchmark: The auxiliary benchmark is a rationed sequential posted-price revenue over unit-demand buyers with singleton values Vij(tij).Each buyer may purchase at most one available item at a nonnegative buyer–item price.
  • First-truncation loss: The first-truncation analysis bounds the nonfavorite contribution using the retained contribution and a high-singleton overlap term.The overlap term is bounded by 2/(1 − b) = 8/3 times the RSPM benchmark when b = 1/4.
  • Scope: The comparison between this auxiliary revenue benchmark and GFT is specific to the fixed-cost reduction.The supplied limitation does not claim a general revenue-to-GFT comparison.
  • Benchmark comparison: Pointwise, auxiliary posted-price revenue is at most the singleton GFT of its matching, and therefore at most optimal unit-demand matching GFT.Taking expectations and the supremum yields the benchmark comparison.

D.3 Supporting Prices and the Fixed-Cost ASPE

This section introduces the bridge from the auxiliary one-sided analysis to the original two-sided market. Exact supporting prices and an attainable residual-surplus proxy enable a fixed-cost ASPE whose seller profit is analyzed through the Cai–Zhao framework.

  • Market bridge: The main new bridge connects the auxiliary one-sided instance to the original two-sided market.It is identified as the section’s central new step.
  • Residual-surplus proxy: Lemma D.7 establishes feasibility of the residual-surplus proxy for every buyer type and available item set.Its proof uses an XOS clause attaining the truncated valuation and the fact that truncation deletes item coefficients.
  • Fixed-cost ASPE: The fixed-cost ASPE profit bound applies Cai–Zhao’s supporting-price and entry-fee analysis with b = 1/4.The induced valuation is XOS over independent items, and exact supporting prices give α = 1.
  • Entry fees: Exact supporting prices and the residual-surplus domination preserve the median-fee acceptance argument in the original market.The buyer’s true utility from the cost-plus-markup menu pointwise dominates the residual-surplus proxy used for entry fees.

D.4 Completing the Fixed-Cost Bound

The fixed-cost analysis is completed by proving buyer-side truthfulness and combining the contribution bounds with convex-analytic and monotone-selector arguments. These steps control the auxiliary benchmarks and establish the required structural properties for implementation.

  • Truthfulness: Buyer-side ASPE is DSIC and ex-post individually rational because prices and entry fees are fixed independently of the buyer’s report.Truthful utility maximization is dominant, while rejecting the menu gives utility zero.
  • Final inequality: The resulting bound includes the term 8µ(c) − 57/8 GFTud Fm(c).This expression follows after substituting the intermediate inequality into Lemma D.8 and applying Lemma D.5 again.
  • Monotone selector: The deterministic matching selector minimizes cardinality, then maximizes the designated item’s priority, then uses a fixed lexicographic order.These first two tie-breaking rules support monotonicity in each item cost.
  • Monotone selector: The selected matching uses each item monotonically: lowering an item’s cost cannot make that item cease to be selected under the specified selector.The argument compares maximum weights among matchings using versus omitting the item and handles equality through tie-breaking.

E.3 Proof of Lemma 7.7

The proof of Lemma 7.7 establishes compactness and continuity of the procurement-menu family, then gives a direct implementation with seller-side DSIC, ex-post IR, and ex-post strong budget balance.

  • Menu regularity: The procurement-menu family is compact, and buyer utility is continuous in both menu parameters and buyer type.Compactness follows from bounded coordinates and closed constraints; continuity follows from finitely many menu realizations and dominated convergence.
  • Implementation: Every fixed procurement menu therefore has an equivalent direct implementation that is DSIC and ex-post individually rational for the seller.The same menu also preserves ex-post strong budget balance for trade payments.
  • Menu regularity: For a fixed procurement menu, the induced allocation and trade-payment rule are independent of the reporting buyer’s type.This yields type-independent trade probabilities and expected trade payments for each buyer.
  • Seller incentives: Seller truth-telling is dominant because each buyer cluster selects the item maximizing the seller’s true profit, with additive costs across disjoint clusters.The seller can always induce the empty selection and receive nonnegative utility.
  • Budget balance: Trade payments are ex-post strongly budget balanced: every traded item’s buyer payment equals the seller’s receipt.This equality holds for every realization of menus, reports, and costs.
Loading 2609.02872v1…