Seminar on Algorithmic Game Theory

Upcoming programme · 2026

Open a session to read its abstract. All times are local to Prague.

• 6 OctTuesday Introduction to AGATEAGATE team

  Abstract: Team members introduce themselves and their interests.
• 13 OctTuesday The House Allocation Problem: Popular Dimension and Envy Ratio of Random Serial DictatorshipNdiamé Gueye Ndiaye

  Abstract: The presentation will cover two recent results in game theory.

  In the first half we study popular matchings in the house allocation problem. In the popular matching problem, (a subset of) the vertices in a graph have preference orderings over their potential matches. A matching is popular if it gets a plurality of votes in a pairwise election against any other matching. Unfortunately, popular matchings typically do not exist. So we study a natural relaxation, namely popular winning sets which are a set of matchings that collectively get a plurality of votes in a pairwise election against any other matching.

  In the second half we focus on a central mechanism for this problem is random serial dictatorship (RSD), which has long served as a canonical subject of study due to its simplicity and the existence of exact characterizations by its properties. Despite this extensive understanding, a basic quantitative question about the fairness of this mechanism remains unresolved. Although RSD is often viewed as fair ex ante, surprisingly, it is not envy-free in expectation. We quantify its deviation from envy-freeness via the envy-ratio, which is defined as the maximum, over all instances and pairs of agents, of the ratio between an agent's expected utility for another agent's random object and for its own random object.

• 20 OctTuesday TentativeCharting Continuous Computational Social Choice at ScaleMartin Koutecký

  Abstract: Thinking in percentages instead of integers can dramatically change the computational complexity of election problems. I will show how AI helps chart this “continuous mirror” of the field.
• 27 OctTuesday Computational social choice boot campTrichotomous-Based Committee ElectionsMatthieu Hervouin

  Abstract: Trichotomous ballots are very close to Approval ballots, but instead of expressing only positive or neutral opinions on candidates, voters can also express a negative opinion. As Approval-Based Committee (ABC) Elections have received a lot of interest from the social choice community in the recent years, which led to many breakthroughs, a natural approach to study Trichotomous-Based Committee (TBC) Elections is to adapt rules and properties from the ABC setting.

  After a quick review of important rules and concepts in ABC elections, we will explore several attempts that have been made at adapting key notions of this setting to TBC elections.

• 3 NovTuesday Computational social choice boot campElections Meet Graph ParametersKristýna Pekárková

  Abstract: While multiwinner voting is computationally hard in general, much of the hardness can be circumvented by exploiting the structure of the input election. Viewing approval elections as bipartite graphs between voters and candidates, we study them through the lens of graph theory and six structural parameters: neighborhood diversity, vertex integrity, tree-width, clique-width, twin-width, and VC-dimension. We first relate these structural parameters to existing restricted domains in approval voting, such as Voter Interval (VI) and Candidate Interval (CI) elections, and then study the complexity of multiwinner voting for three prominent approval-based rules: Proportional Approval Voting (PAV), Minimax Approval Voting (MAV), and Chamberlin-Courant Approval Voting (CCAV). Finally, we look at how these parameters behave in practice, by measuring their values on both real-life and synthetic elections.
• 10 NovTuesday Decision with interacting criteriaMichel Grabisch

  Abstract: Most of multicriteria decision models do not take into account interaction between criteria in a multicriteria decision making (MCDM) problem. However, it is rarely the case in practice that criteria are independent. Considering two criteria, we say that they have a positive synergy if satisfying both of them yields a good score, while satisfying only one of them is not significant. On the other side, two criteria have negative synergy if satisfying one of them yields already a good score. Criteria are said to be interacting if such a synergy effect exist between them, otherwise they are said to be independent. Taking into account interaction leads naturally to the use the Choquet integral while importance of criteria are modelled by a capacity. The Choquet integral is in the finite case a generalization of the weighted arithmetic mean, often used in MCDM models. We show how such a general model can be constructed in a rigorous way from the preference of the decision maker.
