Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2601.16412 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908783311060992 |
|---|---|
| author | Jin, Yaonan |
| author_facet | Jin, Yaonan |
| contents | 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 thorough understanding of the problem, except for determining the tight regret bound for GBB semi-feedback fixed-price mechanisms under adversarial values.
In this paper, we resolve this open question by devising an $\widetilde{O}(T^{2 / 3})$-regret mechanism, matching the $Ω(T^{2 / 3})$ lower bound from [CJLZ25] up to polylogarithmic factors. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_16412 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Tight Regret Bounds for Bilateral Trade under Semi Feedback Jin, Yaonan Computer Science and Game Theory Machine Learning 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 thorough understanding of the problem, except for determining the tight regret bound for GBB semi-feedback fixed-price mechanisms under adversarial values. In this paper, we resolve this open question by devising an $\widetilde{O}(T^{2 / 3})$-regret mechanism, matching the $Ω(T^{2 / 3})$ lower bound from [CJLZ25] up to polylogarithmic factors. |
| title | Tight Regret Bounds for Bilateral Trade under Semi Feedback |
| topic | Computer Science and Game Theory Machine Learning |
| url | https://arxiv.org/abs/2601.16412 |