Exact price of anarchy for weighted congestion games with two players

DOI10.1007/978-3-031-18530-4_12zbMATH Open1528.91002arXiv2203.01740MaRDI QIDQ6166899FDOQ6166899

Authors: Joran van den Bosse, Marc Uetz, Matthias Walter 

Publication date: 3 August 2023

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

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 primitives 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.

Full work available at URL: https://arxiv.org/abs/2203.01740

Recommendations

• Exact price of anarchy for polynomial congestion games
• Weighted congestion games: price of anarchy, universal worst-case examples, and tightness
• The sequential price of anarchy for affine congestion games with few players
• Exact Price of Anarchy for Polynomial Congestion Games
• The price of stability of weighted congestion games

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Applications of game theory (91A80) Noncooperative games (91A10) (n)-person games, (n>2) (91A06) Games involving graphs (91A43)

Cites Work

• Non-cooperative games
• Equilibrium points in n -person games
• Worst-case equilibria
• The price of anarchy is independent of the network topology
• A simple model of imperfect competition where 4 are few and 6 are many
• A class of games possessing pure-strategy Nash equilibria
• Potential games
• Game Theory
• Selfish unsplittable flows
• On the existence of pure Nash equilibria in weighted congestion games
• Congestion games with player-specific payoff functions
• The price of anarchy of finite congestion games
• Tight bounds for selfish and greedy load balancing
• Routing (Un-) Splittable Flow in Games with Player-Specific Linear Latency Functions
• The curse of simultaneity
• The price of routing unsplittable flow
• Some anomalies of farsighted strategic behavior
• A unifying tool for bounding the quality of non-cooperative solutions in weighted congestion games
• Algorithms for pure Nash equilibria in weighted congestion games
• A new model for selfish routing
• The sequential price of anarchy for atomic congestion games
• Congestion games with variable demands
• The inefficiency of Nash and subgame perfect equilibria for network routing
• Iterative refinement for linear programming
• The sequential price of anarchy for affine congestion games with few players
• Exact price of anarchy for weighted congestion games with two players

Cited In (1)

• Exact price of anarchy for weighted congestion games with two players

This page was built for publication: Exact price of anarchy for weighted congestion games with two players

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6166899)