The increasing integration of renewable energy sources into the electricity grid is transforming electricity markets in two major ways. First, because wind and solar power generation do not always align with consumption patterns, energy storage is becoming essential for maintaining grid stability. Second, network congestion is becoming more frequent, as existing infrastructure was not originally designed for decentralized energy generation. We present a flow-based, game-theoretic model of a simplified electricity market, where competitive players purchase electricity, store it, and resell it. Buying and selling prices vary over time but are predetermined for each instance of the game. Players can only buy electricity when both production levels and network capacity allow it. We analyze different special cases and pricing schemes within this abstract model and identify fundamental inefficiencies arising from strategic behavior in such a market.

Network creation games model the formation and evolution of real-world networks through the interaction of selfish agents corresponding to nodes in a network. These agents strategically buy edges towards each other in order to reduce their distance to all other agents in the network. Although many network creation games such as the well-known Network Creation Game by Fabrikant et al. consider networks without edge weights, this is not representative of many real-world networks, such as fiber-optic networks, where distance plays a massive role. To model such settings, Bilò et al. propose the Generalized Network Creation Game, a generalization of the Network Creation Game with edge-weighted host graphs. They show that the Price of Anarchy of their model is significantly larger than the Price of Anarchy of the Network Creation Game. We introduce a bilateral version of the Generalized Network Creation Game and analyze its Price of Anarchy. In particular, we investigate its Price of Anarchy with respect to multiple solution concepts that allow for varying amounts of cooperation. We show that for arbitrary edge weights, the Price of Anarchy remains high for any amount of cooperation. However, for the metric variant of our model, we show that for a certain degree of cooperation, the Price of Anarchy is significantly lower than the Price of Anarchy of the metric Generalized Network Creation Game.

k-center clustering is a fundamental classification problem, where the task is to categorize the given collection of entities into $k$ clusters and come up with a representative for each cluster, so that the maximum distance between an entity and its representative is minimized. In this work, we focus on the setting where the entities are represented by binary vectors with missing entries, which model incomplete categorical data. This version of the problem has wide applications, from predictive analytics to bioinformatics.

Our main finding is that the problem, which is notoriously hard from the classical complexity viewpoint, becomes tractable as soon as the known entries are sparse and exhibit a certain structure. Formally, we show fixed-parameter tractable algorithms for the parameters vertex cover, fracture number, and treewidth of the row-column graph, which encodes the positions of the known entries of the matrix. Additionally, we tie the complexity of the 1-cluster variant of the problem, which is famous under the name Closest String, to the complexity of solving integer linear programs with few constraints. This implies, in particular, that improving upon the running times of our algorithms would lead to more efficient algorithms for integer linear programming in general.

Hedonic Games are fundamental models for investigating the formation of coalitions among a set of strategic agents. The main feature of these games is that every agent has a certain utility for every possible coalition of agents and this utility only depends on the subset of agents that belongs to any given coalition. In general, agents can have arbitrary utility for each of the exponentially many possible coalitions. To avoid this intractability, many variants with succinct representations of the agents' utility functions have been devised and analyzed, most prominently additively-separable and fractional Hedonic Games. We depart from this by studying a novel succinct variant. In our model, each agent has a real-valued type in the range $[0,1]$ and an agent's utility for some given coalition is a simple function of her type differences to the other members of this coalition. This allows to model natural situations like athletes forming training subgroups with similar performance levels or voters that partition themselves along a political spectrum.

We investigate the connection to the recently proposed model of Schelling Games with continuous types and present first results on game dynamics and equilibrium existence for variants using a threshold-based setting, or where agents focus on their maximum or average type difference. This is joined work with Pascal Lenzner and Marcus Wunderlich.

Over the past months, the Bachelor's project has been working with Deutsche Krankenhausgesellschaft to analyse the publicly available, comprehensive hospital quality reports, creating visualisations on questions raised by the project partner. We will report on some insights, troubles and challanges arising in this project, including the difficulty of dealing with inconsistencies in the data format.

Hans: Temporal Network Creation Games: The Impact of Non-Locality and Terminals

