Argyrios Deligkas

I am a Lecturer at the Royal Holloway University of London. Prior to this, I was a Post Doc at the University of Liverpool. and in the department of Industrial Engineering and Management at Technion. I received my PhD at Liverpool, under the supervision of Rahul Savani.

Email: argyrios.deligkas at rhul.ac.uk

Research Interests

  • Computational Complexity

  • Algorithmic Game Theory

  • Mechanism Design

  • Combinatorial Optimization

  • Equilibrium Computation

Publications - Conferences

2022

  • Square-Cut Pizza Sharing is PPA-complete AAAI-22
    With John Fearnley and Themistoklis Melissourgos

  • Heterogeneous Facility Location with Limited Resources AAAI-22
    With Aris Filos-Ratsikas and Alexandros Voudouris

  • The Complexity of Envy-Free Graph Cutting IJCAI-22
    With Eduard Eiben, Robert Ganian, Thekla Hamm, and Sebastian Ordyniak

  • Parameterized Complexity of Hotelling-Downs with Party Nominees IJCAI-22
    With Eduard Eiben, and Tiger-Lily Goldsmith

  • Constant Inapproximability for PPA
    With John Fearnley, Alexandros Hollender, and Themistoklis Melissourgos STOC-22

2021

  • Two's Company, Three's a Crowd: Consensus-Halving for a Constant Number of Agents EC-21
    With Alexandros Hollender and Aris Filos-Ratsikas

  • The Parameterized Complexity of Connected Fair Division IJCAI-21
    With Eduard Eiben, Robert Ganian, Thekla Hamm, and Sebastian Ordyniak

  • Walrasian Equilibria in Markets with Small Demands AAMAS-21
    With Themistoklis Melissourgos and Paul Spirakis Video

  • Ranking Bracelets in Polynomial Time CPM-21
    With Duncan Adamson, Vladimir Gusev, and Igor Potapov

2020

  • Tree Polymatrix Games are PPAD-hard ICALP-20
    With John Fearnley, and Rahul Savani

  • Optimizing Reachability Sets in Temporal Graphs by Delaying AAAI-20
    With Igor Potapov

  • Exact and Approximate Algorithms for Computing a Second Hamiltonian Cycle MFCS-20
    With George Mertzios, Paul Spirakis, and Viktor Zamaraev

  • Crystal Structure Prediction via Oblivious Local Search SEA-20
    With Dmytro Antypov, Vladimir Gusev, Matthew Rosseinsky, Paul Spirakis, and Michael Theofilatos

  • On the Hardness of Energy Minimisation for Crystal Structure Prediction SOFSEM-20
    With Duncan Adamson, Vladimir Gusev, and Igor Potapov

2019

  • Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem ICALP-19
    With John Fearnley, Themistoklis Melissourgos, and Paul Spirakis

  • Connected Subgraph Defense Games SAGT-19
    With Eleni Akrida, Themistoklis Melissourgos, and Paul Spirakis

2018

  • Approximating the Existential Theory of the Reals WINE-18
    With John Fearnley, Themistoklis Melissourgos, and Paul Spirakis

  • Directed Graph Minors and Serial-Parallel Width MFCS-18
    With Reshef Meir

  • Traffic Light Scheduling, Value of Time, and Incentives IJCAI-18
    With Erez Karpaz, Ron Lavi, and Rann Smorodinsky

  • Heterogeneous Facility Location Games AAMAS-18
    With Eleftherios Anastasiadis

2017

  • Computing Constrained Approximate Equilibria in Polymatrix Games SAGT-17
    With John Fearnley and Rahul Savani

  • Binary Search in Graphs Revisited MFCS-17
    With George Mertzios and Paul Spirakis

  • On the Complexity of Weighted Greedy Matchings AAAI-17
    With George Mertzios and Paul Spirakis

2016

  • Inapproximability Results for Approximate Nash Equilibria WINE-16
    With John Fearnley and Rahul Savani

  • Distributed Methods for Computing Approximate Equilibria WINE-16
    With Artur Czumaj, Michail Fasoulakis, John Fearnley, Marcin Jurdziński, and Rahul Savani

  • Lipschitz Continuity and Approximate Equilibria SAGT-16
    With John Fearnley and Paul Spirakis

  • An Empirical Study on Computing Equilibria in Polymatrix Games AAMAS-16
    With John Fearnley, Tobenna Peter Igwe, and Rahul Savani

2014

  • Computing approximate Nash Equilibria in Polymatrix Games WINE-14
    With John Fearnley, Rahul Savani and Paul Spirakis

  • Increasing VCG Revenue by Decreasing the Quality of Items AAAI-14
    With Mingyu Guo and Rahul Savani

2013

  • Revenue Maximization via Hiding Item Attributes IJCAI-13
    With Mingyu Guo


Publications - Journals

  • Optimizing Reachability Sets in Temporal Graphs by Delaying, Information and Computation
    With Igor Potapov

  • On the Hardness of Energy Minimisation for Crystal Structure Prediction, Fundamenta Informaticae
    With Duncan Adamson, Vladimir Gusev, and Igor Potapov

  • Approximating the Existential Theory of the Reals, JCSS
    With John Fearnley, Themistoklis Melissourgos, and Paul Spirakis

  • Connected Subgraph Defense Games, Algorithmica
    With Eleni Akrida, Themistoklis Melissourgos, and Paul Spirakis

  • Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem, JCSS
    With John Fearnley, Themistoklis Melissourgos, and Paul Spirakis

  • Lipschitz Continuity and Approximate Equilibria, Algorithmica
    With John Fearnley and Paul Spirakis

  • Binary Search on Graphs Revisited, Algorithmica
    With George Mertzios and Paul Spirakis

  • Distributed Methods for Computing Approximate Equilibria, Algorithmica
    With Artur Czumaj, Michail Fasoulakis, John Fearnley, Marcin Jurdzínski, and Rahul Savani

  • Inapproximability Results for Constrained Approximate Nash Equilibria, Information and Computation
    With John Fearnley and Rahul Savani

  • Computing approximate Nash Equilibria in Polymatrix Games, Algorithmica
    With John Fearnley, Rahul Savani, and Paul Spirakis

Working Papers

    • A Polynomial-Time Algorithm for 1/3-Approximate Nash Equilibria in Bimatrix Games
      With Michail Fasoulakis and Evangelos Markakis

    • Minimizing reachability times on temporal graphs via shifting labels
      With Eduard Eiben and George Skretas

    • The Parameterized Complexity of Welfare Guarantees in Schelling Segregation
      With Eduard Eiben and Tiger-Lily Goldsmith

    • The K-Centre Problem for Necklaces
      With Duncan Adamson, Vladimir Gusev, and Igor Potapov

PC Member- Subreviewer

  • 2022: AAAI, AAMAS, ICALP, IJCAI, MFCS, WG

  • 2021: AAAI, AAMAS, EC, ICALP, IJCAI, SAGT

  • 2020: AAAI, AAMAS, ECAI, IJCAI, MFCS, SAGT, STOC, WINE

  • 2019: AAAI, AAMAS, ICALP, IJCAI, MFCS, SODA, WINE

  • 2018: AAAI, AAMAS, EC, IJCAI, MFCS, SAGT, SODA, WG, WINE, WWW

  • 2017: AAAI, AAMAS, CIAC, EC, PODC, SAGT, STACS

  • 2016: AAMAS, ESA, WINE

  • 2015: AAAI, AAMAS, ICALP, IJCAI, WINE

  • 2014: AAAI, AAMAS, WINE

  • 2013: AAAI, AAMAS, WINE