• 24 NovTuesday Almost EFX in HypergraphsIoannis Kakatelis

  Abstract: We study the existence of envy-free-up-to-any-good (EFX) allocations of indivisible goods among agents with heterogeneous monotone valuations. Christodoulou et al. (2023) introduced the (multi-hyper)graph setting, where agents and goods are represented by vertices and edges of a graph respectively, and only the endpoints of an edge may have non-zero marginal value for it. Our work simplifies and extends previous results of Kaviani et al. in this domain. First, we provide a simpler construction of EF2X allocation for general monotone valuations in hypergraphs with girth at least 3. We extend our ideas when the multiplicity of each edge is 2 and show that an EF3X allocation always exists for additive valuations. Both results can be constructed in polynomial time. Regarding EFX approximations, we provide a simpler construction for \(\frac{\sqrt{2}}{2}\)-EFX allocations in hypergraphs of girth at least 3 under subadditive valuations. We push the state-of-the-art by establishing the existence of \(\frac{2}{3}\)-EFX allocations for additive valuations when the edge multiplicity is 2. Both of the latter results can be constructed in pseudo-polynomial time. By addressing these multi-hypergraph settings, our work contributes to the ongoing effort to resolve the existence of EFX in increasingly general and applicable domains.
• 1 DecTuesday Exact and approximate maximin share allocations in multigraphsSymeon Mastrakoulis

  Abstract: We study the problem of (approximate) maximin share (MMS) allocation of indivisible items among a set of agents. We focus on the graphical valuation model, in which the input is given by a graph where edges correspond to items, and vertices correspond to agents. An edge may have non-zero marginal value only for its incident vertices. We study additive, XOS and subadditive valuations and we present positive and negative results for (approximate) MMS fairness, and also for (approximate) pairwise maximin share (PMMS) fairness.

Further seminar dates will be announced here.

Past seminars

2026

• Sep 08 -- Martin Loebl: The Book Club Problem

  Abstract: I present a fairness problem and explain its relationship with the Rota Bases Conjecture.
• Sep 01 -- Martin Cerny: Patrolling

  Abstract: Model and computational results on analysing patrolling data of one district of Plzen region is presented.
• Jun 10 -- Holger Meinhardt: A Fenchel-Moreau Conjugation-Based Approach for Computing the Pre-Kernel/Pre-Nucleolus (online)

  Online session: Zoom link

  Abstract: Computing the (pre-)nucleolus of a coalitional game with transferable utility (TU game) is in general NP-hard, whereas polynomial-time algorithms exist for specific classes such as assignment games (Solymosi and Raghavan (1994)), matching games (Kern and Paulusma (2003)), or standard tree games (Megiddo (1978); Granot et al. (1996)). However, Faigle et al. (2001) provided a polynomial-time algorithm for computing the nucleolus for the relatively large class of games having a sole intersection point of the pre-kernel with the core. Their proposed computation procedure relies on the ellipsoid method to solve the associated least-cores and on Maschler’s scheme for approximating the (pre-)kernel. Yet, it is well-known that the ellipsoid method encounters a major drawback, namely, the unbounded complexity in a real number model. This provokes numerical instability issues with floating-point arithmetic, causing the ellipsoid algorithm to fail or converge to an incorrect solution (Meinhardt (2025)). In order to overcome the negative side effects of the ellipsoid method, we suggest an alternative approach for computing the pre-nucleolus by relying on a Fenchel-Moreau conjugation-based approach from convex analysis, which can identify the pre-nucleolus when the pre-kernel is a single point. To illustrate this approach, we resume the method of Meinhardt (2013) to compute a pre-kernel element. Though it is a specialized and highly optimized algorithm for the pre-kernel, it assures a runtime complexity of \(\mathcal{O}(n^3\)) for computing the pre-nucleolus whenever the pre-kernel is a single point and the Faigle et al. (2001) assumption is satisfied, which indicates a polynomial-time algorithm for this class of games. Finally, we focus on the replication of the pre-nucleolus in the sense of Meinhardt (2024) for a class of related games to demonstrate the flexibility of the Fenchel-Moreau conjugation-based approach.
• Jun 02 -- Matthieu Hervouin: Proportionality with approval ballots

  Abstract: We will make a broad introduction to Proportionality with approval ballots, focusing on Committee elections and Participatory Budgeting. When selecting several alternatives, Proportionality is a key fairness notion for voters' representation. This topic has received significant attention from the COMSOC community in the recent years. After an extensive literature review, we will present some results on the online setting, where alternatives are revealed one after the other.
