Trade mechanisms in multi-item markets achieve half the optimal gains
Second-Best Trade Is Half Efficient in Multidimensional Markets
Computer Science and Game Theory
Summary
When buyers and sellers trade many items with complex rules about what trades can happen together, it's challenging to design systems that do the best possible deals. The authors found that even with these complexities, you can always design a system that achieves at least half the best possible benefits from trading. Their approach uses advanced mathematical tools to prove this bound without needing to find the exact best system. This extends previous knowledge from simple one-item trades to more complicated markets.
What this means in practice
- •For market platform designers: Design trading platforms that guarantee at least half the maximum possible trade benefits in complex multi-item markets with constrained trades.
- •For auction system engineers: Develop auction mechanisms for multidimensional goods that balance incentives, rationality, and budget without needing to solve for exact optimal strategies.
A theory result. No direct application yet.
Authors
Dirk Bergemann, Yang Cai, Kangning Wang, Jinzhao Wu, Renzhe Xu
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.