Max Klimm

NeurIPS Conference 2025 Conference Paper

Impartial Selection with Predictions

• Javier Cembrano
• Felix Fischer
• Max Klimm

We study the selection of agents based on mutual nominations, a theoretical problem with many applications from committee selection to AI alignment. As agents both select and are selected, they may be incentivized to misrepresent their true opinion about the eligibility of others to influence their own chances of selection. Impartial mechanisms circumvent this issue by guaranteeing that the selection of an agent is independent of the nominations cast by that agent. Previous research has established strong bounds on the performance of impartial mechanisms, measured by their ability to approximate the number of nominations for the most highly nominated agents. We study to what extent the performance of impartial mechanisms can be improved if they are given a prediction of a set of agents receiving a maximum number of nominations. Specifically, we provide bounds on the consistency and robustness of such mechanisms, where consistency measures the performance of the mechanisms when the prediction is correct and robustness its performance when the prediction is incorrect. For the general setting where up to $k$ agents are to be selected and agents nominate any number of other agents, we give a mechanism with consistency $1-O\big(\frac{1}{k}\big)$ and robustness $1-\frac{1}{e}-O\big(\frac{1}{k}\big)$. For the special case of selecting a single agent based on a single nomination per agent, we prove that $1$-consistency can be achieved while guaranteeing $\frac{1}{2}$-robustness. A close comparison with previous results shows that (asymptotically) optimal consistency can be achieved with little to no sacrifice in terms of robustness.

JAIR Journal 2025 Journal Article

Multi-Leader Congestion Games with an Adversary

• Tobias Harks
• Mona Henle
• Max Klimm
• Jannik Matuschke
• Anja Schedel

We study a multi-leader single-follower congestion game where multiple users choose subsets out of a given set of resources and an adversary attacks the resources with maximum loads, causing additional costs for the users. We first show that the resulting strategic game among the leaders admits a pure Nash equilibrium if the users’ strategy-spaces are given by matroids and the resource costs are linear and identical. However, equilibria may fail to exist already when strategy spaces are not matroids or the linear cost coefficients are not identical. We therefore consider approximate equilibria for the case that each user chooses one resource and the resource costs are linear but non-identical. Our main result establishes that K ≈ 1.1974 is the smallest possible factor such that the existence of a K-approximate equilibrium is guaranteed for all instances of the game. We also provide a polynomial time algorithm for computing an α-approximate equilibrium with the smallest possible factor α ≤ K for a given instance, in particular finding an exact equilibrium if one exists.

AAAI Conference 2024 Conference Paper

Information Design for Congestion Games with Unknown Demand

• Svenja M. Griesbach
• Martin Hoefer
• Max Klimm
• Tim Koglin

We study a novel approach to information design in the standard traffic model of network congestion games. It captures the natural condition that the demand is unknown to the users of the network. A principal (e.g., a mobility service) commits to a signaling strategy, observes the realized demand and sends a (public) signal to agents (i.e., users of the network). Based on the induced belief about the demand, the users then form an equilibrium. We consider the algorithmic goal of the principal: Compute a signaling scheme that minimizes the expected total cost of the induced equilibrium. We concentrate on single-commodity networks and affine cost functions, for which we obtain the following results. First, we devise a fully polynomial-time approximation scheme (FPTAS) for the case that the demand can only take two values. It relies on several structural properties of the cost of the induced equilibrium as a function of the updated belief about the distribution of demands. We show that this function is piecewise linear for any number of demands, and monotonic for two demands. Second, we give a complete characterization of the graph structures for which it is optimal to fully reveal the information about the realized demand. This signaling scheme turns out to be optimal for all cost functions and probability distributions over demands if and only if the graph is series-parallel. Third, we propose an algorithm that computes the optimal signaling scheme for any number of demands whose time complexity is polynomial in the number of supports that occur in a Wardrop equilibrium for some demand. Finally, we conduct a computational study that tests this algorithm on real-world instances.

