Randomized learning-augmented auctions with revenue guarantees
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916104167751680 |
|---|---|
| author | Caragiannis, Ioannis Kalantzis, Georgios |
| author_facet | Caragiannis, Ioannis Kalantzis, Georgios |
| contents | We consider the fundamental problem of designing a truthful single-item auction with the challenging objective of extracting a large fraction of the highest agent valuation as revenue. Following a recent trend in algorithm design, we assume that the agent valuations belong to a known interval, and a (possibly erroneous) prediction for the highest valuation is available. Then, auction design aims for high consistency and robustness, meaning that, for appropriate pairs of values $γ$ and $ρ$, the extracted revenue should be at least a $γ$- or $ρ$-fraction of the highest valuation when the prediction is correct for the input instance or not. We characterize all pairs of parameters $γ$ and $ρ$ so that a randomized $γ$-consistent and $ρ$-robust auction exists. Furthermore, for the setting in which robustness can be a function of the prediction error, we give sufficient and necessary conditions for the existence of robust auctions and present randomized auctions that extract a revenue that is only a polylogarithmic (in terms of the prediction error) factor away from the highest agent valuation. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_13384 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Randomized learning-augmented auctions with revenue guarantees Caragiannis, Ioannis Kalantzis, Georgios Computer Science and Game Theory We consider the fundamental problem of designing a truthful single-item auction with the challenging objective of extracting a large fraction of the highest agent valuation as revenue. Following a recent trend in algorithm design, we assume that the agent valuations belong to a known interval, and a (possibly erroneous) prediction for the highest valuation is available. Then, auction design aims for high consistency and robustness, meaning that, for appropriate pairs of values $γ$ and $ρ$, the extracted revenue should be at least a $γ$- or $ρ$-fraction of the highest valuation when the prediction is correct for the input instance or not. We characterize all pairs of parameters $γ$ and $ρ$ so that a randomized $γ$-consistent and $ρ$-robust auction exists. Furthermore, for the setting in which robustness can be a function of the prediction error, we give sufficient and necessary conditions for the existence of robust auctions and present randomized auctions that extract a revenue that is only a polylogarithmic (in terms of the prediction error) factor away from the highest agent valuation. |
| title | Randomized learning-augmented auctions with revenue guarantees |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2401.13384 |