The Competition Complexity of Prophet Inequalities
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910340275503104 |
|---|---|
| author | Brustle, Johannes Correa, José Dütting, Paul Ezra, Tomer Feldman, Michal Verdugo, Victor |
| author_facet | Brustle, Johannes Correa, José Dütting, Paul Ezra, Tomer Feldman, Michal Verdugo, Victor |
| contents | We study the classic single-choice prophet inequality problem through a resource augmentation lens. Our goal is to bound the $(1-\varepsilon)$-competition complexity of different types of online algorithms. This metric asks for the smallest $k$ such that the expected value of the online algorithm on $k$ copies of the original instance, is at least a $(1-\varepsilon)$-approximation to the expected offline optimum on a single copy.
We show that block threshold algorithms, which set one threshold per copy, are optimal and give a tight bound of $k = Θ(\log \log 1/\varepsilon)$. This shows that block threshold algorithms approach the offline optimum doubly-exponentially fast. For single threshold algorithms, we give a tight bound of $k = Θ(\log 1/\varepsilon)$, establishing an exponential gap between block threshold algorithms and single threshold algorithms.
Our model and results pave the way for exploring resource-augmented prophet inequalities in combinatorial settings. In line with this, we present preliminary findings for bipartite matching with one-sided vertex arrivals, as well as in XOS combinatorial auctions. Our results have a natural competition complexity interpretation in mechanism design and pricing applications. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_11084 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The Competition Complexity of Prophet Inequalities Brustle, Johannes Correa, José Dütting, Paul Ezra, Tomer Feldman, Michal Verdugo, Victor Computer Science and Game Theory Data Structures and Algorithms 90C59, 68W27, 62L15, 60G40 We study the classic single-choice prophet inequality problem through a resource augmentation lens. Our goal is to bound the $(1-\varepsilon)$-competition complexity of different types of online algorithms. This metric asks for the smallest $k$ such that the expected value of the online algorithm on $k$ copies of the original instance, is at least a $(1-\varepsilon)$-approximation to the expected offline optimum on a single copy. We show that block threshold algorithms, which set one threshold per copy, are optimal and give a tight bound of $k = Θ(\log \log 1/\varepsilon)$. This shows that block threshold algorithms approach the offline optimum doubly-exponentially fast. For single threshold algorithms, we give a tight bound of $k = Θ(\log 1/\varepsilon)$, establishing an exponential gap between block threshold algorithms and single threshold algorithms. Our model and results pave the way for exploring resource-augmented prophet inequalities in combinatorial settings. In line with this, we present preliminary findings for bipartite matching with one-sided vertex arrivals, as well as in XOS combinatorial auctions. Our results have a natural competition complexity interpretation in mechanism design and pricing applications. |
| title | The Competition Complexity of Prophet Inequalities |
| topic | Computer Science and Game Theory Data Structures and Algorithms 90C59, 68W27, 62L15, 60G40 |
| url | https://arxiv.org/abs/2402.11084 |