Logo image
Back
EFx Budget-Feasible Allocations with High NashWelfare
Conference proceeding   Open access   Peer reviewed

EFx Budget-Feasible Allocations with High NashWelfare

Marius Garbea, Vasilis Gkatzelis and Xizhi Tan
26TH EUROPEAN CONFERENCE ON ARTIFICIAL INTELLIGENCE, ECAI 2023, v 372, pp 795-802
01 Jan 2023
DOI: https://doi.org/10.3233/FAIA230346
url
https://doi.org/10.3233/FAIA230346View
Published, Version of Record (VoR) Open

Abstract

Computer Science, Artificial Intelligence Computer Science, Interdisciplinary Applications Computer Science, Theory & Methods Science & Technology Computer Science Technology
We study the problem of allocating indivisible items to budget-constrained agents, aiming to provide fairness and efficiency guarantees. Specifically, our goal is to ensure that the resulting allocation is envy-free up to any item (EFx) while minimizing the amount of inefficiency that this needs to introduce. We first show that there exist two-agent problem instances for which no EFx allocation is Pareto-efficient. We, therefore, turn to approximation and use the (Pareto-efficient) maximum Nash welfare allocation as a benchmark. For two-agent instances, we provide a procedure that always returns an EFx allocation while achieving the best possible approximation of the optimal Nash social welfare that EFx allocations can achieve. For the more complicated case of three-agent instances, we provide a procedure that guarantees EFx, while achieving a constant approximation of the optimal Nash social welfare for any number of items.

Metrics

1 Record Views
3 citations in Web of Science

Details

Logo image