CS Paper Radar

The Price of Anarchy in Markets for Lemons

Naveen Durvasula, Tim Roughgarden

cs.GT cs.DSecon.TH ·submitted 2026-11-11 00:17 UTC · v1

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.

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

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

On Competing Sellers with Substitutable Goods

cs.GT ·2026-11-04 ·Moshe Babaioff, Yuval Grofman, Brendan Lucier, Raghuvansh R. Saxena
similarity 0.66
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

Regret Bounds for Profit Maximization in Bilateral Trade: Learning the Best Posted-Price Mechanism

cs.GT cs.DScs.LG ·2026-11-05 ·Johannes Brüstle, Simone Di Gregorio, Federico Fusco, Stefano Leonardi
similarity 0.66
Abstract

Bilateral trade models the task of intermediating between two strategic agents, a seller and a buyer, willing to trade a good for which they hold private valuations. We study this problem from the perspective of a profit-maximizing broker in a regret minimization framework. At each time step, a new seller and buyer arrive and the broker proposes a trading price to each agent. The trade happens if both agents accept, and the profit of the broker is the difference between the price received from the buyer and the one paid to the seller. At the end of each interaction, the learner only observes whether the trade occurred, and its goal is to achieve sublinear regret relative to the best fixed pair of prices in hindsight. We start by investigating the adversarial version of the problem, where buyer and seller valuations are generated by an adversary. In this setting, we construct a polynomial-time learning algorithm with a $\tilde O(T^{\frac 23})$ regret rate, which is nearly tight even if the valuations are drawn i.i.d. from independent distributions, thus matching the rate for one-sided pricing. Our adversarial algorithm combines a localized estimation procedure with an information-based minimax construction. We then consider valuations drawn i.i.d. from independent distributions satisfying the monotone-hazard-rate (MHR) property and provide a learning algorithm with nearly tight $\tilde{O}(\sqrt{T})$ regret. The algorithm combines localized estimation with a stochastic convex bandit routine applied to the negative logarithm of expected profit. Finally, we complement this result by showing a separation between MHR and regular distributions, proving that the minimax regret rate in the latter setting is $\tilde Θ(T^{\frac 35})$. This last result contrasts with the $\tilde{O}(\sqrt{T})$ regret bound that can be obtained for one-sided pricing with regular distributions.

0.15

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

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.65
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 and Limits of Money Burning in Bilateral Trade

cs.GT ·2026-11-03 ·Moshe Babaioff, Noam Nisan, Ariel Shaulker
similarity 0.65
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.

0.23

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