EF1 for Mixed Manna with Unequal Entitlements

Document detail

ID

oai:arXiv.org:2410.12966

Topic

Computer Science - Computer Scienc...

Author

Garg, Jugal Sharma, Eklavya

Year

2024

listing date

10/23/2024

Keywords

mixed manna

Metrics

Abstract

We study fair division of indivisible mixed manna when agents have unequal entitlements, with weighted envy-freeness up to one item (WEF1) as our primary notion of fairness.

We identify several shortcomings of existing techniques to achieve WEF1.

Hence, we relax WEF1 to weighted envy-freeness up to 1 transfer (WEF1T), and give a polynomial-time algorithm for achieving it.

We also generalize Fisher markets to the mixed manna setting, and use them to get a polynomial-time algorithm for two agents that outputs a WEF1 allocation.

Garg, Jugal,Sharma, Eklavya, 2024, EF1 for Mixed Manna with Unequal Entitlements