CS Paper Radar

Second-Best Trade Is Half Efficient in Multidimensional Markets

Dirk Bergemann, Yang Cai, Kangning Wang, Jinzhao Wu, Renzhe Xu

cs.GT ·submitted 2026-11-10 18:48 UTC · v1
theory

Abstract

We prove that at least half of the first-best gains from trade can always be achieved in multidimensional two-sided markets with additive values and costs and arbitrary downward-closed feasibility constraints. The guarantee is achieved by a mechanism satisfying Bayesian incentive compatibility, interim individual rationality, and strong budget balance, and is tight already in single-item bilateral trade. Types are independent across agents, while the coordinates of each agent's type may be arbitrarily correlated. Feasibility constraints may couple trades across items and agents. This extends the known tight one-half guarantee for single-item bilateral trade. Our proof develops a new application of the Cai--Devanur--Weinberg duality framework. We show that the objective of every feasible dual is at least half of the first best. Strong duality then yields the guarantee without characterizing an optimal mechanism or dual. The key observation is that every feasible dual induces continuous-time Markov chains that, when stopped by exponential clocks, recover true types as expectations of virtual types. The dual constraints control the rate at which these chains change the prior distributions. We establish our bound by combining this control with a coupling of the agents' clocks.

Closest papers

Nearest neighbours by meaning across the whole index.

Approximately Efficient Multidimensional Bilateral Trade

cs.GT ·2026-09-02 ·Aviad Rubinstein, Xizhi Tan, Zixin Zhou
top venuehighly cited similarity 0.78
Abstract · To appear in the 67th IEEE Symposium on Foundations of Computer Science (FOCS 2026)

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.

0.47

Second-Best Gains from Trade in Matching Markets

cs.GT ·2026-09-16 ·Xiaohui Bei, Bo Li, Wenhao Wu, Shengwei Zhou
benchmarktheoryhighly cited similarity 0.74
Abstract · 44 pages, 2 figures; Updated with the section on Subsidized Markets

We study gains from trade (GFT) in two-sided matching markets with independent private types and arbitrary downward-closed feasibility constraints. The second-best benchmark is the maximum expected GFT achievable by a Bayesian incentive-compatible, interim individually rational mechanism that is strongly budget balanced at every report profile. These constraints generally preclude attaining the first-best GFT and raise the question of how much efficiency must be lost. We prove that the second-best GFT is at least one half of the first-best GFT in every such matching market. This recovers and generalizes the recent $1/2$ guarantee for bilateral trade by Liu, Qin, Ren, and Wang to markets with multiple buyers and sellers and arbitrary downward-closed feasibility constraints. Together with their matching upper bound for bilateral trade, our result establishes a tight worst-case ratio of $1/2$ for this general class of matching markets. Our proof builds on the virtual-GFT framework of Brüstle, Cai, Wu, and Zhao to reduce the problem to a one-parameter Lagrangian. The main step is a geometric, edge-by-edge analysis based on first-best edge-selection regions, combined with a randomized contraction in rank space. The same analysis also determines the exact worst-case efficiency for every level of outside subsidy. In particular, even a small outside subsidy can significantly improve the worst-case guarantee.

0.33

From Bilateral Trade to Matching Markets: Sharp Gains from Trade

cs.GT ·2026-09-25 ·Zhengyang Liu, Ying Qin, Zihe Wang
similarity 0.66
Abstract

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.

0.40

Optimal Regret for Profit Maximization in Bilateral Trade

cs.GT cs.LG ·2026-11-06 ·Matteo Castiglioni, Anna Lunghi, Alberto Marchesi
theory similarity 0.66
Abstract

Learning to profit from trade requires learning both sides of a market: what a seller is willing to accept and what a buyer is willing to pay. We study repeated bilateral trade, where an intermediary posts a purchase price to a seller and a sale price to a buyer whose valuations are drawn from an unknown joint distribution. Trade occurs only if both parties accept their respective prices, in which case the intermediary earns the difference between the two prices. The intermediary observes only whether trade occurs, without observing either valuation. We show that learning both sides of the market is no harder, in terms of regret, than learning just one. Specifically, we design an algorithm achieving regret $\widetilde{\mathcal{O}}(T^{2/3})$ against the best fixed pair of prices, matching, up to logarithmic factors, the classical lower bound for one-dimensional dynamic pricing. Our result shows that the classical one-dimensional regret rate survives the transition to two dimensions, raising the question of whether this absence of a curse of dimensionality extends to arbitrarily high dimensions.

0.13

Sample Complexity of the Second-Best Bilateral Trade

cs.GT ·2026-08-26 ·Qiaoyun Shi, Shengxin Liu, Zongqi Wan
benchmark similarity 0.65
Abstract

We study the sample complexity of learning near-optimal bilateral trade mechanisms. Unlike previous work on learning simple or fixed-price bilateral-trade mechanisms, we focus on mechanisms satisfying Bayesian incentive compatibility (BIC), interim individual rationality (IIR), and ex-ante weak budget balance (WBB). In other words, our target is to design a sample-based mechanism that achieves the second-best gains-from-trade benchmark. We give matching or nearly matching upper and lower bounds in three regimes. For regular product distributions on $[0,h]^2$, additive $\varepsilon$-approximation has sample complexity $\widetildeΘ(h^2/\varepsilon^2)$. For multiplicative $(1-α)$-approximation under the same assumptions, we find that the sample complexity is $\widetildeΘ(h/(\mathrm{SB}(D)α^2))$, which is benchmark-sensitive with unavoidable dependence on the second-best gains from trade $\mathrm{SB}(D)$. We also investigate unbounded distributions under a monotone hazard rate (MHR) assumption. The sample complexity depends on the ratio $χ_μ(D)=μ(D)/\mathrm{SB}(D)$, where $μ(D)$ is the sum of the buyer's expected value and the seller's expected cost.

