Repeated Bilateral Trade Against a Smoothed Adversary
We study repeated bilateral trade where an adaptive $\sigma$-smooth adversary generates the valuations of sellers and buyers. We provide a complete characterization of the regret regimes for fixed-price mechanisms under different feedback models in the two cases where the learner can post either the same or different prices to buyers and sellers. We begin by showing that the minimax regret after $T$ rounds is of order $\sqrt{T}$ in the full-feedback scenario. Under partial feedback, any algorithm that has to post the same price to buyers and sellers suffers worst-case linear regret. However, when the learner can post two different prices at each round, we design an algorithm enjoying regret of order $T^{3/4}$ ignoring log factors. We prove that this rate is optimal by presenting a surprising $T^{3/4}$ lower bound, which is the main technical contribution of the paper.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Profit Maximization in Bilateral Trade against a Smooth Adversary
Bilateral trade models the task of intermediating between two strategic agents, a seller and a buyer, who wish to trade a good. We study this problem from the perspective of a profit-maximizing broker within an online le…
Unifying Bilateral Filtering and Adversarial Training for Robust Neural Networks
Recent analysis of deep neural networks has revealed their vulnerability to carefully structured adversarial examples. Many effective algorithms exist to craft these adversarial examples, but performant defenses seem to …
Near Optimal Adversarial Attacks on Stochastic Bandits and Defenses with Smoothed Responses
I study adversarial attacks against stochastic bandit algorithms. At each round, the learner chooses an arm, and a stochastic reward is generated. The adversary strategically adds corruption to the reward, and the learne…
Adversarial AttackThompson SamplingBilateral Trade Under Heavy-Tailed Valuations: Minimax Regret with Infinite Variance
We study contextual bilateral trade under full feedback when trader valuations have bounded density but infinite variance. We first extend the self-bounding property of Bachoc et al. (ICML 2025) from bounded to real-valu…
Repeated Bilateral Trade: The Quest for Fairness
We study repeated bilateral trade from a fairness perspective. At each round, a fresh seller-buyer pair arrives, and the platform posts a price before observing the traders' valuations. Trade occurs only if both agents a…