Online participation option available - free of charge.

📌 📌 𝗢𝗻𝗹𝗶𝗻𝗲 𝗽𝗮𝗿𝘁𝗶𝗰𝗶𝗽𝗮𝘁𝗶𝗼𝗻 𝗹𝗶𝗻𝗸: https://lnkd.in/dtXaYTWp

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 (AUTH), 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, Columbia University, 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: Constrained Fair Division Problems
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

Abstract: In this talk, we will provide an overview of recent research on fair division of indivisible resources in the presence of constraints. In contrast to the classic fair division setting, we will discuss two variations of the problem where constraints are imposed on the set of feasible allocations. The first one has to do with cardinality constraints on the bundle size assigned to each agent, motivated by assigning shifts or forming equally sized teams. The second one concerns incompatibilities among items and is modeled by a conflict graph, with the meaning that any two items connected by an edge in the graph cannot be given to the same agent. For both of these models we will discuss the existence and computation of allocations that satisfy fairness criteria such as EF1 and EFX (and their appropriate adaptations in these settings).

17:25 - 17:35
Talk #5
Title: Finite Pinwheel Scheduling: the k-Visits Problem
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

Abstract: Pinwheel Scheduling is a fundamental problem where tasks with deadlines $d_i$ must be scheduled perpetually such that each task $i$ appears at least once in every $d_i$ time slots. Despite a long-standing conjecture of PSPACE-completeness, the problem's precise complexity remains a significant open question: it is not even known yet whether it is NP-hard (under standard encoding). As a first step toward settling this tantalizing question, we introduce a finite variant of Pinwheel Scheduling called k-Visits, requiring each of the n tasks to be scheduled exactly k times. While the 1-Visit case is trivial, we prove that 2-Visits is strongly NP-complete via a novel reduction from Numerical 3-Dimensional Matching (N3DM). As intermediate steps in this reduction, we identify new NP-complete variants of N3DM that may be of independent interest. We extend these hardness results to a generalized version of Pinwheel Scheduling where task deadlines vary over time, marking progress toward settling the core problem's complexity. We conclude with some tractable cases for 2-Visits, one of which uncovers an interesting complexity dichotomy based on whether the input is a set or a multiset. This is joint work with Sotiris Kanellopoulos, Christos Pergaminelis, Maria Kokkou, and Euripides Markou (in SODA 2026); available here.

17:35 - 17:45
Talk #6
Title:Competitive Posted Price Mechanisms for Online Budget Feasible Auctions with Submodular Valuations
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

Abstract: We consider budget feasible procurement auctions, in which n agents, each with a privately held service cost, offer their services to an employer. The employer seeks to maximize a public submodular valuation function over the set of hired agents, while facing a hard budget constraint. We consider an online posted-price setting, in which agents arrive in a uniformly random order and the employer must make irrevocable take-it-or-leave-it offers upon their arrival. We present a general approach to the design of posted-price mechanisms in this setting and obtain constant competitive ratios for monotone and non-monotobe submodular valuations. The talk is based on joint work with Andreas Charalampopoulos and Thanos Tolias.

17:45 - 18:00
Closing Remarks




Organizing Committee

⚬ Christos Papadimitriou, Donovan Family Professor of Computer Science at Columbia Engineering, Columbia University, USA, and Principal Scientist at the Archimedes Research Unit of the Athena Research Center, Greece
⚬ 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
⚬ Georgios Christodoulou, Professor in the School of Informatics at the Aristotle University of Thessaloniki (AUTH), Greece, and a Lead Researcher at the Archimedes Research Unit of the Athena Research Center, Greece
⚬ 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
⚬ 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
⚬ 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
⚬ 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