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