0.05

Tight Liquid Welfare Guarantees for Auctions with Budgets via LP Duality

cs.GT ·2026-09-30 ·Twan Kroll, Guido Schäfer, Artem Tsikiridis
theory similarity 0.65
Abstract

We study the efficiency of auctions with budget-constrained bidders and derive tight price of anarchy (PoA) bounds for coarse correlated equilibria (CCE). To this end, we develop a general framework that reduces proving PoA guarantees to finding feasible solutions to the dual of a linear program. The LP is formulated over a small number of per-bidder equilibrium statistics, incorporates constraints implied by the auction setting and equilibrium behavior, and captures a novel smoothness notion tailored to budget-constrained environments; we provide a reduction from classical smoothness to this new notion. Our approach enables simple and tight PoA analyses across a broad range of auction formats. Using our framework, we obtain tight liquid welfare guarantees for simultaneous first-price, second-price, and all-pay auctions, simultaneous auctions with restricted uniform bidding interfaces, discriminatory and uniform price multi-unit auctions, and generalized first-price position auctions. Beyond budget-constrained settings, we derive new lower bounds for the budget-free uniform price auction and generalized second-price auction; in particular, our lower bound for the uniform price auction matches the upper bound of $3.146$ by de Keijzer et al. (2013).

0.16

On the Power of Determinism in Multi-Item Auctions

cs.GT cs.DM ·2026-09-28 ·Yiannis Giannakopoulos, Johannes Hahn
theory similarity 0.65
Abstract · Improved the upper bound on REV/max{SREV,BREV} from 3 to 2.5 for independent items, and added a lower bound of 2.19. For iid items, improved…

We study the classical multi-item monopoly setting with a single additive buyer and $m$ heterogeneous items whose values are independent but not necessarily identically distributed. We compare the revenue (REV) of the optimal truthful auction, which in general may be randomized or complicated, with the revenues of three simple deterministic auctions: selling all items separately (SREV), selling them as a single grand bundle (BREV), and choosing the better of the two. Our technical cornerstone is a general upper bound on the optimal multidimensional revenue, parameterized by freely chosen item-wise caps, and expressed in terms of optimal single-item, Myersonian revenues and basic statistics of the value distributions. We derive this inequality through Lagrangian duality for a nonlinear programming formulation of the worst-case approximation ratio of separate-selling. Combining this inequality with carefully chosen caps and a probabilistic analysis of the resulting terms, we obtain improved approximation guarantees for all three deterministic auctions, both for general independent values and for iid values. Notably, we prove that $REV\le 2.5\max\{SREV,BREV\}$, improving the long-standing $5.2$ factor of Ma and Simchi-Levi and the $6$ factor of Babaioff, Immorlica, Lucier, and Weinberg. We complement this upper bound with a construction establishing a lower bound of $2.19$, improving the bound of $2$ by Rubinstein. For two iid items, we determine the exact approximation ratio of selling separately. Our proof constructs tight Lagrangian dual certificates for the aforementioned programming formulation, when item values lie in the grid $\{0,1/K,2/K,\dots,1\}$, for any discretization parameter $K$. Taking $K\to\infty$ yields the tight ratio $1+W(1/e)\approx1.2785$ in the continuous-valued setting, where $W$ is the Lambert-W function, closing the $[1.278,1.368]$ gap left by Hart and Nisan.

0.41

Sharp Second-Best Welfare in Bilateral and Matching Markets

cs.GT ·2026-09-29 ·Zhengyang Liu, Ying Qin, Zihe Wang
similarity 0.64
Abstract

How much social welfare must a market lose because values are private? We determine the sharp ratio of second-best to first-best welfare under independent nonnegative types, Bayesian incentive compatibility, interim individual rationality, and no expected budget deficit. The ratio is approximately $0.8882516903$ for arbitrary priors and $0.9113893681$ when buyers have monotone hazard rates and sellers are unrestricted. The arbitrary-prior guarantee holds for every downward-closed family of feasible matchings; the MHR guarantee holds when every matching of a compatibility graph is feasible. Both constants are \revise{attained}{sharp} already in bilateral trade. The proof keeps the sellers' initial endowment inside the budget Lagrangian. For arbitrary priors, a common threshold decomposition reduces the problem to three-parameter power-law distributions. For monotone hazards, common transformations of buyer and seller scores reduce it to shifted capped exponential buyers; a typewise allocation certificate and an explicit worst-case seller satisfy the same boundary equation. The bilateral-to-matching framework, with a welfare endowment charge and an MHR-preserving packing argument, transfers these affine inequalities without loss. We give exact variational characterizations of both constants and reproducible interval certificates for their numerical evaluation. Unrestricted signed transfers also permit pointwise strong budget balance.

0.14