Research map / Learning theory and algorithms / Submodular and game algorithms
Non-excludable Bilateral Trade between Groups
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies multiplayer bilateral trade where many buyers and sellers share a single allocation and payment, giving a dichotomy: efficiency in the limit is achievable when buyers value the item more in expectation, and impossible otherwise for IC mechanisms, deterministic or smooth randomized.
Problem
Bilateral trade with private valuations is impossible to make efficient, IC, IR and budget balanced (Myerson-Satterthwaite). The paper asks whether having many self-interested buyers and sellers on each side, who cannot be excluded and share allocation and payment, permits efficient trade.
Approach
Model multiplayer bilateral trade where all buyers share one allocation and payment and all sellers share one receipt, characterize IC deterministic mechanisms as voting-like monotone rules with a common threshold price, show a simple forced-trade mechanism is efficient in the limit when E[v]>E[c], and prove impossibility otherwise, including for twice-differentiable randomized mechanisms.
Key results
- When E[v]>E[c], the forced-trade mechanism is IC, SBB, and achieves GFT/FB = 1 - e^{-Omega(n)} as n grows.
- When E[v] <= E[c], no IC mechanism is efficient in the limit, and for a uniform/constant-cost instance the ratio of any deterministic IC mechanism to first best is at most sqrt(3)/2 + o(1).
- Simulations with n=10000 and (mu_F, mu_G)=(0.51, 0.49) reach efficiency near 1.0 for Normal and Uniform distributions, while n=5 gives efficiency around 0.36 for Normal.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase the number of agents | Forced-Trade Mechanism · Uniform, (μF, μG)=(0.55, 0.45) | IR probability: 0.464824 -> 0.969823 | Helped |
| Increase the number of agents | Forced-Trade Mechanism · Uniform, (μF, μG)=(0.55, 0.45) | Efficiency: 0.823521 -> 0.999900 | Helped |
| Reduce the gap between expected buyer value and seller cost | Forced-Trade Mechanism · n=100, Normal, Uniform, Bernoulli, and Mixed distributions | IR probability | Hurt |
| Use higher-variance valuation distributions instead of lower-variance distributions | Forced-Trade Mechanism · Generated distributions | Efficiency | Hurt |
Surprising findings
- Smooth randomized IC mechanisms cannot achieve any constant approximation to first best when sellers value the item more in expectation, which is a stronger negative result than for deterministic mechanisms.
Limitations
- Positive result requires buyers' expected value to strictly exceed sellers', and the forced-trade mechanism fails IR with nonvanishing probability at small n.
- Results assume shared allocation and payment within each side and a common Bayesian prior, with IC rather than relaxed incentive notions.
Experimental setup
Metrics: efficiency (GFT/FB) empirical IR probability
Baselines: Forced-Trade Mechanism
Builds on: Myerson's lemma Myerson-Satterthwaite impossibility
Closest papers by meaning
- Fair Online Bilateral Trade (NeurIPS 2024 · similarity 0.84)
- Fair Division with Market Values (AAAI 2025 · similarity 0.84)
- Feature-Based Online Bilateral Trade (ICLR 2025 · similarity 0.83)
- Decentralized Convergence to Equilibrium Prices in Trading Networks (AAAI 2025 · similarity 0.83)
- Epistemic Pairwise Maximin Share (NeurIPS 2026 · similarity 0.83)
- Plant-and-Steal: Truthful Fair Allocations via Predictions (NeurIPS 2024 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.