Archimedes AGT Afternoon Event (ΑAGTA) 2026

Agenda

13:30 - 14:15
Welcome + Lunch (catering)

Session #1
14:15 - 15:45

14:15 - 15:15
Keynote #1
Title: Complexity of Unambiguous Problems in Σ^P_2
Paul Goldberg, Professor at the Dept. of Computer Science, University of Oxford, UK

Abstract: An unambiguous problem is a computational search problem for which any instance has at most one solution. We are interested in particular in problems where this uniqueness of solutions is due to the structure of the problem itself, as opposed to being due to a (hard to verify) promise that any solution is unique. There are not many such problems in the class NP (amongst problems that are not known to be polynomial-time solvable), but there are various interesting ones in the class Σ^P_2. For example, some are based on the idea that we can design competitions for which there is at most one winner. With exponentially-many competitors, we seek a competitor that beats all his opponents: if "beats" is checkable in polynomial time, we have a Σ^P_2 problem having at most one solution. Towards classifying the complexity of these problems, we introduce complexity classes "Polynomial Tournament Winner" and "Polynomial Condorcet Winner". This is joint work in progress with Matan Gilboa, Elias Koutsoupias, and Noam Nisan. I will try to include reminders of definitions of any complexity classes I refer to, apart from P and NP.

Short Bio: Since 2013 he has been a Professor at the Dept. of Computer Science, University of Oxford, UK. Previously, he was a Professor at the Dept. of Computer Science, University of Liverpool, UK, where he was founding Head of the ECCO Research Group. At both Oxford and Liverpool, he worked extensively on algorithmic game theory and related problems in algorithms and computational complexity. Prior to this, he was at the Department of Computer Science, University of Warwick, UK, from 1997. He has also worked at Aston University, UK, and Sandia National Labs (working on algorithmic problems from computational biology), USA. He was awarded his PhD (Edinburgh, ’92) in computational learning theory; and his BA in mathematics (Oxford, ’88). He is currently serving as Editor-in-Chief of ACM Transactions on Economics and Computation, and has ongoing projects in optimisation and computational complexity, and multi-winner voting.

15:15 - 15:25
Talk
Title: TBA
Alkmini Sgouritsa, Assistant Professor at the Department of Informatics of the Athens University of Economics and Business (AUEB), Greece, and a Lead Researcher at the Archimedes Research Unit of the Athena Research Center, Greece

15:25 - 15:35
Talk
Title: Learning Augmented Coordination Mechanisms
Georgios Christodoulou, Professor in the School of Informatics at the Aristotle University of Thessaloniki, Greece,and a Lead Researcher at the Archimedes Research Unit of the Athena Research Center, Greece

Abstract: The inefficiency of decentralized resource allocation, a core challenge in Algorithmic Game Theory, is classically measured by the Price of Anarchy (PoA) and the Price of Stability (PoS). The most widely studied and foundational class of these models are atomic and non-atomic congestion games, for which a robust theory quantifying the inefficiency of equilibria is well- established. To mitigate the effects of this selfish behavior, we employ Coordination Mechanisms, which modify resource costs to incentivize socially improved equilibrium outcomes. In their standard form, Coordination Mechanisms have been limited by a pessimistic, worst-case view; it is assumed that the demand is unknown and adversarially chosen. Consequently, positive results remain sparse, applying mainly to specialized network topologies like parallel links. We address this limitation by studying the design and analysis of learning-augmented coordination mechanisms, where the mechanism is endowed with a potentially inaccurate prediction of the demand.

15:35 - 15:45
Talk
Title: TBA
Georgios Amanatidis, Assistant Professor at the Department of Informatics of the Athens University of Economics and Business (AUEB), Greece, and a Lead Researcher at the Archimedes Research Unit of the Athena Research Center, Greece

15:45 - 16:15
Break

Session #2
16:15 - 17:45

16:15 - 17:15 
Keynote #2
Title: What is the meaning of a game?
Christos Papadimitriou, Donovan Family Professor of Computer Science at Columbia Engineering, USA, and Principal Scientist at the Archimedes Research Unit of the Athena Research Center, Greece

Abstract: We used to believe that the Nash equilibria of a game capture its essence, but decades of computational scrutiny have not been kind to this idea. Perhaps a game should be instead understood as the way in which it changes the correlated behavior of the players through repeated play. Concretely, I propose (and a few people including Georgios Piliouras agree) that the meaning of a game G is a function $\mu_G$ mapping any prior distribution on the mixed strategy space to the limit distribution under the replicator dynamic (the small-step limit of the multiplicative weights update dynamic). I shall discuss the new mathematical and computational challenges this conception of games creates.

Short Bio: Christos Papadimitriou is the Donovan Family Professor of Computer Science at Columbia Engineering, USA, and has held faculty positions at UC Berkeley, Harvard, MIT, Stanford, UC San Diego, and the National Technical University of Athens (NTUA), Greece. He has authored important textbooks like Computational Complexity, Combinatorial Optimization, Algorithms, and Elements of the Theory of Computation, and numerous novels, including the graphic novel Logicomix, which explores the life and work of the philosopher and mathematician Bertrand Russell. His research is diverse and includes Computational Biology, Artificial Intelligence, Machine Learning, Computational Neuroscience, Economics and Game Theory, Generative AI and Large Language Models, Natural Language Processing, Theoretical Computer Science, Algorithms, and Complexity. Christos Papadimitriou is a member of both the US National Academy of Sciences, the US National Academy of Engineering, the Academy of Athens, and a fellow of the American Academy of Arts & Sciences. He has received numerous awards for his scientific contributions, including the 2002 Knuth Prize, the 2012 Godel prize, the 2015 EATCS award, the 2016 IEEE John von Neumann Medal, the Technion 2018 Harvey Prize, and the 2024 INFORMS John von Neumann Theory Prize. In 2022, alongside Constantinos Daskalakis and Timos Sellis, he co-founded Archimedes Research Unit, which operates under Athena Research Center, Greece. Archimedes serves as “a place where the international research community can connect, where groundbreaking ideas can thrive, and where the next generation of scientists can emerge, shaping a brighter future for Greece and the world.”

17:15 - 17:25
Talk
Title: TBA
Evangelos Markakis, Professor at the Department of Informatics of the Athens University of Economics and Business (AUEB), Greece, and Lead Researcher at the Archimedes Research Unit of the Athena Research Center, Greece

17:25 - 17:35
Talk
Title: TBA
Aris Pagourtzis, Professor at the School of Electrical and Computer Engineering, National Technical University of Athens (NTUA), Greece, and Lead Researcher at the Archimedes Research Unit of the Athena Research Center, Greece

17:35 - 17:45
Talk
Title: TBA
Dimitris Fotakis, Professor at the School of Electrical and Computer Engineering, National Technical University of Athens (NTUA), Greece, and Lead Researcher at the Archimedes Research Unit of the Athena Research Center, Greece

17:45 - 18:00
Closing Remarks