@inproceedings{ae6cab6cbf8e4db0a4fb87f696906a6b,
title = "Exact Price of Anarchy for Weighted Congestion Games with Two Players",
abstract = "This paper gives a complete analysis of worst-case equilibria for various versions of weighted congestion games with two players and affine cost functions. The results are exact price of anarchy bounds, which are parametric in the weights of the two players, and establish exactly how the attributes of the game enter into the quality of equilibria. Interestingly, some of the worst-cases are attained when the players{\textquoteright} weights only differ slightly. Our findings also show that sequential play improves the price of anarchy in all cases, however, this effect vanishes with an increasing difference in the players{\textquoteright} weights. Methodologically, we obtain exact price of anarchy bounds by a duality-based proof mechanism, based on a compact linear programming formulation that computes worst-case instances. This mechanism yields duality-based optimality certificates, which can eventually be turned into purely algebraic proofs.",
keywords = "2023 OA procedure",
author = "{van den Bosse}, Joran and Marc Uetz and Matthias Walter",
note = "Publisher Copyright: {\textcopyright} 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.; 7th International Symposium on Combinatorial Optimization, ISCO 2022 ; Conference date: 18-05-2022 Through 20-05-2022",
year = "2022",
doi = "10.1007/978-3-031-18530-4_12",
language = "English",
isbn = "978-3-031-18529-8",
series = "Lecture Notes in Computer Science",
publisher = "Springer Science + Business Media",
pages = "159--171",
editor = "Ivana Ljubi{\'c} and Francisco Barahona and Dey, {Santanu S.} and Mahjoub, {A. Ridha}",
booktitle = "Combinatorial Optimization",
address = "United States",
}