• May 26 -- Martin Loebl: Shapley Meets Tutte

  Abstract: We initiate the study of cooperative games where there exist groups of pre-aligned agents. For example, in a road network, the agents are cross-roads and pre-aligned groups are road-segments. For a set of datasets, the agents are attributes and each database which connects two (or more) attributes is pre-aligned. In this setting, each pre-aligned group has size two. Our goal is to find a way to determine the contribution of each individual local connection (pre-aligned couple) to the connectivity of the network, having an adversarial attack in mind or planning a defense of the network, or wanting to split the profits of the network between various owners of the individual local connections of the network. We model these contributions by Shapley values of the connectivity augmented 'local values' which are characteristic functions determined, e.g., by construction costs. We link the concepts of potential and Shapley values of these connectivity augmented local values to the world of Tutte polynomial and the partition function of the Potts model from statistical physics.
• May 20 -- Laurent Gourvès: Existence, Computation and Efficiency of Nash Stable Outcomes in Hedonic Skill Games (online)

  Online session: Zoom link

  Abstract: This talk deals with hedonic skill games, a non-transferable utility counterpart of coalitional skill games which model collaboration among entities through the abstract notions of tasks and the skills required to complete them.

  In the weighted tasks setting, we show that deciding whether an instance of the game admits a Nash stable outcome is NP-complete. We then characterize the instances admitting a Nash stable outcome. This characterization relies on the fact that every agent holds (resp., every task requires) either a single skill or more than one skill. For these instances, the complexity of computing a Nash stable outcome is determined, together with the possibility that natural dynamics converge to a Nash stable outcome from any initial configuration. Our study is completed with a thorough analysis of the price of anarchy of instances always admitting a Nash stable outcome.

• May 19 -- Martin Balko: Approximating Nash equilibria in sparse games

  Abstract: Computing Nash equilibria in normal-form games is a classical and fundamental problem in algorithmic game theory. It is widely believed to be computationally intractable, which motivates the search for approximation algorithms. It remains unknown whether a PTAS exists for computing ε-Nash equilibria, and even this task appears computationally challenging. However, PTAS may be attainable for ε-Nash equilibria in certain restricted classes of games. In this talk, we study the efficient computation of ε-Nash equilibria in sparse games, that is, games whose payoff matrices contain many zero entries.
• May 06 -- Angelo Fanelli: Computing Approximate Pure Nash equilibria in payoff-maximization potential games (online)

  Online session: Zoom link

  Abstract: Potential games form a key class of games in which the existence of pure Nash equilibria is guaranteed, yet their computation is often intractable. This challenge has motivated extensive research on the computation of approximate equilibria. In this talk, we focus on payoff-maximization potential games. We present an algorithmic framework for efficiently computing approximate pure Nash equilibria in P_d-Flip games, and a recent extension based on group deviations that applies to more general potential games.
• Apr 28 -- David Syrchovsky: AlphaStar

  Abstract: AlphaStar is an artificial intelligence system developed to play the real-time strategy game StarCraft II at a very high level. Unlike board games such as chess or Go, StarCraft II is a much harder challenge for AI because players must make decisions in real time, deal with incomplete information, and manage many units and resources at once. This makes it a useful testbed for building systems that can handle complex, dynamic environments.

  In this talk, I will introduce what AlphaStar is, how it learned to play, and why its success matters beyond gaming. AlphaStar showed that modern AI can combine planning, adaptation, and large-scale learning to solve problems that are closer to real-world decision-making than many earlier benchmark tasks. Understanding AlphaStar helps explain both the recent progress in AI and the broader promise of these methods for domains where fast, strategic decisions are essential.

• Apr 14 -- Nicolas Trotignon: Every graph is essential to large treewidth (online)

  Online session: Zoom link

  Abstract: The celebrated Grid Theorem of Robertson and Seymour states that every graph of huge treewidth contains a grid of large treewidth as a minor. Several attempts have been made to find a similar theorem with « induced subgraph » instead of « minor », at the price of certifying huge treewidth with structures more general than grids. We show that, in some sense, obtaining such a result is impossible. This is demonstrated through generic counter-examples to any kind of statement, obtained through a variation of the so-called layered wheel.

  This is a joint work with Bogdan Alecu, Édouard Bonnet and Pedro Bureo Villafana.

