Arrow Research search

Author name cluster

Jannik Matuschke

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

6 papers
2 author rows

Possible papers

6

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.

PDF Details DOI

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.

PDF Details

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.

PDF Details DOI

SODA Conference 2015 Conference Paper

Robust randomized matchings

  • Jannik Matuschke
  • Martin Skutella
  • José A. Soto

The following zero-sum game is played on a weighted graph G: Alice selects a matching M in G and Bob selects a number k. Then, Alice receives a payoff equal to the ratio of the weight of the top k edges of M to opt k, which is the maximum weight of a matching of size at most k in G. If M guarantees a payoff of at least α then it is called α-robust. In 2002, Hassin and Rubinstein gave an algorithm that returns a -robust matching, which is best possible for this setting. In this paper, we show that Alice can improve on the guarantee of when allowing her to play a randomized strategy. For this setting, we devise a simple algorithm that returns a 1/ln(4)-robust randomized matching. The algorithm is based on the following non-trivial observation: If all edge weights are integer powers of 2, then any lexicographically optimum matching is 1-robust. We prove this property not only for matchings but for any independence system in which opt k is a concave function of k. This class of systems includes matroid intersection, b -matchings, and strong 2-exchange systems. We also show that our robustness results for randomized matchings translate to an asymptotic robustness guarantee for deterministic matchings: When restricting Bob's choice to cardinalities larger than a given constant, then Alice can find a single deterministic matching with approximately the same guaranteed payoff as in the randomized setting. In addition to the above results, we also give a new simple LP-based proof of Hassin and Rubinstein's original result.

Details