Repeated Bilateral Trade Against a Smoothed Adversary
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909111170367488 |
|---|---|
| author | Cesa-Bianchi, Nicolò Cesari, Tommaso Colomboni, Roberto Fusco, Federico Leonardi, Stefano |
| author_facet | Cesa-Bianchi, Nicolò Cesari, Tommaso Colomboni, Roberto Fusco, Federico Leonardi, Stefano |
| contents | We study repeated bilateral trade where an adaptive $σ$-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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2302_10805 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Repeated Bilateral Trade Against a Smoothed Adversary Cesa-Bianchi, Nicolò Cesari, Tommaso Colomboni, Roberto Fusco, Federico Leonardi, Stefano Machine Learning Data Structures and Algorithms Computer Science and Game Theory We study repeated bilateral trade where an adaptive $σ$-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. |
| title | Repeated Bilateral Trade Against a Smoothed Adversary |
| topic | Machine Learning Data Structures and Algorithms Computer Science and Game Theory |
| url | https://arxiv.org/abs/2302.10805 |