Exact price of anarchy for weighted congestion games with two players

DOI10.1007/978-3-031-18530-4_12MaRDI QIDQ6166899zbMATH OpenFDO

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)

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

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)

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.

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

Cites work

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

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)