Alkmini Sgouritsa

AAAI Conference 2026 Conference Paper

EFX Allocation in (Multi)Hypergraphs

• Thanasis Lianeas
• Alkmini Sgouritsa
• Minas Marios Sotiriou

We study fair allocations of indivisible goods among agents with heterogeneous monotone valuations. As fair we consider the allocations that are envy-free-up-to-any-good (EFX). Finding if EFX allocations always exist, even for agents with additive valuations, is a major open problem in Fair Division. 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. We show that for hypergraphs with girth at least 4 and agents with general monotone valuations there always exists an EFX allocation and can be constructed in polynomial time. We generalize our approach to also show that multi-hypergraphs with girth (on the simple hypergraph) at least 4 always admit an EFX allocation, as long as there exists a single vertex whose adjacent edges have multiplicity at most the size of that edge minus 2; our construction in this case needs pseudo-polynomial time.

TCS Journal 2025 Journal Article

Competitive mechanisms for energy-efficient cloud computing

• Antonios Antoniadis
• Andrés Cristi
• Tim Oosterwijk
• Alkmini Sgouritsa

We present a general model for the operation of a cloud computing server comprised of one or more speed-scalable processors. Typically, agents submit tasks to such a cloud computing server in an online fashion, and the server operator has to schedule the tasks and decide on payments without knowledge of tasks arriving in the future. Moreover, the operator should take the different incentives of the agents into account and aim to minimize the energy expenditure. For both the offline and the online setting we provide mechanisms with several desirable properties: The induced game admits a Nash equilibrium, the mechanism is budget balanced, has low communication complexity, is computationally tractable, is intuitive to explain, but above all, has a constant Price of Anarchy. Therefore, the total costs are not too far off from the social optimum. We extend our results to the case of multiple processors and to the Bayesian setting.

AAAI Conference 2025 Conference Paper

EF2X Exists for Four Agents

• Arash Ashuri
• Vasilis Gkatzelis
• Alkmini Sgouritsa

We study the fair allocation of indivisible goods among a group of agents, aiming to limit the envy between any two agents. The central open problem in this literature, which has proven to be extremely challenging, is regarding the existence of an EFX allocation, i.e., an allocation such that any envy from some agent i toward another agent j would vanish if we were to remove any single good from the bundle allocated to j. Prior work has shown that when the agents’ valuations are additive, which has been the main focus of prior works, an EFX allocation is guaranteed to exist for all instances involving up to three agents. Subsequent work extended this guarantee to more general valuations, like nice-cancelable and MMS-feasible. However, the existence of EFX allocations for instances involving four agents remains open, even for additive valuations. We contribute to this literature by focusing on EF2X, a relaxation of EFX which requires that any envy toward some agent would vanish if any two of the goods allocated to that agent were to be removed. Our main result shows that EF2X allocations exist for any instance with four agents, even for the class of cancelable valuations, which is more general than additive. Our proof is constructive, proposing an algorithm that computes such an allocation in pseudo-polynomial time. Furthermore, for instances involving three agents we provide an algorithm that computes an EF2X allocation in polynomial time, in contrast to EFX for which the fastest known algorithm for three agents is only pseudo-polynomial.

AAMAS Conference 2025 Conference Paper

Fairness and Optimality in Routing

• Sreenivas Gollapudi
• Kostas Kollias
• Alkmini Sgouritsa
• Ali Kemal Sinop

We study the existence of almost fair and near-optimal solutions to a routing problem as defined in the seminal work of Rosenthal [41]. We focus on the setting where multiple alternative routes are available for each potential request (which corresponds to a potential user of the network). This model captures a collection of diverse applications such as packet routing in communication networks, routing in road networks with multiple alternative routes, and the economics of transportation of goods. Our proposed centralized routes have provable guarantees in terms of both the total cost and fairness concepts such as approximate envy-freeness. We employ and appropriately combine tools from algorithmic game theory and fair division. Our results apply on two distinct models: the splittable case where the request is split among the selected paths (e. g. , routing a fleet of trucks) and the unsplittable case where the request is assigned to one of its designated paths (e. g. , a single user request). Finally, we conduct an empirical analysis to test the performance of our approach against simpler baselines using the real world road network of New York City.

IJCAI Conference 2025 Conference Paper

Maximin Share Guarantees for Few Agents with Subadditive Valuations

• George Christodoulou
• Vasilis Christoforidis
• Symeon Mastrakoulis
• Alkmini Sgouritsa

