Regret Minimization in Bilateral Trade With Perturbed Markets

We address the problem of maximizing Gain from Trade (GFT) in repeated buyer-seller exchanges subject to global budget balance constraints. While this problem is well-understood in purely adversarial and stochastic settings, these environments exhibit a sharp dichotomy: adversarial environments allow for no-regret learning against the best fixed-price mechanism, whereas stochastic environments allow for no-regret learning against the best distribution over prices that is budget balanced in expectation. This gap is significant, as policies balanced in expectation can increase the GFT by a multiplicative factor of two. In this work, we bridge these extremes by studying perturbed markets, where an underlying stochastic distribution is subject to an adversarial corruption C. We design an algorithm that adaptively scales with the level of corruption, achieving an tildeO(T3/4) + O(Clog(T)) regret bound against the best budget-balanced distribution over prices. Simultaneously, our algorithm maintains the worst-case tildeO(T3/4) regret bound relative to a per-round budget-balanced baseline, ensuring optimality even in fully adversarial environments.