Dr Giorgos Christodoulou

Computer Science

    Publications

    2020

    Resource-Aware Protocols for Network Cost-Sharing Games (Conference Paper)

    Christodoulou, G., Gkatzelis, V., Latifian, M., & Sgouritsa, A. (n.d.). Resource-Aware Protocols for Network Cost-Sharing Games. doi:10.1145/3391403.3399528

    DOI: 10.1145/3391403.3399528

    Resource-Aware Protocols for Network Cost-Sharing Games. (Journal article)

    Christodoulou, G., Gkatzelis, V., Latifian, M., & Sgouritsa, A. (2020). Resource-Aware Protocols for Network Cost-Sharing Games.. CoRR. doi:10.1145/3391403.3399528

    DOI: 10.1145/3391403.3399528

    On the Nisan-Ronen conjecture for submodular valuations (Conference Paper)

    Christodoulou, G., Koutsoupias, E., & Kovács, A. (2020). On the Nisan-Ronen conjecture for submodular valuations. In Proceedings of the Annual ACM Symposium on Theory of Computing (pp. 1086-1096). doi:10.1145/3357713.3384299

    DOI: 10.1145/3357713.3384299

    Existence and Complexity of Approximate Equilibria in Weighted Congestion Games (Journal article)

    Christodoulou, G., Gairing, M., Giannakopoulos, Y., Poças, D., & Waldmann, C. (n.d.). Existence and Complexity of Approximate Equilibria in Weighted Congestion Games. Retrieved from http://arxiv.org/abs/2002.07466v2

    Existence and Complexity of Approximate Equilibria in Weighted Congestion Games. (Conference Paper)

    Christodoulou, G., Gairing, M., Giannakopoulos, Y., Poças, D., & Waldmann, C. (2020). Existence and Complexity of Approximate Equilibria in Weighted Congestion Games.. In A. Czumaj, A. Dawar, & E. Merelli (Eds.), ICALP Vol. 168 (pp. 32:1). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. Retrieved from http://www.informatik.uni-trier.de/~ley/db/conf/icalp/icalp2020.html

    2019

    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

    Impartial Selection with Additive Approximation Guarantees (Conference Paper)

    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

    DOI: 10.1007/978-3-030-30473-7_18

    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 (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 Lecture Notes in Computer Science. Beijing, China: Springer Nature. doi:10.1007/978-3-319-99660-8_9

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

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

    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

    DOI: 10.4230/LIPIcs.ICALP.2018.150

    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).

    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

    Strategic Contention Resolution in Multiple Channels. (Journal article)

    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 (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., 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).

    DOI: 10.1145/3033274.3085151

    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. ACM. doi:10.1145/3033274.3085147

    DOI: 10.1145/3033274.3085147

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

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

    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.

    DOI: 10.1137/1.9781611974782.64

    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. 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

    DOI: 10.4230/LIPIcs.ESA.2016.30

    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

    Price of Stability in Polynomial Congestion Games (Journal article)

    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

    DOI: 10.1145/2841229

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

    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

    DOI: 10.1145/2847520

    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

    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

    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. 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 fuer Informatik. Retrieved from http://drops.dagstuhl.de/opus/portals/lipics/index.php?semnr=16013

    2015

    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

    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

    Universal Network Cost-Sharing Design. (Journal article)

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

    2014

    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

    2013

    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

    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.

    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

    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

    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

    2010

    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

    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

    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.