Matroid Constrained Fair Allocation Problem

Authors

  • Arpita Biswas Indian Institute of Science
  • Siddharth Barman Indian Institute of Science

DOI:

https://doi.org/10.1609/aaai.v33i01.33019921

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.

Downloads

Published

2019-07-17

How to Cite

Biswas, A., & Barman, S. (2019). Matroid Constrained Fair Allocation Problem. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01), 9921-9922. https://doi.org/10.1609/aaai.v33i01.33019921

Issue

Section

Student Abstract Track