Bilateral Trade: A Regret Minimization Perspective
Bilateral trade, a fundamental topic in economics, models the problem of intermediating between two strategic agents, a seller and a buyer, willing to trade a good for which they hold private valuations. In this paper, we cast the bilateral trade problem in a regret minimization framework over $T$ rounds of seller/buyer interactions, with no prior knowledge on their private valuations. Our main contribution is a complete characterization of the regret regimes for fixed-price mechanisms with different feedback models and private valuations, using as a benchmark the best fixed-price in hindsight. More precisely, we prove the following tight bounds on the regret: - $\Theta(\sqrt{T})$ for full-feedback (i.e., direct revelation mechanisms). - $\Theta(T^{2/3})$ for realistic feedback (i.e., posted-price mechanisms) and independent seller/buyer valuations with bounded densities. - $\Theta(T)$ for realistic feedback and seller/buyer valuations with bounded densities. - $\Theta(T)$ for realistic feedback and independent seller/buyer valuations. - $\Theta(T)$ for the adversarial setting.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Tight Regret Bounds for Bilateral Trade under Semi Feedback
The study of \textit{regret minimization in fixed-price bilateral trade} has received considerable attention in recent research. Previous works [CCC+24a, CCC+24b, AFF24, BCCF24, CJLZ25, LCM25a, GDFS25] have acquired a th…
Nearly Tight Regret Bounds for Profit Maximization in Bilateral Trade
Bilateral trade models the task of intermediating between two strategic agents, a seller and a buyer, willing to trade a good for which they hold private valuations. We study this problem from the perspective of a broker…
Tight Regret Bounds for Fixed-Price Bilateral Trade
We examine fixed-price mechanisms in bilateral trade through the lens of regret minimization. Our main results are twofold. (i) For independent values, a near-optimal $\widetilde{\Theta}(T^{2/3})$ tight bound for $\texts…
Breaking the $T^{3/4}$ Barrier for Regret Minimization With Bi-Dimensional CDFs
We study regret minimization for learning CDF-related objectives of the form \[ g(x)\cdot\mathbb{P}_{X\sim\mathcal{D}}(X\le x), \] over $[0,1]^2$, where $g$ is a known Lipschitz function and $\mathcal{D}$ is an unknown d…
Fair Online Bilateral Trade
In online bilateral trade, a platform posts prices to incoming pairs of buyers and sellers that have private valuations for a certain good. If the price is lower than the buyers' valuation and higher than the sellers' va…
Fairness