SODA Conference 2022 Conference Paper

Competitive Strategies for Symmetric Rendezvous on the Line

• Max Klimm
• Guillaume Sagnol
• Martin Skutella
• Khai Van Tran

In the Symmetric Rendezvous Search on the Line with Unknown Initial Distance, two identical agents are placed on the real line with their distance, the other's location, and their orientation unknown to them. Moving along the line at unit speed and executing the same randomized search strategy, the agents' goal is to meet up as early as possible. The expected meeting time obviously depends on the unknown initial distance and orientations. The quality of a randomized search strategy is thus measured by its competitive ratio, that is, the ratio of the expected meeting time and the earliest possible meeting time (half the initial distance). We present a class of successively refined randomized search strategies together with a rigorous mathematical analysis of their continuously improved competitive ratios. These strategies all rely on the basic idea of performing an infinite sequence of steps of geometrically increasing size in random directions, always returning to the agent's initial position before starting the next step. In addition, our more refined strategies use two novel ideas. First, remembering their past random choices, the agents randomly choose the direction of the next step in a Markov-chain-like manner. Second, choosing the next few random directions in advance, each agent may combine consecutive steps in the same direction into one longer step. As our main result, we show that this combination of looking into the past as well as into the future leads to a substantially improved competitive ratio of 13. 93 compared to the previously best known bound of 24. 85 (Ozsoyeller et al. 2013).

AAAI Conference 2022 Conference Paper

Multi-Leader Congestion Games with an Adversary

• Tobias Harks
• Mona Henle
• Max Klimm
• Jannik Matuschke
• Anja Schedel

We study a multi-leader single-follower congestion game where multiple users (leaders) choose one resource out of a set of resources and, after observing the realized loads, an adversary (single-follower) attacks the resources with maximum loads, causing additional costs for the leaders. For the resulting strategic game among the leaders, we show that pure Nash equilibria may fail to exist and therefore, we consider approximate equilibria instead. As our first main result, we show that the existence of a K-approximate equilibrium can always be guaranteed, where K ≈ 1. 1974 is the unique solution of a cubic polynomial equation. To this end, we give a polynomial time combinatorial algorithm which computes a K-approximate equilibrium. The factor K is tight, meaning that there is an instance that does not admit an α-approximate equilibrium for any α < K. Thus α = K is the smallest possible value of α such that the existence of an α-approximate equilibrium can be guaranteed for any instance of the considered game. Secondly, we focus on approximate equilibria of a given fixed instance. We show how to compute efficiently a best approximate equilibrium, that is, with smallest possible α among all α-approximate equilibria of the given instance.

JAIR Journal 2021 Journal Article

Pure Nash Equilibria in Resource Graph Games

• Tobias Harks
• Max Klimm
• Jannik Matuschke

This paper studies the existence of pure Nash equilibria in resource graph games, a general class of strategic games succinctly representing the players’ private costs. These games are defined relative to a finite set of resources and the strategy set of each player corresponds to a set of subsets of resources. The cost of a resource is an arbitrary function of the load vector of a certain subset of resources. As our main result, we give complete characterizations of the cost functions guaranteeing the existence of pure Nash equilibria for weighted and unweighted players, respectively. For unweighted players, pure Nash equilibria are guaranteed to exist for any choice of the players’ strategy space if and only if the cost of each resource is an arbitrary function of the load of the resource itself and linear in the load of all other resources where the linear coefficients of mutual influence of different resources are symmetric. This implies in particular that for any other cost structure there is a resource graph game that does not have a pure Nash equilibrium. For weighted games where players have intrinsic weights and the cost of each resource depends on the aggregated weight of its users, pure Nash equilibria are guaranteed to exist if and only if the cost of a resource is linear in all resource loads, and the linear factors of mutual influence are symmetric, or there is no interaction among resources and the cost is an exponential function of the local resource load. We further discuss the computational complexity of pure Nash equilibria in resource graph games showing that for unweighted games where pure Nash equilibria are guaranteed to exist, it is coNP-complete to decide for a given strategy profile whether it is a pure Nash equilibrium. For general resource graph games, we prove that the decision whether a pure Nash equilibrium exists is Σ p 2 -complete.

