Exact Price of Anarchy for Weighted Congestion Games with Two Players

Joran van den Bosse, Marc Uetz, Matthias Walter*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

49 Downloads (Pure)

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’ 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 languageEnglish
Title of host publicationCombinatorial Optimization
Subtitle of host publication7th International Symposium, ISCO 2022, Virtual Event, May 18–20, 2022, Revised Selected Papers
EditorsIvana Ljubić, Francisco Barahona, Santanu S. Dey, A. Ridha Mahjoub
Place of PublicationCham
PublisherSpringer
Pages159-171
Number of pages13
ISBN (Electronic)978-3-031-18530-4
ISBN (Print)978-3-031-18529-8
DOIs
Publication statusPublished - 2022
Event7th International Symposium on Combinatorial Optimization, ISCO 2022 - Virtual, Online
Duration: 18 May 202220 May 2022
Conference number: 7

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume13526
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference7th International Symposium on Combinatorial Optimization, ISCO 2022
Abbreviated titleISCO 2022
CityVirtual, Online
Period18/05/2220/05/22

Keywords

  • 2023 OA procedure

Fingerprint

Dive into the research topics of 'Exact Price of Anarchy for Weighted Congestion Games with Two Players'. Together they form a unique fingerprint.

Cite this