Regret Minimization in Bilateral Trade With Perturbed Markets
For the problem of maximizing gain from trade in repeated bilateral trade, this work provides the first algorithm that adapts to the level of adversarial corruption, achieving near-optimal regret in both stochastic and adversarial extremes.
The paper studies regret minimization in bilateral trade under perturbed markets, where stochastic distributions are subject to adversarial corruption. The proposed algorithm achieves an adaptive regret bound of O(T^{3/4}) + O(C log T) against the best budget-balanced distribution over prices, bridging the gap between adversarial and stochastic settings.
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 $\tilde{\mathcal{O}}(T^{3/4}) + \mathcal{O}(C\log(T))$ regret bound against the best budget-balanced distribution over prices. Simultaneously, our algorithm maintains the worst-case $\tilde{\mathcal{O}}(T^{3/4})$ regret bound relative to a per-round budget-balanced baseline, ensuring optimality even in fully adversarial environments.