CS Paper Radar

The Power and Limits of Money Burning in Bilateral Trade

Moshe Babaioff, Noam Nisan, Ariel Shaulker

cs.GT ·submitted 2026-11-03 19:03 UTC · v1

Abstract

We study the power of money burning in bilateral trade. In this problem, a seller owns an indivisible item, a buyer would like to acquire it, and each of these two traders has a private value for the item and the values are sampled from independent distributions. We ask whether the traders can benefit from a mechanism that burns money, that is, one that charges the buyer more than it pays the seller, so that neither trader enjoys the difference (money burnt is a loss for the traders). Is it possible that the traders will ever be better off if the trade mechanism can burn money? For Bayesian incentive-compatible mechanisms and for deterministic dominant-strategy incentive-compatible (DSIC) mechanisms, it is known that money burning is always a waste and can only hurt the traders. Maybe surprisingly, we show that once a DSIC mechanism can use randomization, money burning can significantly benefit the traders, and the gain of each of them can be arbitrarily large. In contrast, we show that the power of DSIC randomized mechanisms that burn money is still very limited in the sense that they cannot guarantee any constant fraction of the first-best gains-from-trade.

Closest papers

Nearest neighbours by meaning across the whole index.

On Competing Sellers with Substitutable Goods

cs.GT ·2026-11-04 ·Moshe Babaioff, Yuval Grofman, Brendan Lucier, Raghuvansh R. Saxena
similarity 0.68
Abstract · 84 pages

We study mechanism design by an incumbent seller facing competition from an entrant seller of a substitute good. The incumbent commits to a potentially randomized mechanism before her competitor responds. A unit-demand buyer with fixed, publicly known values for the two goods observes both mechanisms and may interact with them in either order. How should a revenue-maximizing incumbent design her mechanism when her product is superior or inferior to her competitor's? We determine the incumbent's exact optimal revenue and characterize all mechanisms that obtain it. Commitment and randomization allow her to earn strictly positive revenue even against an arbitrarily superior product, despite earning nothing under posted-price (i.e., Bertrand) competition. Optimal mechanisms can require a continuum of lottery options, even though the buyer selects only one in equilibrium: unselected options shape the competitor's incentives rather than screen private buyer information. We also show that the buyer's ability to choose the interaction order can be strictly beneficial to the incumbent, even though the incumbent is always visited first at equilibrium. Finally, we show that without commitment, every pure Nash equilibrium yields Bertrand revenues even with randomized mechanisms.

0.23

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.41

The Power of Simple Mechanisms: A Tight $e$-Approximation for Gains from Trade in Matching Markets

cs.GT ·2026-09-29 ·Xiaohui Bei, Wenhao Wu, Shengwei Zhou
highly cited similarity 0.66
Abstract

We study how well simple mechanisms approximate gains from trade (GFT) in two-sided matching markets with independent buyer values and seller costs, where feasible outcomes form an arbitrary downward-closed family of matchings. This model includes bilateral trade and double auctions as special cases. We focus on the Generalized Random-Offerer (GRO) mechanism, which is an equal mixture of the Generalized Sellers-Offering Mechanism (GSOM) and the Generalized Buyers-Offering Mechanism (GBOM). We determine GRO's exact worst-case approximation ratio with respect to first-best GFT, showing that it is $e$. This improves the previous $3.15$ approximation guarantee (Babaioff et al. STOC 2026) for the same mechanism. In bilateral trade, the result implies a $1/e$ guarantee for the random-offerer mechanism, improving the previous $1/π$ bound (Jo 2026). Our analysis uses a two-dimensional inequality in quantile space to compare first-best GFT with optimal one-sided auction profits. For each potential trade, we identify the region of buyer values and seller costs for which the first-best allocation selects that trade, and then randomly shrink this region in quantile space, yielding posted-price rules whose expected profits can be evaluated exactly. We establish tightness of the $e$ approximation by constructing markets with regular type distributions, pairwise disjoint trading edges, and a single knapsack constraint. On these instances, GRO's expected GFT approaches a $1/e$ fraction of first-best GFT, therefore ruling out any better guarantee even under these restrictions.

0.45

Approximately Efficient Multidimensional Bilateral Trade

cs.GT ·2026-09-02 ·Aviad Rubinstein, Xizhi Tan, Zixin Zhou
top venuehighly cited similarity 0.66
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

The Price of Anarchy in Markets for Lemons

cs.GT cs.DSecon.TH ·2026-11-11 ·Naveen Durvasula, Tim Roughgarden
similarity 0.65
Abstract

We study the worst-case equilibrium gains from trade in simple bilateral trade mechanisms with interdependent valuations. Equilibria in such settings are typically complex, as proposed prices can convey private information held by the proposer. Such equilibria suffer lost gains from trade both due to the inefficiency introduced by screening (as in independent private value settings) and due to adverse selection. We identify broad conditions under which, nevertheless, sequential equilibria are guaranteed to achieve a constant fraction of the first-best gains from trade. Our bounds quantify the central role of rare pessimistic seller signals and rare optimistic buyer signals. The results apply to seller-proposer, buyer-proposer, and random-proposer mechanisms. The key idea in our analysis is to relate equilibrium gains from trade to proposer profits in an auxiliary market with independent private values.

0.21

Second-Best Trade Is Half Efficient in Multidimensional Markets

cs.GT ·2026-11-10 ·Dirk Bergemann, Yang Cai, Kangning Wang, Jinzhao Wu, Renzhe Xu
theory similarity 0.64
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.

0.05

An Improved Upper Bound for the Random-Offerer Mechanism in Bilateral Trade via Recursive Hard Instances

cs.GT ·2026-10-05 ·Heyang Shang, Jing Chen
theory similarity 0.64
Abstract

We study the worst-case efficiency of the random-offerer mechanism in bilateral trade relative to the first-best gains from trade. We construct a family of independent buyer value and seller cost distributions whose ratio converges to $0.436943488\ldots$, improving the previous upper bound of $0.460242308\ldots$. Our construction combines recursively nested seller distributions with downward transport of buyer values. The recursive structure allows contributions from different scales to accumulate, leading to stronger hard instances. We analyze this construction through a recurrence and obtain an analytic characterization of the limiting constant.

0.16

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.64
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