Research output per year
Research output per year
Joran van den Bosse, Marc Uetz, Matthias Walter*
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review
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’ 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’ 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.
Original language | English |
---|---|
Title of host publication | Combinatorial Optimization |
Subtitle of host publication | 7th International Symposium, ISCO 2022, Virtual Event, May 18–20, 2022, Revised Selected Papers |
Editors | Ivana Ljubić, Francisco Barahona, Santanu S. Dey, A. Ridha Mahjoub |
Place of Publication | Cham |
Publisher | Springer |
Pages | 159-171 |
Number of pages | 13 |
ISBN (Electronic) | 978-3-031-18530-4 |
ISBN (Print) | 978-3-031-18529-8 |
DOIs | |
Publication status | Published - 2022 |
Event | 7th International Symposium on Combinatorial Optimization, ISCO 2022 - Virtual, Online Duration: 18 May 2022 → 20 May 2022 Conference number: 7 |
Name | Lecture Notes in Computer Science |
---|---|
Publisher | Springer |
Volume | 13526 |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference | 7th International Symposium on Combinatorial Optimization, ISCO 2022 |
---|---|
Abbreviated title | ISCO 2022 |
City | Virtual, Online |
Period | 18/05/22 → 20/05/22 |
Research output: Working paper › Preprint › Academic