Optimal Online Learning in Bilateral Trade Through Interest

Mengfan Ma, Haoyu Song, Yiran Tong

Nov 1, 2026arXiv:2611.01999v1

cs.GT

Scorecard· 16/16

6.5/10 impact

Technically strong, complete tight characterization of a new interest-based budget relaxation, but niche and an incremental extension of a recent line of work.

Abstract

We consider online learning in bilateral trade on platforms such as Uber, Airbnb, and eBay. In each round, a platform posts a payment to a seller and a price to a buyer, both with private valuations, and observes only whether trade occurs. Its objective is to maximize cumulative gains-from-trade, the sum of the differences between buyers' and sellers' valuations across completed trades. We measure the platform's performance by its regret against the best fixed common price. Financial self-sufficiency motivates global budget balance (Bernasconi et al., 2024), which allows profits from some trades to subsidize others, provided that the final balance is nonnegative. Such financial planning should also account for the time value of money: profits earned earlier can accumulate interest, providing additional funds for future subsidies. Motivated by this observation, we introduce global budget balance with interest, under which a platform starting with no funds can use both trading profits and accrued interest to finance subsidies. For a horizon of $T$ rounds and a fixed exponent $θ\ge0$ , we consider the per-round interest rate $r_T = T^{-θ}$ . We study two classic valuation models, adversarial and correlated i.i.d., and obtain tight bounds on regret against the best fixed common price in both. As the interest rate grows, optimal regret in each model drops from $\tildeΘ(T^{3/4})$ to $\tildeΘ(T^{5/7})$ . The intermediate rates differ: $\tildeΘ(T^{3θ/4})$ for adversarial valuations when $20 / 21 < θ < 1$ , and $\tildeΘ(T^{(2θ+3)/7})$ for correlated i.i.d. valuations when $1 < θ < 9 / 8$ . Finally, as an extension, we study $α$ -regret, with approximation factor $α\ge1$ , for adversarial valuations against the best feasible distribution over price pairs, and show that the optimal competitive ratio rises from 2 to 3 as interest strengthens.

AI Impact Assessments

(1 model)

Core Contribution

The paper introduces "global budget balance with interest" for online bilateral trade. A platform starting with zero funds earns interest at per-round rate r_T = T^{-θ} on its account, so early profit can fund later subsidies. It then characterizes the minimax regret against the best fixed common price, tight up to polylog factors, for every θ, in two models:

Adversarial valuations: the exponent is 5/7 for θ ≤ 20/21, 3θ/4 for 20/21 < θ < 1, and 3/4 for θ ≥ 1.

Correlated i.i.d. valuations: the exponent is 5/7 for θ ≤ 1, (2θ+3)/7 for 1 < θ < 9/8, and 3/4 for θ ≥ 9/8.

Two structural findings stand out. First, interest generated by the platform's own earnings can match the benefit of an external O(T^{6/7}) subsidy (Lunghi et al.), giving Õ(T^{5/7}). Second, stationarity separates the two models, so even weak interest helps the i.i.d. case but not the adversarial one. As an extension, the paper pins down the optimal competitive ratio for α-regret against the best feasible price-pair distribution. It moves from 2 (θ > 1) through about 2.1831 (θ = 1) to 3 (θ < 1), closing the 36/35-to-2 gap left open by Bernasconi et al.

Technical content

Adversarial upper bound. This is largely a clever composition of existing black boxes. A seed profit of 1/T is earned cheaply and compounded for about log T / r_T rounds while GFT-Max runs. The accumulated reserve of size T then pays for Lunghi et al.'s Subsidized-GFT. The analysis is short and correct-looking, but conceptually modest.

Correlated i.i.d. upper bound. This is the substantial algorithmic contribution. It jointly optimizes an earning pair, a subsidy pair, and the switching time under the interest-weighted budget. It uses a new quantity, GFTUB, to build an economical feasible set via adaptive bisection and interval pairing. GFTUB does triple duty: it upper-bounds the gains-from-trade (GFT) of every pair in an interval, it is monotone under bisection, and it is tight to the subsidy-pair GFT. The proofs are long and technical, but they appear carefully constructed.

Lower bounds. These adapt Chen et al.'s Ω(T^{3/4}) construction, whose "global price balance" breaks under discounting. The adversarial case mixes each round with a two-point distribution so that regret scales by (1+r)^{-t}. The i.i.d. case adds negative-GFT points (V_rev) that penalize subsidies by the terminal weight. Both fixes are neat and non-trivial.

α-regret. The lower bound uses a three-phase instance (earn, wait, subsidize). The threshold α* = 2 + (e−1)/(√e+√2)² at θ = 1 arises from a Lagrangian analysis. Upper and lower bounds match.

Rigor

The proofs are detailed and appear internally consistent, with explicit constants and events. The main weakness is that the full set of Appendix and lower-bound lemmas leans heavily on prior papers' lemmas, so correctness hinges on those. The results are purely theoretical, with no experiments, which is fine for this venue. The tightness claims across all θ are a strong, complete result.

Potential Impact

Within the subfield. It gives a clean and complete picture of how budget flexibility trades off against regret, a natural extension in an active line (Bernasconi et al., Lunghi et al., Chen et al., Jin). The full phase diagram, with its odd thresholds 20/21 and 9/8, is a satisfying result. The adversarial-versus-stochastic separation via compound interest is a conceptual insight.

Beyond the subfield. Real-world applicability is limited. The model is stylized: per-round interest rates of T^{-θ} are essentially negligible for realistic horizons, and one-bit feedback with a fixed-price benchmark is a theory construct. The Airbnb and Shopify motivation is rhetorical. Transfer to other online-learning-with-budget-constraint problems (discounted resource constraints) is plausible, but the techniques are specialized.

Reuse. The GFTUB construction and the weighted lower-bound techniques may be reused in follow-up bilateral-trade work.

Timeliness

It fits a hot niche in online learning for economics (EC, COLT, STOC, and NeurIPS communities). It is a natural "next question" after the budget-violation paper, but it is incremental relative to those works. The paper cites 2026 sources and a Nobel, which suggests an unusual timeline but is irrelevant to the assessment.

Strengths

Complete tight characterization across the whole range of θ in two models, plus α-regret.

Non-obvious structural insight (stationarity enables exploiting compounding).

Technical novelty in both the i.i.d. algorithm and the lower-bound adaptations.

Clearly written intuition sections.

Limitations

The interest model is artificial: the threshold regime requires r_T ≥ T^{-20/21}, and the practical relevance of such tiny rates is questionable.

The adversarial upper bound is mostly a composition of existing algorithms.

The proof-heavy presentation is dense, and the exposition relies on cited lemmas.

No empirical validation or practical algorithm.

The audience is narrow (online learning in bilateral trade).

Overall

This is a solid, technically strong theory paper that completes a research thread. It is likely to be cited by the bilateral-trade regret community but unlikely to reach far beyond it.

Rating:6.5/ 10

Significance 5.5Rigor 7.5Novelty 6.5Clarity 6.5

Generated Nov 3, 2026

Comparison History (0)

No comparisons yet.

Scorecard· 16/16

6.5/10 impact

Technically strong, complete tight characterization of a new interest-based budget relaxation, but niche and an incremental extension of a recent line of work.