Tata Institute of Fundamental Research
Fair and Efficient Allocations under Sub-additive Valuations
STCS Student Seminar
Speaker:
Yeshwant Chandrakant Pandit
Date:
Friday, 24 Feb 2023, 16:00 to 17:00
Venue:
A201
(Scan to add to calendar)
Abstract:
Fair division of a set of resources among several agents is a commonly occurring problem in many real-world settings. In this paper, we will study the problem of allocating a set of indivisible goods among agents with sub-additive valuations in a fair and efficient manner. Envy-Freeness up to any good (EFX) is the most compelling notion of fairness in the context of indivisible goods. Although the existence of EFX is not known beyond the simple case of two agents with sub-additive valuations , some good approximations of EFX are known to exist, namely 1/2-EFX allocation and EFX allocations with bounded charity.
In this talk, we will look at a polynomial time algorithm that outputs an allocation that satisfies either of the two approximations of EFX as well as achieve an O(n) approximation to the Nash welfare
| Speaker: | Yeshwant Chandrakant Pandit |
| Date: | Friday, 24 Feb 2023, 16:00 to 17:00 |
| Venue: | A201 |
(Scan to add to calendar)
Abstract:
Fair division of a set of resources among several agents is a commonly occurring problem in many real-world settings. In this paper, we will study the problem of allocating a set of indivisible goods among agents with sub-additive valuations in a fair and efficient manner. Envy-Freeness up to any good (EFX) is the most compelling notion of fairness in the context of indivisible goods. Although the existence of EFX is not known beyond the simple case of two agents with sub-additive valuations , some good approximations of EFX are known to exist, namely 1/2-EFX allocation and EFX allocations with bounded charity.
In this talk, we will look at a polynomial time algorithm that outputs an allocation that satisfies either of the two approximations of EFX as well as achieve an O(n) approximation to the Nash welfare
In this talk, we will look at a polynomial time algorithm that outputs an allocation that satisfies either of the two approximations of EFX as well as achieve an O(n) approximation to the Nash welfare