We consider the problem of dividing indivisible resources among a set of agents ``fairly''. Our underlying fairness notion is envy-freeness up to any good (EFX), where no agent envies another following the removal of any single good from the other's bundle. Despite substantial effort from the community, the existence of EFX allocations has not been settled. In this talk, we elaborate the proof of existence of certain relaxations of EFX allocations and the existence of EFX allocations when there are only three agents. In the end, we also reduce the problem of finding improved relaxations of EFX allocations to a problem in extremal graph theory.
