Multi-Leader Congestion Games with an Adversary
Authors: Tobias Harks, Mona Henle, Max Klimm, Jannik Matuschke, Anja Schedel
JAIR 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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 alfa-approximate equilibrium with the smallest possible factor alfa Kfor a given instance, in particular finding an exact equilibrium if one exists. |
| Researcher Affiliation | Academia | TOBIAS HARKS, University of Passau, Germany MONA HENLE , University of Applied Sciences Augsburg, Germany MAX KLIMM, TU Berlin, Germany JANNIK MATUSCHKE, Research Center for Operations Management, KU Leuven, Belgium ANJA SCHEDEL, University of Passau, Germany |
| Pseudocode | Yes | Algorithm 1: Computation of an a-approximate PNE. Input: Player set N= [n], resource set R= {r1, . . . ,rm}, resource cost coefficients 0 a1 am, budget B> 0, and a 1. Output: a-approximate pure Nash equilibrium x. 1 x (0, 0, . . . , 0); 2 for k= 1, 2, . . . ,ndo 3 t min{t [m] : crt(rt,x k) cr(r,x k) r R}; 4 xt rt; 5 while Wa(x) do 6 Ra(x) {r R: xi= rfor some i Wa(x)}; 7 t max{t [m] : rt Ra(x) and crt(x) cr(x) r Ra(x)}; 8 i some player with xi= rt ; 9 t+ min{t [m] : crt(rt,x i) cr(r,x i) r R}; 10 xi rt+; 11 return x; |
| Open Source Code | No | The paper does not contain any explicit statements about the release of source code for the methodology described, nor does it provide any links to code repositories. |
| Open Datasets | No | The paper describes theoretical game instances (e.g., Example 4, Example 5) to illustrate concepts and proofs, rather than using empirical datasets for experimentation. Therefore, the concept of 'publicly available datasets' in the traditional sense (e.g., for machine learning models) does not apply. No datasets are mentioned as publicly available for access. |
| Dataset Splits | No | The paper focuses on theoretical analysis and proofs regarding game equilibria. It does not conduct experiments on empirical datasets that would require train/test/validation splits. The 'instances' or 'examples' used are small, constructed scenarios for illustrating theoretical points, not for empirical evaluation requiring data splits. |
| Hardware Specification | No | The paper presents theoretical results, including existence proofs and algorithm design, without detailing any empirical experiments or simulations. As such, there is no mention of specific hardware used to run experiments. |
| Software Dependencies | No | The paper describes Algorithm 1 and Algorithm 2 conceptually within a theoretical framework. It does not provide any specific software dependencies or version numbers (e.g., programming languages, libraries, or solvers with version numbers) that would be needed to replicate experimental results, as no empirical experiments are detailed. |
| Experiment Setup | No | The paper is theoretical in nature, focusing on mathematical proofs, algorithm design, and game theory concepts. It does not describe any empirical experiments, and therefore, there are no hyperparameters, training configurations, or system-level settings to detail for an experimental setup. |