Research map / Bandits and online learning / Online convex optimization and games
Fair Online Bilateral Trade
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 online bilateral trade with a fairness-aware reward (min of seller and buyer utilities, "fair gain from trade") and characterizes regret regimes under bit feedback and full feedback: Theta(ln T) deterministic, linear stochastic in general, Otilde(T^{2/3}) under independence, and O(sqrt T) with full feedback.
Problem
Online bilateral trade where a platform posts prices to seller-buyer pairs; standard gain-from-trade objectives can produce very unequal utility shares, so the platform should be rewarded by the minimum of the two utilities while learning only from accept/reject bits.
Approach
Replace the sum of utilities (gain from trade) with the minimum of utilities (fair gain from trade), show that GFT-no-regret algorithms fail under this objective, and exploit a convolution identity for FGFT to estimate its expectation from binary accept/reject feedback under independence, yielding matching upper and lower regret bounds.
Key results
- Stochastic general case: any algorithm suffers regret at least T/48 on some i.i.d. distribution (linear regret).
- Stochastic independent case: Convolution Pricing achieves O~(T^{2/3}) regret, matched by an Omega(T^{2/3}) lower bound.
- Deterministic case: regret is Theta(ln T), via Double Binary Search upper bound and an Omega(log T) lower bound.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Assume seller and buyer valuations are independent | Fair bilateral trade with partial feedback · Stochastic valuations | regret: R_T \ge \frac{T}{48} -> \widetilde{O}(T^{2/3}) | Helped |
| Use Convolution Pricing under independent valuations | Fair bilateral trade with partial feedback · Stochastic, independent valuations | regret: \widetilde{O}(T^{2/3}); c T^{2/3} | Mixed |
| Reveal true seller and buyer valuations after each round | Fair bilateral trade · Stochastic valuations | regret: \widetilde{O}(T^{2/3}) -> O(\sqrt{T}) | Helped |
| Reveal true valuations after each round | Fair bilateral trade · Deterministic valuations | regret: O(\ln T) -> 1/2 | Helped |
| Optimize fair gain from trade instead of standard gain from trade | No-regret algorithm for standard bilateral trade · Stochastic instance with S_t in {0,1-h} and B_t=1 | fair gain from trade regret: h/2; 1/4 | Hurt |
| Use Double Binary Search Pricing | Fair bilateral trade with partial feedback · Deterministic valuations | regret: \frac{1}{32} \log_2(T); O(\ln T) | Helped |
| Use Follow the Best Empirical Price with full feedback | Fair bilateral trade · Stochastic valuations | regret: O(\sqrt{T}); c \sqrt{T} | Helped |
Surprising findings
- A no-regret algorithm for standard gain from trade can have linear regret under fair gain from trade, even being no-alpha-regret for any alpha.
- In the deterministic case, gain from trade admits constant regret while fair gain from trade requires Theta(ln T) regret.
Limitations
- Stochastic regret is linear without the independence assumption between seller and buyer valuations.
- The T^{2/3} stochastic independent bounds are tight only up to logarithmic factors.
- Analysis is single-item, single seller-buyer pair per round; multi-agent and contextual extensions are left open.
Experimental setup
Metrics: cumulative regret
Baselines: Gain-from-trade no-regret algorithms
Builds on: Convolution-based pricing for standard bilateral trade Partial monitoring revealing action Dvoretzky-Kiefer-Wolfowitz inequality
Closest papers by meaning
- Feature-Based Online Bilateral Trade (ICLR 2025 · similarity 0.90)
- Improved Regret Bounds for Online Fair Division with Bandit Learning (AAAI 2025 · similarity 0.87)
- Honor Among Bandits: No-Regret Learning for Online Fair Division (NeurIPS 2024 · similarity 0.87)
- Learning Safe Strategies for Value Maximizing Buyers in Uniform Price Auctions (ICML 2025 · similarity 0.86)
- A Parametric Contextual Online Learning Theory of Brokerage (ICML 2025 · similarity 0.86)
- Equilibrium of Data Markets with Externality (ICML 2024 · similarity 0.86)
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.