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 Speaker #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 #1
Title: Learning Augmented Mechanism Design
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

Abstract: We revisit the design of mechanisms via the learning-augmented framework, where supplementary (machine-learned) information is provided. We first adopt a perspective in which the mechanism receives an output recommendation. The goal is to leverage this advice to design mechanisms with better approximation guarantees when the recommendation is accurate, while maintaining robust performance against worst-case scenarios when the advice is misleading. We propose a generic, universal measure, which we call quality of recommendation, to evaluate the mechanism performance of several well-studied mechanism design paradigms, and devise new mechanisms, but also provide refined analysis for existing ones. We complement these positive results by exploring the limitations of known strategyproof mechanisms when restricted to output recommendations. Finally, we study a hybrid advice model that integrates output recommendations with partial prediction of input types. We explore the trade-off between these two predictive extremes, demonstrating that targeting predictions of specific input types are essential for achieving significantly improved performance guarantees.

15:25 - 15:35
Talk #2
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 #3
Title: Online Fair Division for Personalized 2-Value Instances
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

Abstract: We study an online fair division setting, where goods arrive one at a time and there is a fixed set of n agents, each of whom has an additive valuation function over the goods. Once a good appears, the value each agent has for it is revealed and it must be allocated immediately and irrevocably to one of the agents. It is known that without any assumptions about the values being severely restricted or coming from a distribution, very strong impossibility results hold in this setting. To bypass the latter, we turn our attention to instances where the valuation functions are restricted. In particular, we study personalized 2-value instances, where there are only two possible values each agent may have for each item, possibly different across agents, and we show how to obtain worst case guarantees with respect to well-known fairness notions, such as maximin share fairness and envy-freeness up to one (or two) good(s). Further, we show that, by allowing some limited access to future information, it is possible to have stronger results with less involved approaches. This is joint work with Alexandros Lolos, Evangelos Markakis, Victor Turmel.

15:45 - 16:15
Break

Session #2
16:15 - 17:45

16:15 - 17:15 
Keynote Speaker #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 #4
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 #5
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 #6
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