Almost Envy-Free allocations in multigraphs

This thesis studies the problem of "fairly" dividing goods in several agents. The study of the problem started in the late 40's for divisible goods with the "cake cutting" prob- lem. There are multiple notions of fairness when referring to the field of Fair Division. One notion is envy-free allocations, where nobody envies what is allocated to any other agent. Envy-freeness has been extensively studied in settings with divisible resources. This thesis focuses on settings with indivisible resources, where envy-freeness cannot be guaranteed. Instead, our focus revolves around a fairness criterion approximating envy-free allocations: that is envy-free up to any good (EFX) allocations, i.e., no agent envies any proper subset of the goods given to any other agent. The existence or not of EFX allocations is a major open problem in Fair Division, and there are only positive results for special cases. Christodoulou et al. 2023 introduced a setting with a restriction on the agents' valuations according to a graph structure: the vertices correspond to agents and the edges to goods, and each vertex/agent has zero marginal value (or in other words, they are indifferent) for the edges/goods that are not adjacent to them. The existence of EFX allocations has been shown for simple graphs when agents have general monotone valuations by Christodoulou et al. 2023, and for multigraphs for restricted additive valuations by Ka- viani et al. 2024. In this thesis, we push the state-of-the-art further, and show that the EFX allocations always exists in multigraphs and for general monotone valuations if any of the follow- ing three conditions hold: either (a) the multigraph is bipartite, or (b) each agent has at most ⌈n/4⌉ − 1 neighbors, where n is the total number of agents, or (c)
the shortest cycle