Matroid Constrained Fair Allocation Problem
Abstract
We consider the problem of allocating a set of indivisible goods among a group of homogeneous agents under matroid constraints and additive valuations, in a fair manner. We propose a novel algorithm that computes a fair allocation for instances with additive and identical valuations, even under matroid constraints. Our result provides a computational anchor to the existential result of the fairness notion, called EF1 (envy-free up to one good) by Biswas and Barman in this setting. We further provide examples to show that the fairness notions stronger than EF1 does not always exist in this setting.
Cite
Text
Biswas and Barman. "Matroid Constrained Fair Allocation Problem." AAAI Conference on Artificial Intelligence, 2019. doi:10.1609/AAAI.V33I01.33019921Markdown
[Biswas and Barman. "Matroid Constrained Fair Allocation Problem." AAAI Conference on Artificial Intelligence, 2019.](https://mlanthology.org/aaai/2019/biswas2019aaai-matroid/) doi:10.1609/AAAI.V33I01.33019921BibTeX
@inproceedings{biswas2019aaai-matroid,
title = {{Matroid Constrained Fair Allocation Problem}},
author = {Biswas, Arpita and Barman, Siddharth},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2019},
pages = {9921-9922},
doi = {10.1609/AAAI.V33I01.33019921},
url = {https://mlanthology.org/aaai/2019/biswas2019aaai-matroid/}
}