The Average-Value Allocation Problem
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_ | 1866915483482062848 |
|---|---|
| author | Bhawalkar, Kshipra Feng, Zhe Gupta, Anupam Mehta, Aranyak Wajc, David Wang, Di |
| author_facet | Bhawalkar, Kshipra Feng, Zhe Gupta, Anupam Mehta, Aranyak Wajc, David Wang, Di |
| contents | We initiate the study of centralized algorithms for welfare-maximizing allocation of goods to buyers subject to average-value constraints. We show that this problem is NP-hard to approximate beyond a factor of $\frac{e}{e-1}$, and provide a $\frac{4e}{e-1}$-approximate offline algorithm. For the online setting, we show that no non-trivial approximations are achievable under adversarial arrivals. Under i.i.d. arrivals, we present a polytime online algorithm that provides a constant approximation of the optimal (computationally-unbounded) online algorithm. In contrast, we show that no constant approximation of the ex-post optimum is achievable by an online algorithm. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_10401 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The Average-Value Allocation Problem Bhawalkar, Kshipra Feng, Zhe Gupta, Anupam Mehta, Aranyak Wajc, David Wang, Di Data Structures and Algorithms Computer Science and Game Theory We initiate the study of centralized algorithms for welfare-maximizing allocation of goods to buyers subject to average-value constraints. We show that this problem is NP-hard to approximate beyond a factor of $\frac{e}{e-1}$, and provide a $\frac{4e}{e-1}$-approximate offline algorithm. For the online setting, we show that no non-trivial approximations are achievable under adversarial arrivals. Under i.i.d. arrivals, we present a polytime online algorithm that provides a constant approximation of the optimal (computationally-unbounded) online algorithm. In contrast, we show that no constant approximation of the ex-post optimum is achievable by an online algorithm. |
| title | The Average-Value Allocation Problem |
| topic | Data Structures and Algorithms Computer Science and Game Theory |
| url | https://arxiv.org/abs/2407.10401 |