We study the problem of fairly allocating a set of indivisible items among a set of agents. We consider the notion of (approximate) maximin share (MMS) and we provide an improved lower bound of 1/2 (which is tight) for the case of subadditive valuations when the number of agents is at most four. We also provide a tight lower bound for the case of multiple agents, when they are equipped with one of two possible types of valuations. Moreover, we propose a new model that extends previously studied models in the area of fair division, which will hopefully give rise to further research. We demonstrate the usefulness of this model by employing it as a technical tool to derive our main result, and we provide a thorough analysis for this model for the case of three agents. Finally, we provide an improved impossibility result for the case of three submodular agents.

AAMAS Conference 2025 Conference Paper

On the Existence of EFX Allocations in Multigraphs

• 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. Christodoulou et al. [19] 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 [19], and for multigraphs for restricted additive valuations [28]. 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 two conditions hold: either (a) each agent has at most ⌈𝑛 4 ⌉ − 1 neighbors, where 𝑛 is the total number of agents, or (b) the shortest cycle with non-parallel edges has length at least 6.

NeurIPS Conference 2024 Conference Paper

Mechanism design augmented with output advice

• George Christodoulou
• Alkmini Sgouritsa
• Ioannis Vlachos

Our work revisits the design of mechanisms via the learning-augmented framework. In this model, the algorithm is enhanced with imperfect (machine-learned) information concerning the input, usually referred to as prediction. The goal is to design algorithms whose performance degrades gently as a function of the prediction error and, in particular, perform well if the prediction is accurate, but also provide a worst-case guarantee under any possible error. This framework has been successfully applied recently to various mechanism design settings, where in most cases the mechanism is provided with a prediction about the types of the players. We adopt a perspective in which the mechanism is provided with an output recommendation. We make no assumptions about the quality of the suggested outcome, and the goal is to use the recommendation to design mechanisms with low approximation guarantees whenever the recommended outcome is reasonable, but at the same time to provide worst-case guarantees whenever the recommendation significantly deviates from the optimal one. We propose a generic, universal measure, which we call quality of recommendation, to evaluate mechanisms across various information settings. We demonstrate how this new metric can provide refined analysis in existing results. This model introduces new challenges, as the mechanism receives limited information comparing to settings that use predictions about the types of the agents. We study, through this lens, several well-studied mechanism design paradigms, devising new mechanisms, but also providing refined analysis for existing ones, using as a metric the quality of recommendation. We complement our positive results, by exploring the limitations of known classes of strategyproof mechanisms that can be devised using output recommendation.

SODA Conference 2020 Conference Paper

A Little Charity Guarantees Almost Envy-Freeness

• Bhaskar Ray Chaudhury
• Telikepalli Kavitha
• Kurt Mehlhorn
• Alkmini Sgouritsa

SODA Conference 2017 Conference Paper

An Improved Upper Bound for the Universal TSP on the Grid

• George Christodoulou 0001
• Alkmini Sgouritsa

We study the universal Traveling Salesman Problem in an n × n grid with the shortest path metric. The goal is to define a (universal) total ordering over the set of grid's vertices, in a way that for any input (subset of vertices), the tour, which visits the points in this ordering, is a good approximation of the optimal tour, i. e. has low competitive ratio. This problem was first studied by Platzman and Bartholdi [26]. They proposed a heuristic, which was based on the Sierpinski space-filling curve, in order to define a universal ordering of the unit square [0, 1] 2 under the Euclidean metric. Their heuristic visits the points of the unit square in the order of their appearance along the space-filling curve. They provided a logarithmic upper bound which was shown to be tight up to a constant by Bertsimas and Grigni [3]. Bertsimas and Grigni further showed logarithmic lower bounds for other space-filling curves and they conjectured that any universal ordering has a logarithmic lower bound for the n × n grid. In this work, we disprove this conjecture by showing that there exists a universal ordering of the n × n grid with competitive ratio of The heuristic we propose defines a universal ordering of the grid's vertices based on a generalization of the Lebesgue space filling curve. In order to analyze the competitive ratio of our heuristic, we employ techniques from the theory of geometric spanners in Euclidean spaces. We finally show that our analysis is tight up to a constant.

SODA Conference 2016 Conference Paper

Designing Networks with Good Equilibria under Uncertainty

• George Christodoulou 0001
• Alkmini Sgouritsa