Modern networks—economic, social, and technological—are dynamic and shaped by the decisions of many interacting agents. A recent model by Bilò et al. (IJCAI 2023) captures this by letting selfish agents form temporal networks to reach others over time. In our work, we explore two natural extensions of this model: first, agents may build connections beyond just their incident edges (the global setting), and second, they may only need to reach a subset of nodes (the terminal model). We study the existence and structure of equilibria in both cases. Surprisingly, more freedom in edge creation can lead to worse outcomes: the global model has a strictly higher Price of Anarchy than the local one. For the terminal model, we uncover a strong dependency on the number of terminals and provide a translation tool between the two models. Unlike previous work, our results also extend to settings where connections may be available at multiple time steps.

Simon:The Bakers and Millers Game with Restricted Locations

We study a strategic location game known as the Bakers and Millers Game, where two types of agents—bakers and millers—choose locations to maximize their access to the opposite type while minimizing competition from their own. Bakers are restricted in their location choices, while millers are not. Each agent optimizes the ratio of opposing-type agents to same-type agents at their chosen location. We show that, despite these restrictions, pure Nash equilibria still exist and can be computed efficiently. Our algorithm also guarantees a near-optimal social welfare, within a factor of $2\left(\frac{e}{e-1}\right)$. We further establish tight bounds on the price of anarchy and stability. Conceptually, our model extends classical Hedonic Games by introducing spatial constraints: agents sharing a location form a coalition. This framework captures and generalizes both Fractional Hedonic Games and Hedonic Diversity Games, opening new directions for coalition formation under location constraints.

Stefan:As You Go: Enumerating Edges of a Spanning Tree

Classical planning separates plan creation from execution, but in settings where planning is slow—due to complex constraints or expensive data access—it can be better to interleave the two. We explore this idea using enumeration algorithms that quickly output parts of a solution with low delay. Our concrete case is the minimum spanning tree problem, across all four variants: directed/undirected and weighted/unweighted. Here, each output is an edge of the tree. We show that efficient enumeration is possible in three of the four variants, achieving low preprocessing and delay bounds. Only for the weighted directed case is enumeration provably infeasible. We support our theoretical results with experiments on random graphs, showing that our method performs well in practice, making fast, incremental planning feasible in real-world scenarios.

TBA

Janina: Evaluating Network Creation Game Models on Real-World Dynamic Graphs

This master thesis will investigate how well game-theoretic network formation models explain the dynamics of real-world networks. Using temporal graph data from domains such as scientific collaboration and internet topology, the thesis evaluates how closely these models align with observed structural changes over time. A central focus lies on assessing the predictive power of game-theoretic mechanisms for link prediction. The aim is to better understand the applicability of network creation models in explaining and analyzing the behavior of real-world networks.

Lara: From Arrival to Departure: Assigning Buses to Parking Spots

When buses return to the bus depot in the evening, they must be assigned to lanes that follow FIFO or LIFO constraints. The key challenge is to ensure that each bus can depart the next day to serve a scheduled trip, and that each trip is covered by a bus of the correct type (e.g. electric vs. diesel, or large vs. small). Mismatches between bus types and trips, or having to repark vehicles to allow departures, are both highly undesirable in practice. These issues are further complicated by real-world factors such as delays, disruptions, and limited depot infrastructure. At the same time, the problem presents interesting theoretical challenges in scheduling and combinatorial optimisation. In this short talk, I will introduce the core problem, discuss solution approaches and outline the current direction of my Master’s thesis.

The NP class of problems includes optimisation and decision problems. Famously, each problem in this class (e.g.: routing, planning, scheduling) can be transformed into every other problem in the class. This allows us to --ghostbusters' style-- choose the form of the Destructor best suited to attack such problems. A logic representation, such as Boolean satisfiability, one of its derivatives is surprisingly efficient. But why limit ourselves to a single terminator? Why do few current solvers run on parallel hardware? What should be done to change that? Join me on 2 June to see just how deep this rabbit hole goes, as well as some easy parallel wins to make your solvers more efficient.

We investigate the connection to the recently proposed model of Schelling Games with continuous types and present first results on game dynamics and equilibrium existence for variants using a threshold-based setting, or where agents focus on their maximum or average type difference. This is joined work with Pascal Lenzner and Marcus Wunderlich.

