Alkmini Sgouritsa

Personal Info

I am an Assistant Professor at the Athens University of Economics and Business (AUEB), Department of Informatics. I am further a Research Collaborator in Archimedes Unit of the Athena Research Center.

Previously, I was an Assistant Professor at the University of Liverpool, Department of Computer Science. During 2022, I was a Visiting Researcher at Google Research, CA, USA.

During the academic year 2018-2019 I was a PostDoctoral Research at the Max-Planck Institute for Informatics, in Algorithms and Complexity Department.

I completed my PhD in 2017 under the supervision of George Christodoulou at the University of Liverpool, Department of Computer Science. My PhD thesis on Algorithms for Game-Theoretic Environment was the highly-commended runner up for the prestigious British Computer Society (BCS) Distinguished Dissertation award in 2018. It can be found here. 

In parallel, in 2016, I worked as a Lecturer at the University of Liverpool for the MSc module “Algorithmic Game Theory”. 

I hold a master degree in Computer Science (with specialisation in Theoretical Computer Science) from the University of Edinburgh. My MSc thesis on Online Profit-Maximising Sampling Auctions For Digital Goods can be found here. I obtained my Diploma (MSc & BSc) from the School of Electrical and Computer Engineering National Technical University of Athens.

Here is my cv, my dblp page and my google scholar page.

Research Interest

Algorithmic Game Theory, Routing, Online Algorithms, Learning, Fair Division

Selected Scientific Work

• ML predictions in decentralised multi-agent systems

Very recently, the leverage of ML predictions has been adapted in multi-agent systems. Our work in the following paper is one of the first in this area. While other works focus on centralised mechanisms, we are the first to design decentralised protocols under this learning-augmented framework with improved price of anarchy bounds. We do this for two classic decentralised resource allocation problems: scheduling games and network formation games.

Improved Price of Anarchy via Predictions

V. Gkatzelis, K. Kollias, A. Sgouritsa, X. Tan

23rd ACM Conference on Economics and Computations (EC) 2022.

• Resource Aware Cost-Sharing Rules

Agents want to connect their origin and destination on a network and need to share the occurred cost on the edges that are used. How to share those costs affect the choices of the agents and therefore the equilibria. Prior to our work, two models had been considered with respect to the information that the designer of the cost-sharing rule has: he either has full information of the network and demand or is oblivious of both of them. Our work is the first to consider the more realistic scenario where the designer of the cost-sharing rule knows only the network but not the demand. In the following works, we show interesting separations from the other two models. 

Designing Networks with Good Equilibria under Uncertainty

G. Christodoulou, A. Sgouritsa, 

27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) 2016, 

SIAM Journal on Computing (SICOMP) 2019.

Cost-Sharing Methods for Scheduling Games under Uncertainty

G. Christodoulou, V. Gkatzelis, A. Sgouritsa

18th ACM Conference on Economics and Computations (EC) 2017,

Operations Research (OR) 2024.

Resource-Aware Protocols for Network Cost-Sharing Games

G. Christodoulou, V. Gkatzelis, M. Latifian, A. Sgouritsa

21st ACM Conference on Economics and Computations (EC) 2020.

• Fair Division of Indivisible Goods

Arguably, one of the most important open problems in fair division of indivisible goods is the existence of EFX allocation; an allocation satisfies EFX, if no agent envies anybody else after the removal of any good from the latter's set. The state of the art is very poor: an EFX allocation exists a) when all agents have the same valuation function over the sets of goods, b) when there are only two agents, and c) when there are only three agents with additive valuations. Two main relaxations have also been studied: approximate-EFX and EFX with charity (i.e., some goods remain unallocated). 

Our following work lies on the first relaxation where we provide an improved approximation of EFX for several cases, tackling the problem by pushing from several different directions.

Pushing the Frontier on Approximate EFX Allocations

G. Amanatidis, A. Filos-Ratsikas, A. Sgouritsa

25th ACM Conference on Economics and Computations (EC) 2024.

We also had an important contribution regarding the second relaxation in the following work, where we provide an allocation with charity with the main property to be that nobody envies the charity. In other words, we provide an EFX allocation in the case that there exists a "dummy" agent that has zero value for every set of goods. 

A Little Charity Guarantees Almost Envy-Freeness

B.R. Chaudhury, K. Telikepalli, K. Mehlhorn, A. Sgouritsa

31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) 2020, 

SIAM Journal on Computing (SICOMP) 2021.

We further show in the following work how to find an EFX allocation in polynomial time in a restricted setting represented by a graph structure  that indicates which agents are interested in which goods.

Fair Allocation in Graphs

G. Christodoulou, A. Fiat, E. Koutsoupias, A. Sgouritsa

24th ACM Conference on Economics and Computations (EC) 2023.

• Universal TSP on the Grid

A universal algorithm finds a solution  for the universe of input elements and whenever an actual input appears it quickly adjusts the universal solution to the input. In the universal TSP, a global ordering of all possible clients is decided beforehand and when a subset of them requests service, the tour follows this order. In the following work, we disprove an almost 30-year conjecture made by Bertsimas and Grigni 1989, by showing that there exists a universal ordering on the grid with sublogarithmic competitive ratio.

An Improved Upper Bound for the Universal TSP on the Grid 

G. Christodoulou, A. Sgouritsa

28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) 2017,

SIAM Journal on Computing (SICOMP) (to appear).

Publications

Here is a whole list of my publications.

Teaching

Algorithmic Game Theory (MSc)

Game Theory and Decision Making (BSc)

Introduction to Computer Science (BSc)

Previously

Algorithms (BSc)

Database and Information Systems (MSc)

Algorithmic Game Theory  (MSc)

Computational Game Theory and Mechanism Design (BSc)

Current Supervised Students

PhD students

• Ioannis Vlachos (main supervisor), Athens University of Economics and Business

• Vasileios Christoforidis (co-supervisor), Aristotle University of Thessaloniki 

MSc Students

• Konstantinos Kivotos (main supervisor), Athens University of Economics and Business

• Ioannis Mpekiaris  (main supervisor), Athens University of Economics and Business

• Minas-Marios Sotiriou (co-supervisor), ALMA, National and Kapodistrian University of Athens - National Technical University of Athens 

Prior Supervised Students

Here is a list of the projects and students I have supervised.