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 MelissourgosHeterogeneous Facility Location with Limited Resources AAAI-22
With Aris Filos-Ratsikas and Alexandros VoudourisThe Complexity of Envy-Free Graph Cutting IJCAI-22
With Eduard Eiben, Robert Ganian, Thekla Hamm, and Sebastian OrdyniakParameterized Complexity of Hotelling-Downs with Party Nominees IJCAI-22
With Eduard Eiben, and Tiger-Lily GoldsmithConstant 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-RatsikasThe Parameterized Complexity of Connected Fair Division IJCAI-21
With Eduard Eiben, Robert Ganian, Thekla Hamm, and Sebastian OrdyniakWalrasian Equilibria in Markets with Small Demands AAMAS-21
With Themistoklis Melissourgos and Paul Spirakis VideoRanking 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 SavaniOptimizing Reachability Sets in Temporal Graphs by Delaying AAAI-20
With Igor PotapovExact 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 PotapovOn the Hardness of Energy Minimisation for Crystal Structure Prediction, Fundamenta Informaticae
With Duncan Adamson, Vladimir Gusev, and Igor PotapovApproximating the Existential Theory of the Reals, JCSS
With John Fearnley, Themistoklis Melissourgos, and Paul SpirakisConnected Subgraph Defense Games, Algorithmica
With Eleni Akrida, Themistoklis Melissourgos, and Paul SpirakisComputing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem, JCSS
With John Fearnley, Themistoklis Melissourgos, and Paul SpirakisLipschitz 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 MarkakisMinimizing reachability times on temporal graphs via shifting labels
With Eduard Eiben and George SkretasThe Parameterized Complexity of Welfare Guarantees in Schelling Segregation
With Eduard Eiben and Tiger-Lily GoldsmithThe 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