Alkmini Sgouritsa

Ioannis Kakatelis, Thanasis Lianeas, Alkmini Sgouritsa et al.

We study the existence of envy-free-up-to-any-good (EFX) allocations of indivisible goods among agents with heterogeneous monotone valuations. Christodoulou et al. (2023) introduced the (multi-hyper)graph setting, where agents and goods are represented by vertices and edges of a graph respectively, and only the endpoints of an edge may have non-zero marginal value for it. Our work simplifies and extends previous results of Kaviani et al. (Alireza Kaviani, Masoud Seddighin, Amir Mohammad Shahrezaei. Almost Envy-Free Allocation of Indivisible Goods: A Tale of Two Valuations. WINE 2024) in this domain. First, we provide a simpler construction of EF2X allocation for general monotone valuations in hypergraphs with girth at least 3. We extend our ideas when the multiplicity of each edge is 2 and show that an EF3X allocation always exists for additive valuations. Both results can be constructed in polynomial time. Regarding EFX approximations, we provide a simpler construction for $\frac{\sqrt{2}}{2}$-EFX allocations in hypergraphs of girth at least 3 under subadditive valuations. We push the state-of-the-art by establishing the existence of $\frac{2}{3}$-EFX allocations for additive valuations when the edge multiplicity is 2. Both of the latter results can be constructed in pseudo-polynomial time. By addressing these multi-hypergraph settings, our work contributes to the ongoing effort to resolve the existence of EFX in increasingly general and applicable domains.

Alkmini Sgouritsa, Minas Marios Sotiriou

We study the problem of "fairly" dividing indivisible goods to several agents that have valuation set functions over the sets of goods. As fair we consider the allocations that are envy-free up to any good (EFX), 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. [George Christodoulou, Amos Fiat, Elias Koutsoupias, Alkmini Sgouritsa 2023] introduced 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 with general monotone valuations [George Christodoulou, Amos Fiat, Elias Koutsoupias, Alkmini Sgouritsa 2023], and for multigraphs for restricted additive valuations [Alireza Kaviani, Masoud Seddighin, Amir Mohammad Shahrezaei 2024]. In this work, we push the state-of-the-art further, and show that the EFX allocations always exists in multigraphs and general monotone valuations if any of the following three conditions hold: either (a) the multigraph is bipartite, or (b) each agent has at most $\lceil \frac{n}{4} \rceil -1$ neighbors, where $n$ is the total number of agents, or (c) the shortest cycle with non-parallel edges has length at least 6.

Georgios Amanatidis, Aris Filos-Ratsikas, Alkmini Sgouritsa

We study the problem of allocating a set of indivisible goods to a set of agents with additive valuation functions, aiming to achieve approximate envy-freeness up to any good ($α$-EFX). The state-of-the-art results on the problem include that (exact) EFX allocations exist when (a) there are at most three agents, or (b) the agents' valuation functions can take at most two values, or (c) the agents' valuation functions can be represented via a graph. For $α$-EFX, it is known that a $0.618$-EFX allocation exists for any number of agents with additive valuation functions. In this paper, we show that $2/3$-EFX allocations exist when (a) there are at most \emph{seven agents}, (b) the agents' valuation functions can take at most \emph{three values}, or (c) the agents' valuation functions can be represented via a \emph{multigraph}. Our results can be interpreted in two ways. First, by relaxing the notion of EFX to $2/3$-EFX, we obtain existence results for strict generalizations of the settings for which exact EFX allocations are known to exist. Secondly, by imposing restrictions on the setting, we manage to beat the barrier of $0.618$ and achieve an approximation guarantee of $2/3$. Therefore, our results push the \emph{frontier} of existence and computation of approximate EFX allocations, and provide insights into the challenges of settling the existence of exact EFX allocations.