I am an Associate Professor in the School of Informatics at the Aristotle University of Thessaloniki and also a Collaborating Senior Researcher at the Archimedes Research Unit. I previously held faculty positions at the University of Liverpool (UK) and University of Saarland (Germany), and a postdoctoral research position at the Max-Planck Institute for Informatics (Germany). In 2015, I was a long-term Visiting Scholar in the Economics and Computation program at the Simons Institute for the Theory of Computing at UC Berkeley, and in 2018 I spent a semester as Visiting Professor at the Athens University of Economics and Business. 

Algorithmic Game Theory, Mechanism Design, Online Algorithms, Approximation Algorithms, Fair Division

On the Nisan-Ronen conjecture

Is VCG the best truthful mechanism for scheduling? 

In the following papers you can find about our recent progress on the famous Nisan-Ronen conjecture.

• A proof of the Nisan-Ronen conjecture. 

George Christodoulou, Elias Koutsoupias, Annamária Kovács. 

STOC 2023

• On the Nisan-Ronen conjecture. 

George Christodoulou, Elias Koutsoupias, Annamária Kovács. 

FOCS 2021

• Truthful Allocation in Graphs and Hypergraphs.

George Christodoulou, Elias Koutsoupias, Annamária Kovács. 

ICALP 2021

• On the Nisan-Ronen conjecture for submodular valuations. 

George Christodoulou, Elias Koutsoupias, Annamária Kovács. 

STOC 2020

Universal TSP on the Grid

 Is there a total ordering over the points of a grid, that can provide a good approximation of the optimal tour, for every subset of points?

 In the following paper we provide a new upper bound, disproving an old conjecture due to Bertsimas and Grigni.

• An Improved Upper Bound for the Universal TSP on the Grid. 

George Christodoulou, Alkmini Sgouritsa.  

SODA 2017

Price of Anarchy in Auctions

 Is it a good idea to sell items via simultaneous second price auctions? 

 The following paper initiated the study of Price of Anarchy in auction settings.

• Bayesian Combinatorial Auctions.

George Christodoulou, Annamaria Kovacs, Michael Schapira.

In Proceedings of Automata, Languages and Programming: 35th International Colloquium ICALP 2008, JACM 2016.

Price of Anarchy of Congestion games and Smoothness

What is the efficiency loss in traffic systems due to drivers' selfishness? 

Our work provided a very simple solution to one of the major open problems for linear congestion games and worked as a precursor to Roughgarden's smoothness framework.

• The Price of Anarchy of Finite Congestion Games. 

George Christodoulou, Elias Koutsoupias.

In Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC 2005) 

•  On the Price of Anarchy and Stability of Correlated Equilibria of Linear Congestion Games.

George Christodoulou, Elias Koutsoupias.

In Proc. of the 13th Annual European Symposium (ESA 2005). 

• A proof of the Nisan-Ronen conjecture. 

George Christodoulou, Elias Koutsoupias, Annamária Kovács. 

STOC 2023

• Truthful Aggregation of Budget Proposals with Proportionality Guarantees. 

Ioannis Caragiannis, George Christodoulou, Nicos Protopapas.

AAAI 2022

• Optimal Deterministic Clock Auctions and Beyond. 

Giorgos Christodoulou, Vasilis Gkatzelis, Daniel Schoepflin. 

ITCS 2022

• On the Nisan-Ronen conjecture. 

George Christodoulou, Elias Koutsoupias, Annamária Kovács. 

FOCS 2021

• Truthful Allocation in Graphs and Hypergraphs.

George Christodoulou, Elias Koutsoupias, Annamária Kovács. 

ICALP 2021

• Existence and Complexity of Approximate Equilibria in Weighted Congestion Games. 

George Christodoulou, Martin Gairing, Yiannis Giannakopoulos, Diogo Poças, Clara Waldmann.

ICALP 2020, MOR 2022

• Resource-Aware Protocols for Network Cost-Sharing Games. 

George Christodoulou, Vasilis Gkatzelis, Mohamad Latifian, Alkmini Sgouritsa.

ACM EC 2020

• On the Nisan-Ronen conjecture for submodular valuations. 

George Christodoulou, Elias Koutsoupias, Annamária Kovács. 

STOC 2020

• Impartial Selection with Additive Approximation Guarantees.

Ioannis Caragiannis, George Christodoulou, Nicos Protopapas.

SAGT 2019, TOCS (Special Issue) 2022

• The Price of Stability of Weighted Congestion Games. 

George Christodoulou, Martin Gairing, Yiannis Giannakopoulos, Paul G. Spirakis. 

ICALP 2018, SICOMP 2019

• An Improved Envy-Free Cake Cutting Protocol for Four Agents. 

Georgios Amanatidis, George Christodoulou, John Fearnley, Evangelos Markakis, Christos-Alexandros Psomas, Eftychia Vakaliou. 

SAGT 2018

• Short Paper: Strategic Contention Resolution in Multiple Channels with Limited Feedback. 

George Christodoulou, Themistoklis Melissourgos, Paul G. Spirakis.

SAGT 2018

• Strategic Contention Resolution in Multiple Channels. 

George Christodoulou, Themistoklis Melissourgos, Paul G. Spirakis
      WAOA 2018

• A 3-Player Protocol Preventing Persistence in Strategic Contention with Limited Feedback.

George Christodoulou, Martin Gairing, Sotiris E. Nikoletseas, Christoforos L. Raptopoulos, Paul G. Spirakis:

SAGT 2017

• Cost-Sharing Methods for Scheduling Games under Uncertainty.

Giorgos Christodoulou, Vasilis Gkatzelis, Alkmini Sgouritsa:
      ACM EC 2017

• Truthful Allocation Mechanisms Without Payments: Characterization and Implications on Fairness.