SODA Conference 2020 Conference Paper

Complexity and Parametric Computation of Equilibria in Atomic Splittable Congestion Games via Weighted Block Laplacians

• Max Klimm
• Philipp Warode

SODA Conference 2019 Conference Paper

Computing all Wardrop Equilibria parametrized by the Flow Demand

• Max Klimm
• Philipp Warode

SODA Conference 2016 Conference Paper

Undirected Graph Exploration with ⊝(log log n ) Pebbles

• Yann Disser
• Jan Hackfeld
• Max Klimm

We consider the fundamental problem of exploring an undirected and initially unknown graph by an agent with little memory. The vertices of the graph are unlabeled, and the edges incident to a vertex have locally distinct labels. In this setting, it is known that ⊝(log n ) bits of memory are necessary and sufficient to explore any graph with at most n vertices. We show that this memory requirement can be decreased significantly by making a part of the memory distributable in the form of pebbles. A pebble is a device that can be dropped to mark a vertex and can be collected when the agent returns to the vertex. We show that for an agent ℴ (log log n ) distinguishable pebbles and bits of memory are sufficient to explore any bounded-degree graph with at most n vertices. We match this result with a lower bound exhibiting that for any agent with sub-logarithmic memory, Ω(log log n ) distinguishable pebbles are necessary for exploration.

TCS Journal 2015 Journal Article

Improving the H k -bound on the price of stability in undirected Shapley network design games

• Yann Disser
• Andreas Emil Feldmann
• Max Klimm
• Matúš Mihalák

In this article we show that the price of stability of Shapley network design games on undirected graphs with k players is at most k 3 ( k + 1 ) / 2 − k 2 1 + k 3 ( k + 1 ) / 2 − k 2 H k = ( 1 − Θ ( 1 / k 4 ) ) H k, where H k denotes the k-th harmonic number. This improves on the known upper bound of H k, which is also valid for directed graphs but for these, in contrast, is tight. Hence, we give the first non-trivial upper bound on the price of stability for undirected Shapley network design games that is valid for an arbitrary number of players. Our bound is proved by analyzing the price of stability restricted to Nash equilibria that minimize the potential function of the game. We also present a game with k = 3 players in which such a restricted price of stability is 1. 634. This shows that the analysis of Bilò and Bove (2011) [3] is tight. In addition, we give an example for three players that improves the lower bound on the (unrestricted) price of stability to 1. 571.

TARK Conference 2011 Conference Paper

Congestion games with variable demands

• Tobias Harks
• Max Klimm

We initiate the study of congestion games with variable demands where the (variable) demand has to be assigned to exactly one subset of resources. The players’ incentives to use higher demands are stimulated by non-decreasing and concave utility functions. The payoff for a player is defined as the difference between the utility of the demand and the associated cost on the used resources. Although this class of non-cooperative games captures many elements of real-world applications, it has not been studied in this generality, to our knowledge, in the past. We study the fundamental problem of the existence of pure Nash equilibria (PNE for short) in congestion games with variable demands. We call a set of cost functions C consistent if every congestion game with variable demands and cost functions in C possesses a PNE. We say that C is FIP consistent if every such game possesses the α-Finite Improvement Property for every α > 0. Our main results provide a complete characterization of consistency of cost functions revealing structural differences to congestion games with fixed demands (weighted congestion games), where in the latter even inhomogeneously exponential functions are FIP consistent. Finally, we study consistency and FIP consistency of cost functions in a slightly different class of games, where every player experiences the same cost on a resource (uniform cost model). We give a characterization of consistency and FIP consistency showing that only homogeneously exponential functions are consistent while no functions are FIP consistent.