• Mar 24 -- Martin Tancer: Necklace splitting on trees

  Abstract: In the classical necklace splitting problem k thieves steal an open-ended necklace with t different types of gems. The number of gems of each type is divisible by k. The target of the thieves is to split the necklace with as few cuts as possible so that they can distribute the pieces so that each thief gets the same number of gems of each type as the other thieves. In this variant, it is well known that (k-1)t cuts are sufficient and for some necklaces also necessary.

  During the talk, I will discuss the variant of this problem when the necklace is arranged along the tree. This setting offers several variants of the problem. I will show a combinatorial solution and a geometric solution of some of the variants.

  The talk is based on joint discussions with Martin Loebl.

• Mar 10 -- Milan Studeny: Semi-graphoids viewed as collections of posets

  Abstract: Semi-graphoids are discrete structures introduced in context of probabilistic reasoning. We show that any semi-graphoid over a finite non-empty variable set N can be viewed as a collection of posets (= partial orderings) on N. To this end, a semi-graphoid is first identified with a particular subgraph of the so-called permutohedral graph, whose nodes are enumerations (= total orderings) of N. The components of this semi-graphoidal subgraph appear to be special geodetically convex sets in the permutohedral graph and, for this reason, each of these components uniquely corresponds to a poset on N. We also mention geometrical interpretation of finite posets in terms of so-called braid cones.
• Mar 03 -- Michel Grabisch: Polynomial representation of TU-games

  Abstract: We propose in this paper a polynomial representation of TU-games, fuzzy measures, capacities, and more generally set functions. Our representation needs a countably infinite set of players and the natural ordering of finite sets of N, defined recursively. For a given basis of the vector space of games, we associate to each game v a formal polynomial of degree at most 2n − 1 whose coefficients are the coordinates of v in the given basis. By the fundamental theorem of algebra, v can be represented by the roots of the polynomial. We present some new families of games stemming from this polynomial context, like the irreducible games, the multiplicative games and the cyclotomic games.

  This is joint work with U. Faigle.

• Feb 25 -- Ulle Endriss: Notions of Single-Peakedness for Incomplete Preferences (Exceptionally in S7)

  Abstract: In the classical model of social choice theory, we say that the preferences of a population are single-peaked if we can arrange the alternatives voters express preferences over on a left-to-right axis in such a way that each voter's preference, when plotted along that axis, will have only a single peak. When preferences are single-peaked in this sense, this greatly simplifies the process of collective decision making, avoiding classical impossibility result such as Arrow's Theorem, and can offer deep insights into the internal makeup of the population reporting preferences.

  Inspired by the needs of applications in the domain of digital democracy, I will discuss how to generalise the concept of single-peakedness from the classical model of voting with ranked preferences to a richer and more flexible model where preferences can be incomplete and where they can include indifferences. This will naturally lead to a total of 10 different notions of single-peakedness, which exhibit intriguing differences in axiomatic, algorithmic, and experimental terms. The talk will be broadly accessible, not assuming any prior exposure to social choice theory.

  This is joint work with Théo Delemazure, Umberto Grandi, and Mohamed Ouaguenouni.

• Feb 17 -- Stephane Gonzales: An Axiomatic Characterization of the Knapsack Budget Allocation Rule

  Abstract: We provide the first axiomatic characterization of the knapsack choice rule — a budget allocation mechanism that selects a subset of items maximizing total value under a hard budget constraint. Our result embeds the knapsack choice rule within a broader class of Prioritize-and-Choose (P&C) mechanisms, which assign vectors of scores to items across ordered priority tiers and rank bundles by comparing their additive scores lexicographically, following this priority order. We characterize both the knapsack choice rule and the full class of P&C mechanisms using simple normative principles, offering a foundation for discrete allocation under budget constraints.

  This is joint work with Federica Ceron and Adriana Navarro-Ramos.

• Feb 03 -- discussions of new research topics: David Sychrovsky on neural networks
• Jan 27 -- discussions of new research topics: Martin Loebl on the regularity lemma
• Jan 20 -- discussions of new research topics
• Jan 14 -- Introduction of new research topics (Loebl, ... )

2025

• Dec 17, 5PM -- Xmass special
• Dec 12, 3PM -- Discussions
• Dec 05, 3.30PM -- Filip Uradnik
• Nov 26, 5PM -- Michel Grabisch: Polarization Networks
• Nov 19, 5PM -- David Sychrovsky: thesis talk prep
• Nov 05, 5PM -- Ismail Ozcan: Interval Valued Cooperative Games
• September, October: discussions on the use of topological methods for study of fairness