Congestion games with complementarities

DOI10.1007/978-3-319-57586-5_19MaRDI QIDQ5283369zbMATH OpenOpenAlexFDO

Authors Matthias Feldotto, Lennart Leder, Alexander Skopalik

Publication date 21 July 2017

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

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

zbMATH Keywords

aggregationcomplementaritiescongestion gamesexistence of equilibria\(L_p\) normsapproximate pure Nash equilibria

Mathematics Subject Classification ID

Potential and congestion games (91A14)

Abstract: We study a model of selfish resource allocation that seeks to incorporate dependencies among resources as they exist in modern networked environments. Our model is inspired by utility functions with constant elasticity of substitution (CES) which is a well-studied model in economics. We consider congestion games with different aggregation functions. In particular, we study $L_p$ norms and analyze the existence and complexity of (approximate) pure Nash equilibria. Additionally, we give an almost tight characterization based on monotonicity properties to describe the set of aggregation functions that guarantee the existence of pure Nash equilibria.

Recommendations

• Games with congestion-averse utilities
• Congestion games with capacitated resources
• Congestion games with capacitated resources
• Congestion games with variable demands
• Efficiency Loss in a Network Resource Allocation Game

Cites work

• scientific article; zbMATH DE number 5485547 (Why is no real title available?)
• A class of games possessing pure-strategy Nash equilibria
• Approximate pure Nash equilibria in weighted congestion games
• Bounding the potential function in congestion games and approximate pure Nash equilibria
• Combinatorial Optimization. Polyhedra and efficiency. CD-ROM
• Complexity of pure Nash equilibria in player-specific network congestion games
• Computing pure Nash and strong equilibria in bottleneck congestion games
• Congestion Games with Mixed Objectives
• Congestion Games with Player-Specific Constants
• Congestion games revisited
• Congestion games with player-specific payoff functions
• Convergence to approximate Nash equilibria in congestion games
• Efficient computation of approximate pure Nash equilibria in congestion games
• Games with congestion-averse utilities
• Intrinsic robustness of the price of anarchy
• On the complexity of pure-strategy Nash equilibria in congestion and local-effect games
• On the impact of combinatorial structure on congestion games
• On the performance of approximate equilibria in congestion games
• Potential games
• Pure Nash equilibria in player-specific and weighted congestion games
• Selfish unsplittable flows
• The complexity of pure Nash equilibria
• Worst-case equilibria

Cited in

(14)

• Congestion games with multisets of resources and applications in synthesis
• Congestion games with variable demands
• Congestion games with capacitated resources
• Transfer implementation in congestion games
• Congestion games with capacitated resources
• Budgeted personalized incentive approaches for smoothing congestion in resource networks
• Congestion Games with Multi-Dimensional Demands
• Efficiency Loss in a Network Resource Allocation Game
• Pure Nash equilibria in weighted matroid congestion games with non-additive aggregation and beyond
• Competitive Resource Allocation Among Urban Congestion Areas in a Modern Big City
• A unified approach to congestion games and two-sided markets
• Congestion games revisited
• A common generalization of budget games and congestion games
• Congestion Games with Mixed Objectives

This page was built for publication: Congestion games with complementarities

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