Online Fair Allocation with Best-of-Many-Worlds Guarantees
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_ | 1866916346631028736 |
|---|---|
| author | Yang, Zongjun Liao, Luofeng Gao, Yuan Kroer, Christian |
| author_facet | Yang, Zongjun Liao, Luofeng Gao, Yuan Kroer, Christian |
| contents | We investigate the online fair allocation problem with sequentially arriving items under various input models, with the goal of balancing fairness and efficiency. We propose the unconstrained PACE (Pacing According to Current Estimated utility) algorithm, a parameter-free allocation dynamic that requires no prior knowledge of the input while using only integral allocations. PACE attains near-optimal convergence or approximation guarantees under stationary, stochastic-but-nonstationary, and adversarial input types, thereby achieving the first best-of-many-worlds guarantee in online fair allocation. Beyond theoretical bounds, PACE is highly simple, efficient, and decentralized, and is thus likely to perform well on a broad range of real-world inputs. Numerical results support the conclusion that PACE works well under a variety of input models. We find that PACE performs very well on two real-world datasets even under the true temporal arrivals in the data, which are highly nonstationary. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_02403 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Online Fair Allocation with Best-of-Many-Worlds Guarantees Yang, Zongjun Liao, Luofeng Gao, Yuan Kroer, Christian Computer Science and Game Theory Data Structures and Algorithms Optimization and Control We investigate the online fair allocation problem with sequentially arriving items under various input models, with the goal of balancing fairness and efficiency. We propose the unconstrained PACE (Pacing According to Current Estimated utility) algorithm, a parameter-free allocation dynamic that requires no prior knowledge of the input while using only integral allocations. PACE attains near-optimal convergence or approximation guarantees under stationary, stochastic-but-nonstationary, and adversarial input types, thereby achieving the first best-of-many-worlds guarantee in online fair allocation. Beyond theoretical bounds, PACE is highly simple, efficient, and decentralized, and is thus likely to perform well on a broad range of real-world inputs. Numerical results support the conclusion that PACE works well under a variety of input models. We find that PACE performs very well on two real-world datasets even under the true temporal arrivals in the data, which are highly nonstationary. |
| title | Online Fair Allocation with Best-of-Many-Worlds Guarantees |
| topic | Computer Science and Game Theory Data Structures and Algorithms Optimization and Control |
| url | https://arxiv.org/abs/2408.02403 |