Subgame Optimal and Prior-Independent Online Algorithms
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916160466845696 |
|---|---|
| author | Hartline, Jason Johnsen, Aleck Shah, Anant |
| author_facet | Hartline, Jason Johnsen, Aleck Shah, Anant |
| contents | This paper takes a game theoretic approach to the design and analysis of online algorithms and illustrates the approach on the finite-horizon ski-rental problem. This approach allows beyond worst-case analysis of online algorithms. First, we define "subgame optimality" which is stronger than worst case optimality in that it requires the algorithm to take advantage of an adversary not playing a worst case input. Algorithms only focusing on the worst case can be far from subgame optimal. Second, we consider prior-independent design and analysis of online algorithms, where rather than choosing a worst case input, the adversary chooses a worst case independent and identical distribution over inputs. Prior-independent online algorithms are generally analytically intractable; instead we give a fully polynomial time approximation scheme to compute them. Highlighting the potential improvement from these paradigms for the finite-horizon ski-rental problem, we empirically compare worst-case, subgame optimal, and prior-independent algorithms in the prior-independent framework. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_10451 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Subgame Optimal and Prior-Independent Online Algorithms Hartline, Jason Johnsen, Aleck Shah, Anant Computer Science and Game Theory This paper takes a game theoretic approach to the design and analysis of online algorithms and illustrates the approach on the finite-horizon ski-rental problem. This approach allows beyond worst-case analysis of online algorithms. First, we define "subgame optimality" which is stronger than worst case optimality in that it requires the algorithm to take advantage of an adversary not playing a worst case input. Algorithms only focusing on the worst case can be far from subgame optimal. Second, we consider prior-independent design and analysis of online algorithms, where rather than choosing a worst case input, the adversary chooses a worst case independent and identical distribution over inputs. Prior-independent online algorithms are generally analytically intractable; instead we give a fully polynomial time approximation scheme to compute them. Highlighting the potential improvement from these paradigms for the finite-horizon ski-rental problem, we empirically compare worst-case, subgame optimal, and prior-independent algorithms in the prior-independent framework. |
| title | Subgame Optimal and Prior-Independent Online Algorithms |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2403.10451 |