Achieving a Fairer Future by Changing the past

Jiafan He, Ariel D. Procaccia, Alexandros Psomas, David Zeng

IJCAI 2019 pp. 343-349

doi:10.24963/IJCAI.2019/49 /ijcai/2019/he2019ijcai-achieving/

Abstract

We study the problem of allocating T indivisible items that arrive online to agents with additive valuations. The allocation must satisfy a prominent fairness notion, envy-freeness up to one item (EF1), at each round. To make this possible, we allow the reallocation of previously allocated items, but aim to minimize these so-called adjustments. For the case of two agents, we show that algorithms that are informed about the values of future items can get by without any adjustments, whereas uninformed algorithms require Theta(T) adjustments. For the general case of three or more agents, we prove that even informed algorithms must use Omega(T) adjustments, and design an uninformed algorithm that requires only O(T^(3/2)).

PDF IJCAI Semantic Scholar

Cite

Text

He et al. "Achieving a Fairer Future by Changing the past." International Joint Conference on Artificial Intelligence, 2019. doi:10.24963/IJCAI.2019/49

Markdown

[He et al. "Achieving a Fairer Future by Changing the past." International Joint Conference on Artificial Intelligence, 2019.](https://mlanthology.org/ijcai/2019/he2019ijcai-achieving/) doi:10.24963/IJCAI.2019/49

BibTeX

@inproceedings{he2019ijcai-achieving,
  title     = {{Achieving a Fairer Future by Changing the past}},
  author    = {He, Jiafan and Procaccia, Ariel D. and Psomas, Alexandros and Zeng, David},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {2019},
  pages     = {343-349},
  doi       = {10.24963/IJCAI.2019/49},
  url       = {https://mlanthology.org/ijcai/2019/he2019ijcai-achieving/}
}