Georgios Amanatidis, Georgios Birmpas, George Christodoulou, Evangelos Markakis

ACM EC 2017

• An Improved Upper Bound for the Universal TSP on the Grid. 

George Christodoulou, Alkmini Sgouritsa.  

SODA 2017

• Tight Bounds for the Price of Anarchy of Simultaneous First Price Auctions.  

George Christodoulou, Annamária Kovács, Alkmini Sgouritsa, Bo Tang.  

ACM TEAC 2016

• Strategic Contention Resolution with Limited Feedback.

George Christodoulou, Martin Gairing, Sotiris E. Nikoletseas, Christoforos Raptopoulos, Paul G. Spirakis.  

ESA 2016

• Designing Cost-Sharing Methods for Bayesian Games.

George Christodoulou, Stefano Leonardi, Alkmini Sgouritsa.  

SAGT 2016, TOCS (Special Issue) 2019

• Designing Networks with Good Equilibria under Uncertainty.

George Christodoulou, Alkmini Sgouritsa.  

SODA 2016, SICOMP 2019

• On the Efficiency of All-Pay Mechanisms.  

George Christodoulou, Alkmini Sgouritsa, Bo Tang.  

ESA 2015, Algorithmica 2018

• On the Efficiency of the Proportional Allocation Mechanism for Divisible Resources. 

George Christodoulou, Alkmini Sgouritsa, Bo Tang.  

SAGT 2015, TOCS (Special Issue)

• Price of Stability in Polynomial Congestion Games.

George Christodoulou, Martin Gairing.  

ICALP 2013, ACM TEAC 2016

• Mechanisms for Scheduling with Single-Bit Private Values. 

Vincenzo Auletta, George Christodoulou, Paolo Penna.  

SAGT 2012, TOCS 2015 (Special Issue)

• A Global Characterization of Envy-free Truthful Scheduling of Two Tasks. 

George Christodoulou, Annamaria Kovacs.  

WINE 2011

•  Improving the Price of Anarchy for Selfish Routing via Coordination Mechanisms.  

George Christodoulou, Kurt Mehlhorn, Evangelia Pyrga .  

ESA 2011, Algorithmica 2014

• A Truthful Constant Approximation for Maximizing the Minimum Load on Related Machines.

George Christodoulou, Annamaria Kovacs, Rob van Stee.

WINE 2010, TCS 2013

• Truthful Mechanisms for Exhibitions.

George Christodoulou, Khaled Elbassioni, Mahmoud Fouz.

WINE 2010

• Contention Resolution under Selfishness.

George Christodoulou, Katrina Ligett, Evangelia Pyrga.  

ICALP 2010, Algorithmica 2014  

•  A deterministic truthful PTAS for scheduling related machines.

George Christodoulou, Annamaria Kovacs.  

SODA 2010

•  On the Price of Stability for Undirected Network Design.

George Christodoulou, Christine Chung, Katrina Ligett, Evangelia Pyrga, Rob van Stee.  

WAOA 2009

• On the performance of approximate equilibria in congestion games.

George Christodoulou, Elias Koutsoupias, Paul Spirakis.  

In Proc. of the 17th Annual European Symposium (ESA 2009).

•  Mechanism Design for Scheduling.

George Christodoulou, Elias Koutsoupias.  

In Bulletin of the European Association for Theoretical Computer Science (BEATCS), 97:3959, February 2009.

•  A characterization of 2-player mechanisms for scheduling.

George Christodoulou, Elias Koutsoupias, Angelina Vidali.  

In Proc. of the 16th Annual European Symposium (ESA 2008).

• Bayesian Combinatorial Auctions.

George Christodoulou, Annamaria Kovacs, Michael Schapira.

In Proceedings of Automata, Languages and Programming: 35th International Colloquium ICALP 2008, JACM 2016.

• Scheduling selfish tasks: about the performance of truthful algorithms.

George Christodoulou, Laurent Gourves, Fanny Pascual.

In Proceedings of the 13th Annual International Computing and Combinatorics Conference (COCOON 2007).

• Mechanism Design for fractional scheduling on unrelated machines.

George Christodoulou, Elias Koutsoupias, Annamaria Kovacs.

In Proceedings of Automata, Languages and Programming: 34th International Colloquium (ICALP 2007).  

• A lower bound for scheduling mechanisms.

George Christodoulou, Elias Koutsoupias, Angelina Vidali.

In ACM-SIAM Symposium on Discrete Algorithms (SODA 2007).  

• Convergence and Approximation in Potential Games. 

George Christodoulou, Vahab S. Mirrokni, Anastasios Sidiropoulos.

In Proc. of the 23rd Symposium on Theoretical Aspects of Computer Science (STACS 2006).  

• On the Price of Anarchy and Stability of Correlated Equilibria of Linear Congestion Games.

George Christodoulou, Elias Koutsoupias.

In Proc. of the 13th Annual European Symposium (ESA 2005). 

• The Price of Anarchy of Finite Congestion Games. 

George Christodoulou, Elias Koutsoupias.

In Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC 2005)  

• Coordination Mechanisms. 

George Christodoulou, Elias Koutsoupias, Akash Nanavati.

In Proc. of Automata, Languages and Programming: 31st International Colloquium (ICALP 2004).

• On-line Maximum Independent Set in Chordal Graphs. 

George Christodoulou, Vassilis Zissimopoulos.

Journal of Foundations of Computing and Decision Sciences, Vol. 30, No 4, 2005.  

• Crew Assignment by Constraint Logic Programming.

George Christodoulou, Panagiotis Stamatopoulos.

In Proceedings of the 2nd Hellenic Conference on Artificial Intelligence SETN-2002 (Companion Volume)

• Algorithms, Spring 2022