• About
• Teaching
• Research
• Publications
• Contacts

Seminar on Algorithmic Game Theory

Organization

Program

2026

• 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 paper, 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 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 6 (Wednesday) -- Angelo Fanelli: Computing Approximate Pure Nash equilibria in payoff-maximization potential games (Exceptionally over zoom)
  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.
• April 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.

• April 14 -- Nicolas Trotignon: Every graph is essential to large treewidth (Exceptionally over 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.

• March 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.

• March 10 -- Milan Studeny: Semi-graphoids viewed as collections of posets
  Absract: 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.
• March 3 -- 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.

• February 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.

• February 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.

• February 3 -- discussions of new research topics: David Sychrovsky on neural networks
• January 27 -- discussions of new research topics: Martin Loebl on the regularity lemma
• January 20 -- discussions of new research topics
• January 14, 5PM -- Introduction of new research topics (Loebl, ... )

2025

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