Publications
2023
Existence and Complexity of Approximate Equilibria in Weighted Congestion Games
Christodoulou, G., Gairing, M., Giannakopoulos, Y., Pocas, D., & Waldmann, C. (2022). Existence and Complexity of Approximate Equilibria in Weighted Congestion Games. In MATHEMATICS OF OPERATIONS RESEARCH. doi:10.1287/moor.2022.1272
2022
On the Nisan-Ronen conjecture
Christodoulou, G., Koutsoupias, E., & Kovacs, A. (2022). On the Nisan-Ronen conjecture. In 2021 IEEE 62ND ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2021) (pp. 839-850). doi:10.1109/FOCS52979.2021.00086
Optimal Deterministic Clock Auctions and Beyond
Christodoulou, G., Gkatzelis, V., & Schoepflin, D. (2022). Optimal Deterministic Clock Auctions and Beyond. In Leibniz International Proceedings in Informatics Lipics Vol. 215. doi:10.4230/LIPIcs.ITCS.2022.49
2021
Truthful allocation in graphs and hypergraphs
Christodoulou, G., Koutsoupias, E., & Kovács, A. (2021). Truthful allocation in graphs and hypergraphs. In Leibniz International Proceedings in Informatics Lipics Vol. 198. doi:10.4230/LIPIcs.ICALP.2021.56
Introduction to the Special Issue on WINE'18: Part 1
Christodoulou, G., & Harks, T. (2021). Introduction to the Special Issue on WINE'18: Part 1. ACM TRANSACTIONS ON ECONOMICS AND COMPUTATION, 9(1). doi:10.1145/3447510
2020
Resource-Aware Protocols for Network Cost-Sharing Games
Christodoulou, G., Gkatzelis, V., Latifian, M., & Sgouritsa, A. (2020). Resource-Aware Protocols for Network Cost-Sharing Games. Retrieved from http://dx.doi.org/10.1145/3391403.3399528
Resource-Aware Protocols for Network Cost-Sharing Games.
Christodoulou, G., Gkatzelis, V., Latifian, M., & Sgouritsa, A. (2020). Resource-Aware Protocols for Network Cost-Sharing Games.. CoRR. doi:10.1145/3391403.3399528
On the Nisan-Ronen conjecture for submodular valuations
Christodoulou, G., Koutsoupias, E., & Kovacs, A. (2020). On the Nisan-Ronen conjecture for submodular valuations. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2020) (pp. 1086-1096). New York, NY, USA: Accoiation for Computing Machinery. doi:10.1145/3357713.3384299
Existence and Complexity of Approximate Equilibria in Weighted Congestion Games
Christodoulou, G., Gairing, M., Giannakopoulos, Y., Poças, D., & Waldmann, C. (2020). Existence and Complexity of Approximate Equilibria in Weighted Congestion Games. Retrieved from http://arxiv.org/abs/2002.07466v3
2019
Impartial Selection with Additive Approximation Guarantees
Caragiannis, I., Christodoulou, G., & Protopapas, N. (2019). Impartial Selection with Additive Approximation Guarantees. In ALGORITHMIC GAME THEORY (SAGT 2019) Vol. 11801 (pp. 269-283). doi:10.1007/978-3-030-30473-7_18
Designing Networks with Good Equilibria under Uncertainty
Christodoulou, G., & Sgouritsa, A. (2019). Designing Networks with Good Equilibria under Uncertainty. SIAM Journal on Computing, 48(4), 1364-1396. doi:10.1137/16M1096694
The Price of Stability of Weighted Congestion Games
Christodoulou, G., Gairing, M., Giannakopoulos, Y., & Spirakis, P. G. (2019). The Price of Stability of Weighted Congestion Games. SIAM Journal on Computing, 48(5), 1544-1582. doi:10.1137/18M1207880
2018
Strategic Contention Resolution in Multiple Channels
Christodoulou, G., Melissourgos, T., & Spirakis, P. G. (2018). Strategic Contention Resolution in Multiple Channels. In APPROXIMATION AND ONLINE ALGORITHMS (WAOA 2018) Vol. 11312 (pp. 165-180). doi:10.1007/978-3-030-04693-4_11
An Improved Envy-Free Cake Cutting Protocol for Four Agents
Amanatidis, G., Christodoulou, G., Fearnley, J., Markakis, E., Psomas, C. -A., & Vakaliou, E. (2018). An Improved Envy-Free Cake Cutting Protocol for Four Agents. In Lecture Notes in Computer Science. Beijing, China: Springer Nature. doi:10.1007/978-3-319-99660-8_9
The Price of Stability of Weighted Congestion Games
Christodoulou, G., Gairing, M., Giannakopoulos, Y., & Spirakis, P. G. (2018). The Price of Stability of Weighted Congestion Games. In LIPIcs : Leibniz International Proceedings in Informatics Vol. 107 (pp. 150:1-150:16). Prague: Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik. doi:10.4230/LIPIcs.ICALP.2018.150
On the Efficiency of All-Pay Mechanisms
Christodoulou, G., Sgouritsa, A., & Tang, B. (2018). On the Efficiency of All-Pay Mechanisms. ALGORITHMICA, 80(4), 1115-1145. doi:10.1007/s00453-017-0296-2
An Improved Envy-Free Cake Cutting Protocol for Four Agents.
Amanatidis, G., Christodoulou, G., Fearnley, J., Markakis, E., Psomas, C. -A., & Vakaliou, E. (2018). An Improved Envy-Free Cake Cutting Protocol for Four Agents.. In X. Deng (Ed.), SAGT Vol. 11059 (pp. 87-99). Springer. Retrieved from https://doi.org/10.1007/978-3-319-99660-8
Preface
Christodoulou, G., & Harks, T. (2018). Preface (Vol. 11316 LNCS).
Short Paper: Strategic Contention Resolution in Multiple Channels with Limited Feedback
Christodoulou, G., Melissourgos, T., & Spirakis, P. G. (2018). Short Paper: Strategic Contention Resolution in Multiple Channels with Limited Feedback. In Unknown Conference (pp. 245-250). Springer International Publishing. doi:10.1007/978-3-319-99660-8_22
Strategic Contention Resolution in Multiple Channels.
Christodoulou, G., Melissourgos, T., & Spirakis, P. G. (2018). Strategic Contention Resolution in Multiple Channels.. CoRR, abs/1810.04565.
2017
A 3-player protocol preventing persistence in strategic contention with limited feedback
Spirakis, P. G., Christodoulou, G., Gairing, M., Nikoletseas, S., & Raptopoulos, C. (2017). A 3-player protocol preventing persistence in strategic contention with limited feedback. In LNCS ARCoSS. L'Acquilla Iatly.
Cost-sharing methods for scheduling games under uncertainty
Christodoulou, G., Sgouritsa, A., & Gkatzelis, V. (2017). Cost-Sharing Methods for Scheduling Games under Uncertainty. In EC '17: Proceedings of the 2017 ACM Conference on Economics and Computation (pp. 441-458).
Truthful Allocation Mechanisms Without Payments: Characterization and Implications on Fairness
Amanatidis, G., Birmpas, G., Christodoulou, G., & Markakis, E. (2017). Truthful Allocation Mechanisms Without Payments: Characterization and Implications on Fairness. In EC'17: PROCEEDINGS OF THE 2017 ACM CONFERENCE ON ECONOMICS AND COMPUTATION (pp. 545-562). doi:10.1145/3033274.3085147
A 3-Player Protocol Preventing Persistence in Strategic Contention with Limited Feedback.
Christodoulou, G., Gairing, M., Nikoletseas, S. E., Raptopoulos, C. L., & Spirakis, P. G. (2017). A 3-Player Protocol Preventing Persistence in Strategic Contention with Limited Feedback.. In V. Bilò, & M. Flammini (Eds.), SAGT Vol. 10504 (pp. 240-251). Springer. Retrieved from https://doi.org/10.1007/978-3-319-66700-3
An improved upper bound for the universal TSP on the grid
Christodoulou, G., & Sgouritsa, A. (2017). An Improved Upper Bound for the Universal TSP on the Grid. In Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017 (pp. 1006). Barcelona.
2016
On the Efficiency of the Proportional Allocation Mechanism for Divisible Resources
Christodoulou, G., Sgouritsa, A., & Tang, B. (2016). On the Efficiency of the Proportional Allocation Mechanism for Divisible Resources. THEORY OF COMPUTING SYSTEMS, 59(4), 600-618. doi:10.1007/s00224-016-9701-5
Strategic Contention Resolution with Limited Feedback
Christodoulou, G., Gairing, M., Nikoletseas, S., Raptopoulos, C., & Spirakis, P. G. (2016). Strategic Contention Resolution with Limited Feedback. In Leibniz International Proceedings in Informatics (LIPIcs) Vol. 57 (pp. 30:1-30:16). Aarhus , Denmark. doi:10.4230/LIPIcs.ESA.2016.30
Bayesian Combinatorial Auctions
Christodoulou, G., Kovacs, A., & Schapira, M. (2016). Bayesian Combinatorial Auctions. JOURNAL OF THE ACM, 63(2). doi:10.1145/2835172
Price of Stability in Polynomial Congestion Games
Christodoulou, G., & Gairing, M. (2016). Price of Stability in Polynomial Congestion Games. ACM Transactions on Economics and Computation, 4(2), 1-17. doi:10.1145/2841229
Designing Cost-Sharing Methods for Bayesian Games
Christodoulou, G., Leonardi, S., & Sgouritsa, A. (2016). Designing Cost-Sharing Methods for Bayesian Games. In ALGORITHMIC GAME THEORY, SAGT 2016 Vol. 9928 (pp. 327-339). doi:10.1007/978-3-662-53354-3_26
Strategic Contention Resolution with Limited Feedback.
Christodoulou, G., Gairing, M., Nikoletseas, S. E., Raptopoulos, C. L., & Spirakis, P. G. (2016). Strategic Contention Resolution with Limited Feedback.. In P. Sankowski, & C. D. Zaroliagis (Eds.), ESA Vol. 57 (pp. 30:1). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. Retrieved from http://drops.dagstuhl.de/opus/portals/lipics/index.php?semnr=16013
2015
Mechanisms for Scheduling with Single-Bit Private Values
Auletta, V., Christodoulou, G., & Penna, P. (2015). Mechanisms for Scheduling with Single-Bit Private Values. THEORY OF COMPUTING SYSTEMS, 57(3), 523-548. doi:10.1007/s00224-015-9625-5
On the Efficiency of All-Pay Mechanisms
Christodoulou, G., Sgouritsa, A., & Tang, B. (2015). On the Efficiency of All-Pay Mechanisms. In ALGORITHMS - ESA 2015 Vol. 9294 (pp. 349-360). doi:10.1007/978-3-662-48350-3_30
On the Efficiency of the Proportional Allocation Mechanism for Divisible Resources
Christodoulou, G., Sgouritsa, A., & Tang, B. (2015). On the Efficiency of the Proportional Allocation Mechanism for Divisible Resources. ALGORITHMIC GAME THEORY, SAGT 2015, 9347, 165-177. doi:10.1007/978-3-662-48433-3_13
Designing Networks with Good Equilibria under Uncertainty
Christodoulou, G., & Sgouritsa, A. (2015). Designing Networks with Good Equilibria under Uncertainty. Retrieved from http://arxiv.org/abs/1503.03392v2
Social Welfare in One-Sided Matching Mechanisms
Christodoulou, G., Filos-Ratsikas, A., Stiil, S. K., Goldberg, P. W., Zhang, J., & Zhang, J. (2016). Social Welfare in One-Sided Matching Mechanisms. In AAMAS'16: PROCEEDINGS OF THE 2016 INTERNATIONAL CONFERENCE ON AUTONOMOUS AGENTS & MULTIAGENT SYSTEMS (pp. 1297-1298). Retrieved from https://www.webofscience.com/
On the Efficiency of the Proportional Allocation Mechanism for Divisible Resources.
Christodoulou, G., Sgouritsa, A., & Tang, B. (2015). On the Efficiency of the Proportional Allocation Mechanism for Divisible Resources.. In M. Hoefer (Ed.), SAGT Vol. 9347 (pp. 165-177). Springer. Retrieved from https://doi.org/10.1007/978-3-662-48433-3
Universal Network Cost-Sharing Design.
Christodoulou, G., & Sgouritsa, A. (2015). Universal Network Cost-Sharing Design.. CoRR, abs/1503.03392.
2014
Contention Resolution under Selfishness
Christodoulou, G., Ligett, K., & Pyrga, E. (2014). Contention Resolution under Selfishness. ALGORITHMICA, 70(4), 675-693. doi:10.1007/s00453-013-9773-4
Improving the Price of Anarchy for Selfish Routing via Coordination Mechanisms
Christodoulou, G., Mehlhorn, K., & Pyrga, E. (2014). Improving the Price of Anarchy for Selfish Routing via Coordination Mechanisms. ALGORITHMICA, 69(3), 619-640. doi:10.1007/s00453-013-9753-8
2013
Tight Bounds for the Price of Anarchy of Simultaneous First Price Auctions.
Christodoulou, G., Kovacs, A., Sgouritsa, A., & Tang, B. (2016). Tight Bounds for the Price of Anarchy of Simultaneous First Price Auctions.. ACM Transactions on Economics and Computation, 4(2). doi:10.1145/2847520
Price of Stability in Polynomial Congestion Games
Christodoulou, G., & Gairing, M. (2013). Price of Stability in Polynomial Congestion Games. In AUTOMATA, LANGUAGES, AND PROGRAMMING, PT II Vol. 7966 (pp. 496-507). Retrieved from https://www.webofscience.com/
A Deterministic Truthful PTAS for Scheduling Related Machines.
Christodoulou, G., & Kovács, A. R. (2013). A Deterministic Truthful PTAS for Scheduling Related Machines.. SIAM Journal on Computing., 42(4), 1572-1595.
A truthful constant approximation for maximizing the minimum load on related machines.
Christodoulou, G., Kovács, A. R., & van Stee, R. (2013). A truthful constant approximation for maximizing the minimum load on related machines.. Theoretical Computer Science, 489-49, 88-98.
2012
Convergence and approximation in potential games
Christodoulou, G., Mirrokni, V. S., & Sidiropoulos, A. (2012). Convergence and approximation in potential games. Theoretical Computer Science, 438, 13-27. doi:10.1016/j.tcs.2012.02.033
Mechanisms for Scheduling with Single-Bit Private Values.
Auletta, V., Christodoulou, G., & Penna, P. (2012). Mechanisms for Scheduling with Single-Bit Private Values.. In SAGT (pp. 25-36). Barcelona: Springer.
2011
On the Performance of Approximate Equilibria in Congestion Games
Christodoulou, G., Koutsoupias, E., & Spirakis, P. G. (2011). On the Performance of Approximate Equilibria in Congestion Games. Algorithmica, 61(1), 116-140. doi:10.1007/s00453-010-9449-2
A Global Characterization of Envy-Free Truthful Scheduling of Two Tasks.
Christodoulou, G., & Kovács, A. R. (2011). A Global Characterization of Envy-Free Truthful Scheduling of Two Tasks.. In WINE (pp. 84-96). Singapore: Springer.
Improving the Price of Anarchy for Selfish Routing via Coordination Mechanisms
Christodoulou, G., Mehlhorn, K., & Pyrga, E. (2011). Improving the Price of Anarchy for Selfish Routing via Coordination Mechanisms. In Unknown Conference (pp. 119-130). Springer Berlin Heidelberg. doi:10.1007/978-3-642-23719-5_11
2010
Mechanism design for fractional scheduling on unrelated machines
Christodoulou, G., Koutsoupias, E., & Kovács, A. (2010). Mechanism design for fractional scheduling on unrelated machines. ACM Transactions on Algorithms, 6(2), 1-18. doi:10.1145/1721837.1721854
A Deterministic Truthful PTAS for Scheduling Related Machines
Christodoulou, G., & Kovacs, A. (2010). A Deterministic Truthful PTAS for Scheduling Related Machines. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 1005-1016). Austin, Texas, USA, January. Retrieved from http://www.siam.org/proceedings/soda/2010/SODA10_081_christodouloug.pdf
A Truthful Constant Approximation for Maximizing the Minimum Load on Related Machines.
Christodoulou, G., Kovács, A. R., & van Stee, R. (2010). A Truthful Constant Approximation for Maximizing the Minimum Load on Related Machines.. In WINE (pp. 182-193). Stanford: Springer.
Contention Resolution under Selfishness
Christodoulou, G., Ligett, K., & Pyrga, E. (2010). Contention Resolution under Selfishness. In Unknown Conference (pp. 430-441). Springer Berlin Heidelberg. doi:10.1007/978-3-642-14162-1_36
Truthful Mechanisms for Exhibitions.
Christodoulou, G., Elbassioni, K. M., & Fouz, M. (2010). Truthful Mechanisms for Exhibitions.. In WINE (pp. 170-181). Stanford: Springer.
2009
A Lower Bound for Scheduling Mechanisms
Christodoulou, G., Koutsoupias, E., & Vidali, A. (2009). A Lower Bound for Scheduling Mechanisms. Algorithmica, 55(4), 729-740. doi:10.1007/s00453-008-9165-3
On the Performance of Approximate Equilibria in Congestion Games
Christodoulou, G., Koutsoupias, E., & Spirakis, P. G. (2009). On the Performance of Approximate Equilibria in Congestion Games. In Unknown Conference (pp. 251-262). Springer Berlin Heidelberg. doi:10.1007/978-3-642-04128-0_22
Coordination mechanisms
Christodoulou, G., Koutsoupias, E., & Nanavati, A. (2009). Coordination mechanisms. Theoretical Computer Science, 410(36), 3327-3336. doi:10.1016/j.tcs.2009.01.005
Mechanism Design for Scheduling.
Christodoulou, G., & Koutsoupias, E. (2009). Mechanism Design for Scheduling.. Bulletin of the EATCS, 97, 40-59.
On the Price of Stability for Undirected Network Design.
Christodoulou, G., Chung, C., Ligett, K., Pyrga, E., & van Stee, R. (2009). On the Price of Stability for Undirected Network Design.. In WAOA (pp. 86-97). Copenhagen: Springer.
2008
A Characterization of 2-Player Mechanisms for Scheduling
Christodoulou, G., Koutsoupias, E., & Vidali, A. (2008). A Characterization of 2-Player Mechanisms for Scheduling. In Unknown Conference (pp. 297-307). Springer Berlin Heidelberg. doi:10.1007/978-3-540-87744-8_25
Bayesian Combinatorial Auctions
Christodoulou, G., Kovács, A., & Schapira, M. (2008). Bayesian Combinatorial Auctions. In Unknown Conference (pp. 820-832). Springer Berlin Heidelberg. doi:10.1007/978-3-540-70575-8_67
Price of Anarchy.
Christodoulou, G. (2008). Price of Anarchy.. In M. -Y. Kao (Ed.), Encyclopedia of Algorithms (pp. Not available). N/A: Springer.
2007
A lower bound for scheduling mechanisms.
Christodoulou, G., Koutsoupias, E., & Vidali, A. (2007). A lower bound for scheduling mechanisms.. In SODA (pp. 1163-1170). New Orleans,: SIAM.
Mechanism Design for Fractional Scheduling on Unrelated Machines.
Christodoulou, G., Koutsoupias, E., & Kovács, A. R. (2007). Mechanism Design for Fractional Scheduling on Unrelated Machines.. In ICALP (pp. 40-52). Wroclaw: Springer.
Scheduling Selfish Tasks: About the Performance of Truthful Algorithms.
Christodoulou, G., Gourvès, L., & Pascual, F. (2007). Scheduling Selfish Tasks: About the Performance of Truthful Algorithms.. In COCOON (pp. 187-197). Banff: Springer.
2006
Convergence and Approximation in Potential Games.
Christodoulou, G., Mirrokni, V. S., & Sidiropoulos, A. (2006). Convergence and Approximation in Potential Games.. In B. Durand, & W. Thomas (Eds.), STACS (pp. 349-360). Marseille: Springer.
2005
On the Price of Anarchy and Stability of Correlated Equilibria of Linear Congestion Games.
Christodoulou, G., & Koutsoupias, E. (2005). On the Price of Anarchy and Stability of Correlated Equilibria of Linear Congestion Games.. In ESA (pp. 59-70). Palma de Mallorca: Springer.
The price of anarchy of finite congestion games.
Christodoulou, G., & Koutsoupias, E. (2005). The price of anarchy of finite congestion games.. In STOC (pp. 67-73). Baltimore: ACM.
2004
Coordination Mechanisms.
Christodoulou, G., Koutsoupias, E., & Nanavati, A. (2004). Coordination Mechanisms.. In J. DÃaz, J. Karhumäki, A. Lepistö, & D. Sannella (Eds.), ICALP (pp. 345-357). Turku: Springer.