Temporal graphs model networks with time-dependent connections. Small changes in their definition—such as whether paths must strictly increase in time, whether adjacent edges may be active simultaneously, or whether multiple labels are allowed—give rise to different settings of temporal graphs. In this talk, we analyze these classes through the lens of reachability equivalence: when do two temporal graph (classes) induce the same reachability graphs? We discuss recent results and analyze the relations between aforementioned temporal settings.

Gray-box optimization is an approach for making some problem-specific information available to the algorithm while still relying on fitness information as the main guide to an optimum. This approach was shown to be beneficial in various combinatorial optimization tasks and neatly captures the continuum between fully black-box algorithms and tailored algorithms.

In this work, we discuss different flavors of gray-box algorithms. We then analyze various black-box and gray-box algorithms on the vertex coloring problem. Employing run time analysis on complete bipartite graphs and paths, we show how progressively more problem knowledge leads to asymptotic run time gains.

Our society is critically dependent on reliable algorithms, especially optimisation algorithms to support complex decision making, but establishing trust is a growing concern. How do we know that our algorithmic choices – whether it be a heuristic or exact solver, or a model, or parameter configurations – are reliable in practice? This vexing issue relies on testing algorithms with enough unbiased test instances to gain insights into strengths and weaknesses under various conditions. This talk will provide a brief introduction to Instance Space Analysis as a methodology that provides a mathematically rigorous foundation for “stress-testing” algorithms. ISA exposes the strengths and weaknesses of algorithms and supports the generation of rich and diverse test problems to understand algorithm reliability under a variety of conditions. The methodology has been made available via an online tool (matilda.unimelb.edu.au) that has been adopted worldwide by researchers in many fields, and is supporting industry partners keen to avoid disasters when deploying critical algorithms. The webinar will use several case studies from timetabling and bin packing to highlight how insights into performance of heuristics, MIP models or solvers can be obtained by generating and testing diverse instances with ISA.

The performance of algorithms depends heavily on internal parameters, which are often hard to configure. Automatic Algorithm Configuration (AC) addresses this challenge, but existing methods either lack theoretical guarantees or are resource-inefficient. The work we present in this talk provides an introduction to Multi-Armed Bandits (MAB) and advances AC by developing MAB-based methods that combine provable quality guarantees with improved efficiency. We propose a general Combinatorial Bandit framework for AC, supporting both numerical and preference-based feedback, and prove it identifies near-optimal configurations within a theoretically minimal budget. Additionally, we adapt and enhance an existing method for Hyperparameter Optimization to reuse samples efficiently.

Since our last progress report, the Bachelor's project has taken yet another 180-degree turn: We have finally received data and attempted the development of a forecasting model for hospital care personnel with regards to imminent hospital closures. In this talk, we will both give an insight into the challenges of developing such a model as well as some concluding views on the project as a whole.

The Vehicle Routing Problem (VRP) is a popular generalization of the Traveling Salesperson Problem. Instead of one salesperson traversing the entire weighted, undirected graph G, there are k vehicles available to jointly cover the set of clients C ⊆ V(G). Every vehicle must start at one of the depot vertices D ⊆ V(G) and return to its start. Capacitated Vehicle Routing (CVRP) additionally restricts the route of each vehicle by limiting the number of clients it can cover, the distance it can travel, or both. In this work, we study the complexity of VRP and the three variants of CVRP for several parameterizations, in particular focusing on the treewidth of G. We present an FPT algorithm for VRP parameterized by treewidth. For CVRP, we prove paraNP- and W[·]-hardness for various parameterizations, including treewidth, thereby rendering the existence of FPT algorithms unlikely. In turn, we provide an XP algorithm for CVRP when parameterized by both treewidth and the vehicle capacity. To be presented at IPEC'25

Shortcut sets are sets of new edges to add to a graph to reduce the number of hops between any two nodes without changing who can reach who. Our goal is to create small shortcut sets that reduce the distance between any two reachable nodes as far as possible. While the undirected case has been essentially settled for a long time, the directed case has enjoyed significant attention in recent years, leading to many intricate results and techniques. In this talk, I will introduce the notion of shortcut sets, give an overview of the state-of-the-art, and, if time allows, show you both elegant proofs from the recent literature and new results we obtained for an upcoming publication.