CS Paper Radar

Sharp Second-Best Welfare in Bilateral and Matching Markets

Zhengyang Liu, Ying Qin, Zihe Wang

cs.GT ·submitted 2026-09-29 12:25 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

From Bilateral Trade to Matching Markets: Sharp Gains from Trade

cs.GT ·2026-09-25 ·Zhengyang Liu, Ying Qin, Zihe Wang
similarity 0.79
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

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

The Exact Welfare Guarantee of Fixed-Price Bilateral Trade

cs.GT econ.TH ·2026-09-27 ·Tingyi Lin, Yichen Shi, Ke Dong, Jiazhuo Li, Shawn Yu +1 more
similarity 0.73
Abstract

A seller and a buyer with independent private values can trade only at a posted price. We determine the worst case of this mechanism exactly: the best posted price always guarantees a $β_*=0.738024\ldots$ fraction of first-best welfare, where $β_*$ is given in closed form by the root of an explicit equation, the worst-case buyer is unique up to scaling, and the worst case is never attained. This closes the gap $[0.7292,0.73805]$ left by work from SODA 2016 through two STOC 2023 papers and AAAI 2026. The proof is an explicit certificate of optimality: after one change of variables, the gap between the optimum and the value of any buyer is a sum of nonnegative integrals, as in a linear-programming dual, and equality identifies the worst-case shape. The certificate also gives the complete tradeoff between gains from trade and the seller's initial welfare: when first-best gains from trade are a fraction $κ$ of initial seller welfare, the exact worst-case fraction $ρ(κ)$ of gains obtained by the best price satisfies $ρ(κ)\sim2/\log(1/κ)$ as $κ\to0$. The worst-case buyer's survival function has two constant segments joined by an explicit nonexponential curve, and the worst case is approached through a vanishing atom escaping to infinity. The same constant is the exact guarantee of dominant-strategy mechanisms with individual rationality and strong budget balance in every realization. For two units with increasing submodular valuations, an explicit finite instance has ratio below $0.7290804$, so two units are strictly harder than one. Fixing the buyer, we characterize the least probability a random common price needs to guarantee a given ratio against every seller; bounding this quantity over all buyers would determine the exact two-unit constant. Within an explicit family the worst ratio is $0.729080\ldots$, conjectured to be the two-unit constant.

0.16

Approximately Efficient Multidimensional Bilateral Trade

cs.GT ·2026-09-02 ·Aviad Rubinstein, Xizhi Tan, Zixin Zhou
top venuehighly cited similarity 0.72
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 Exact Approximation Ratio of the Optimal Fixed-Price Mechanism in Bilateral Trade

cs.DS ·2026-08-20 ·Tao Jiang, Minbo Gao, Shaowei Cai
similarity 0.69
Abstract

In bilateral trade, a seller owns an item that a buyer may value more, and their values are drawn independently from known distributions. A fixed-price mechanism posts a single price and trades exactly when both agents accept it. How much of the first-best expected welfare can the optimal fixed price guarantee? A sequence of analytic and computer-assisted results narrowed the worst-case ratio to the interval $[0.7292,0.73805]$, but its exact value remained open. We determine this ratio exactly: it equals $0.7380243357\ldots$, given in closed form through the unique root of an explicit one-dimensional equation. The guarantee holds for every pair of independent nonnegative distributions with finite means, including atomic and unbounded ones, and an explicit family of instances shows that no larger constant is possible. The proof reduces the problem, through put and call transforms of the two distributions and a worst-case choice of seller, to a one-dimensional control problem for the buyer. A logarithmic change of variables makes this problem strictly convex, so its first-order conditions certify a global optimum. The optimizer switches exactly once from an interior arc to the boundary and can be integrated in closed form. Realizing it yields a bounded seller and a bounded buyer together with a vanishing buyer atom at a diverging value. The worst case is approached by this family but attained by no instance.

0.32

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.67
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.44

Welfare Approximation in Multilateral Trade

cs.GT ·2026-08-11 ·Tomer Ezra, Aadityan Ganesh, Aviad Rubinstein
theory similarity 0.66
Abstract

We introduce the study of \emph{multilateral trade}: a mechanism-design problem in which a single potential trade involves $k$ agents and can be executed only if all $k$ agents agree to participate. The classical case $k=2$ is the well-studied bilateral trade problem, where a seller and a buyer with private values must decide whether to trade an item initially held by the seller. Existing extensions of bilateral trade have largely focused on markets with many buyers and many sellers, but where each realized transaction is still bilateral, requiring agreement only between the matched buyer and seller. Our formulation captures settings in which the trade itself requires joint participation, coupling the agents' incentives and creating new challenges. We study welfare approximation in this setting under incentive compatibility, individual rationality, and budget balance. We give a DSIC mechanism with approximation ratio $O(k^2)$, and a BIC mechanism with approximation ratio $\widetilde O(k^{3/2})$. We prove matching lower bounds up to polylogarithmic factors. Finally, we extend the model to an $\ell$-out-of-$k$ partial-agreement setting, where the trade may occur once at least $\ell$ agents participate. In this relaxed model, the welfare guarantees improve smoothly as $k-\ell$, the number of agents whose participation is not required, grows, and we obtain matching upper and lower bounds up to polylogarithmic factors.

0.04

A Weakly Group Strategy-Proof and Pareto-Stable Matching Mechanism with Two-Sided Indifferences under Gross Substitutes

cs.GT econ.TH ·2026-10-22 ·Yasushi Kawase, Ryosuke Sato
similarity 0.65
Abstract

We study finite many-to-one matching markets with indifferences on both sides and publicly known firm preferences over sets of workers. A standard approach breaks ties uniformly at random and runs deferred acceptance, which is strategy-proof for workers but may select a weakly stable matching that is Pareto dominated under the agents' original preferences. For the broad class of markets in which each firm's preferences admit a gross substitutes (GS) representation, we construct a deterministic generalized deferred acceptance mechanism that is weakly stable, Pareto efficient with respect to both sides, worker weakly group strategy-proof, and implementable in strongly polynomial time given value oracles for the GS representations. This domain includes nonresponsive firm preferences, such as additive scores under matroid constraints and assignment values. Our analysis bridges ordinal matching with indifferences and competitive equilibria under imperfectly transferable utility. Although the mechanism uses only ordinal comparisons, it returns a seller-optimal equilibrium matching of a tiered auxiliary market, and the equilibrium structure of this market yields the stability, efficiency, and incentive guarantees.

0.07