Online Decision Making with Fairness over Time
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2022
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912898152923136 |
|---|---|
| author | Chen, Rui Gunluk, Oktay Lodi, Andrea Wang, Guanyi |
| author_facet | Chen, Rui Gunluk, Oktay Lodi, Andrea Wang, Guanyi |
| contents | Online platforms increasingly rely on sequential decision-making algorithms to allocate resources, match users, or control exposure, while facing growing pressure to ensure fairness over time. We study a general online decision-making framework in which a platform repeatedly makes decisions from possibly non-convex and discrete feasible sets, such as indivisible assignments or assortment choices, to maximize accumulated reward. Importantly, these decisions must jointly satisfy a set of general, $m$-dimensional, potentially unbounded but convex global constraints, which model diverse long-term fairness goals beyond simple budget caps. We develop a primal-dual algorithm that interprets fairness constraints as dynamic prices and updates them online based on observed outcomes. The algorithm is simple to implement, requiring only the solution of perturbed local optimization problems at each decision step. Under the standard random permutation model, we show that our method achieves $\tilde{O}(\sqrt{mT})$ regret in expected reward while guaranteeing $O(\sqrt{mT})$ violation of long-term fairness constraints deterministically over a horizon of $T$ steps. To capture realistic demand patterns such as periodicity or perturbation, we further extend our guarantees to a grouped random permutation model. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2211_03997 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Online Decision Making with Fairness over Time Chen, Rui Gunluk, Oktay Lodi, Andrea Wang, Guanyi Optimization and Control Data Structures and Algorithms Online platforms increasingly rely on sequential decision-making algorithms to allocate resources, match users, or control exposure, while facing growing pressure to ensure fairness over time. We study a general online decision-making framework in which a platform repeatedly makes decisions from possibly non-convex and discrete feasible sets, such as indivisible assignments or assortment choices, to maximize accumulated reward. Importantly, these decisions must jointly satisfy a set of general, $m$-dimensional, potentially unbounded but convex global constraints, which model diverse long-term fairness goals beyond simple budget caps. We develop a primal-dual algorithm that interprets fairness constraints as dynamic prices and updates them online based on observed outcomes. The algorithm is simple to implement, requiring only the solution of perturbed local optimization problems at each decision step. Under the standard random permutation model, we show that our method achieves $\tilde{O}(\sqrt{mT})$ regret in expected reward while guaranteeing $O(\sqrt{mT})$ violation of long-term fairness constraints deterministically over a horizon of $T$ steps. To capture realistic demand patterns such as periodicity or perturbation, we further extend our guarantees to a grouped random permutation model. |
| title | Online Decision Making with Fairness over Time |
| topic | Optimization and Control Data Structures and Algorithms |
| url | https://arxiv.org/abs/2211.03997 |