Dr Giorgos Christodoulou

Computer Science

    Publications

    2019

    Impartial Selection with Additive Approximation Guarantees (Conference Paper)

    Caragiannis, I., Christodoulou, G., & Protopapas, N. (n.d.). Impartial Selection with Additive Approximation Guarantees. Retrieved from http://arxiv.org/abs/1910.00135v1

    DESIGNING NETWORKS WITH GOOD EQUILIBRIA UNDER UNCERTAINTY (Journal article)

    Christodoulou, G., & Sgouritsa, A. (2019). DESIGNING NETWORKS WITH GOOD EQUILIBRIA UNDER UNCERTAINTY. SIAM JOURNAL ON COMPUTING, 48(4), 1364-1396. doi:10.1137/16M1096694

    DOI: 10.1137/16M1096694

    THE PRICE OF STABILITY OF WEIGHTED CONGESTION GAMES (Journal article)

    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

    DOI: 10.1137/18M1207880

    2018

    An Improved Envy-Free Cake Cutting Protocol for Four Agents (Journal article)

    Amanatidis, G., Christodoulou, G., Fearnley, J., Markakis, E., Psomas, C. -A., & Vakaliou, E. (n.d.). An Improved Envy-Free Cake Cutting Protocol for Four Agents. Lecture Notes in Computer Science. doi:10.1007/978-3-319-99660-8_9

    DOI: 10.1007/978-3-319-99660-8_9

    Short Paper: Strategic Contention Resolution in Multiple Channels with Limited Feedback (Conference Paper)

    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

    DOI: 10.1007/978-3-319-99660-8_22

    Strategic Contention Resolution in Multiple Channels (Conference Paper)

    Christodoulou, G., Melissourgos, T., & Spirakis, P. G. (n.d.). Strategic Contention Resolution in Multiple Channels. Retrieved from http://arxiv.org/abs/1810.04565v1

    The Price of Stability of Weighted Congestion Games (Conference Paper)

    Christodoulou, G., Gairing, M., Giannakopoulos, Y., & Spirakis, P. G. (n.d.). The Price of Stability of Weighted Congestion Games. Retrieved from http://arxiv.org/abs/1802.09952v4

    On the Efficiency of All-Pay Mechanisms (Journal article)

    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

    DOI: 10.1007/s00453-017-0296-2

    An Improved Envy-Free Cake Cutting Protocol for Four Agents. (Conference Paper)

    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 (Book)

    Christodoulou, G., & Harks, T. (2018). Preface (Vol. 11316 LNCS).

    2017

    A 3-player protocol preventing persistence in strategic contention with limited feedback (Conference Paper)

    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 (Conference Paper)

    Christodoulou, G., Gkatzelis, V., & Sgouritsa, A. (2017). Cost-Sharing Methods for Scheduling Games under Uncertainty. In Proceedings of the 2017 ACM Conference on Economics and Computation - EC '17. ACM Press. doi:10.1145/3033274.3085151

    DOI: 10.1145/3033274.3085151

    A 3-Player Protocol Preventing Persistence in Strategic Contention with Limited Feedback. (Conference Paper)

    Christodoulou, G., Gairing, M., Nikoletseas, S. E., Raptopoulos, C., & 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 (Conference Paper)

    Christodoulou, G., Sgouritsa, A., & ACM. (2017). An Improved Upper Bound for the Universal TSP on the Grid. In PROCEEDINGS OF THE TWENTY-EIGHTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS (pp. 1006-1021). Retrieved from http://gateway.webofknowledge.com/

    Truthful Allocation Mechanisms Without Payments (Conference Paper)

    Amanatidis, G., Birmpas, G., Christodoulou, G., & Markakis, E. (2017). Truthful Allocation Mechanisms Without Payments. In Proceedings of the 2017 ACM Conference on Economics and Computation - EC '17. ACM Press. doi:10.1145/3033274.3085147

    DOI: 10.1145/3033274.3085147

    2016

    On the Efficiency of the Proportional Allocation Mechanism for Divisible Resources (Journal article)

    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

    DOI: 10.1007/s00224-016-9701-5

    Strategic Contention Resolution with Limited Feedback (Conference Paper)

    Christodoulou, G., Gairing, M., Nikoletseas, S., Raptopoulos, C., & Spirakis, P. (n.d.). Strategic Contention Resolution with Limited Feedback. Retrieved from http://arxiv.org/abs/1606.06580v1

    Bayesian Combinatorial Auctions (Journal article)

    Christodoulou, G., Kovacs, A., & Schapira, M. (2016). Bayesian Combinatorial Auctions. JOURNAL OF THE ACM, 63(2). doi:10.1145/2835172

    DOI: 10.1145/2835172

    Designing Cost-Sharing Methods for Bayesian Games (Conference Paper)

    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

    DOI: 10.1007/978-3-662-53354-3_26

    Social Welfare in One-Sided Matching Mechanisms (Conference Paper)

    Christodoulou, G., Filos-Ratsikas, A., Stiil, S. K., Goldberg, P. W., Zhang, J., Zhang, J., & Machinery, A. C. (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 http://gateway.webofknowledge.com/

    Strategic Contention Resolution with Limited Feedback. (Conference Paper)

    Christodoulou, G., Gairing, M., Nikoletseas, S. E., Raptopoulos, C., & 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 fuer Informatik. Retrieved from http://drops.dagstuhl.de/opus/portals/lipics/index.php?semnr=16013

    2015

    Price of Stability in Polynomial Congestion Games (Journal article)

    Christodoulou, G., & Gairing, M. (2015). Price of Stability in Polynomial Congestion Games. ACM Transactions on Economics and Computation, 4(2), 1-17. doi:10.1145/2841229

    DOI: 10.1145/2841229

    Designing Networks with Good Equilibria under Uncertainty (Conference Paper)

    Christodoulou, G., & Sgouritsa, A. (n.d.). Designing Networks with Good Equilibria under Uncertainty. Retrieved from http://arxiv.org/abs/1503.03392v2

    On the Efficiency of All-Pay Mechanisms (Conference Paper)

    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

    DOI: 10.1007/978-3-662-48350-3_30

    On the Efficiency of the Proportional Allocation Mechanism for Divisible Resources (Journal article)

    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

    DOI: 10.1007/978-3-662-48433-3_13

    On the Efficiency of the Proportional Allocation Mechanism for Divisible Resources. (Conference Paper)

    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

    Tight Bounds for the Price of Anarchy of Simultaneous First Price Auctions. (Journal article)

    Christodoulou, G., Kovács, A., Sgouritsa, A., & Tang, B. (n.d.). Tight Bounds for the Price of Anarchy of Simultaneous First Price Auctions. Retrieved from http://arxiv.org/abs/1312.2371v3

    Universal Network Cost-Sharing Design. (Journal article)

    Christodoulou, G., & Sgouritsa, A. (2015). Universal Network Cost-Sharing Design.. CoRR, abs/1503.03392.

    2014

    Mechanisms for Scheduling with Single-Bit Private Values (Journal article)

    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

    DOI: 10.1007/s00224-015-9625-5

    2013

    A Deterministic Truthful PTAS for Scheduling Related Machines. (Journal article)

    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. (Journal article)

    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.

    Contention Resolution under Selfishness (Journal article)

    Christodoulou, G., Ligett, K., & Pyrga, E. (2014). Contention Resolution under Selfishness. ALGORITHMICA, 70(4), 675-693. doi:10.1007/s00453-013-9773-4

    DOI: 10.1007/s00453-013-9773-4

    Improving the Price of Anarchy for Selfish Routing via Coordination Mechanisms (Journal article)

    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

    DOI: 10.1007/s00453-013-9753-8

    Price of Stability in Polynomial Congestion Games (Conference Paper)

    Christodoulou, G., & Gairing, M. (2013). Price of Stability in Polynomial Congestion Games. In Unknown Conference (pp. 496-507). Springer Berlin Heidelberg. doi:10.1007/978-3-642-39212-2_44

    DOI: 10.1007/978-3-642-39212-2_44

    2012

    Convergence and approximation in potential games (Journal article)

    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

    DOI: 10.1016/j.tcs.2012.02.033

    Mechanisms for Scheduling with Single-Bit Private Values. (Conference Paper)

    Auletta, V., Christodoulou, G., & Penna, P. (2012). Mechanisms for Scheduling with Single-Bit Private Values.. In SAGT (pp. 25-36). Barcelona: Springer.

    2011

    A Global Characterization of Envy-Free Truthful Scheduling of Two Tasks. (Conference Paper)

    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 (Conference Paper)

    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

    DOI: 10.1007/978-3-642-23719-5_11

    On the Performance of Approximate Equilibria in Congestion Games (Journal article)

    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

    DOI: 10.1007/s00453-010-9449-2

    2010

    A Deterministic Truthful PTAS for Scheduling Related Machines (Conference Paper)

    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. (Conference Paper)

    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 (Conference Paper)

    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

    DOI: 10.1007/978-3-642-14162-1_36

    Mechanism design for fractional scheduling on unrelated machines (Journal article)

    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

    DOI: 10.1145/1721837.1721854

    Truthful Mechanisms for Exhibitions. (Conference Paper)

    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 (Journal article)

    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

    DOI: 10.1007/s00453-008-9165-3

    Coordination mechanisms (Journal article)

    Christodoulou, G., Koutsoupias, E., & Nanavati, A. (2009). Coordination mechanisms. Theoretical Computer Science, 410(36), 3327-3336. doi:10.1016/j.tcs.2009.01.005

    DOI: 10.1016/j.tcs.2009.01.005

    Mechanism Design for Scheduling. (Journal article)

    Christodoulou, G., & Koutsoupias, E. (2009). Mechanism Design for Scheduling.. Bulletin of the EATCS, 97, 40-59.

    On the Performance of Approximate Equilibria in Congestion Games. (Conference Paper)

    Christodoulou, G., Koutsoupias, E., & Spirakis, P. G. (2009). On the Performance of Approximate Equilibria in Congestion Games.. In ESA (pp. 251-262). Copenhagen: Springer.

    On the Price of Stability for Undirected Network Design. (Conference Paper)

    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 (Conference Paper)

    Christodoulou, G., Koutsoupias, E., & Vidali, A. (n.d.). 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

    DOI: 10.1007/978-3-540-87744-8_25

    Bayesian Combinatorial Auctions (Conference Paper)

    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

    DOI: 10.1007/978-3-540-70575-8_67

    Price of Anarchy. (Chapter)

    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. (Conference Paper)

    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. (Conference Paper)

    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. (Conference Paper)

    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. (Conference Paper)

    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. (Conference Paper)

    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. (Conference Paper)

    Christodoulou, G., & Koutsoupias, E. (2005). The price of anarchy of finite congestion games.. In STOC (pp. 67-73). Baltimore: ACM.

    2004

    Coordination Mechanisms. (Conference Paper)

    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.