On the Impact of Combinatorial Structure on Congestion Games

No abstract is available for this paper.

• Publication year

  2006

• Venue

  IEEE Annual Symposium on Foundations of Computer Science

• Publication date

  2006-10-21

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/1455248.1455249
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Introduction

  2006cited by this paper
• Pure Nash Equilibria in Player-Specific and Weighted Congestion Games

  2006cited by this paper
• Fast and Compact: A Simple Class of Congestion Games

  2005cited by this paper
• Fairness and optimality in congestion games

  2005cited by this paper
• Approximation algorithms for distributed and selfish agents

  2005cited by this paper
• Internet indirection infrastructure

  2004cited by this paper
• Market sharing games applied to content distribution in ad hoc networks

  2004cited by this paper
• The price of stability for network design with fair cost allocation

  2004cited by this paper
• The complexity of pure Nash equilibria

  2004cited by this paper
• Combinatorial optimization. Polyhedra and efficiency.

  2003cited by this paper
• Near-optimal network design with selfish agents

  2003cited by this paper
• Internet indirection infrastructure

  2002cited by this paper
• Finding minimum congestion spanning trees

  1999cited by this paper
• Computing with Truly Asynchronous Threshold Logic Networks

  1997cited by this paper
• Integer Linear Programs and Local Search for Max-Cut

  1995cited by this paper
• Complexity Issues in Discrete Hopfield Networks

  1994cited by this paper
• Simple Local Search Problems That are Hard to Solve

  1991cited by this paper
• How Easy is Local Search?

  1985cited by this paper
• A class of games possessing pure-strategy Nash equilibria

  1973cited by this paper
• and as an in

  year unknowncited by this paper

• Price of Anarchy in Paving Matroid Congestion Games

  2026cites this paper
• Game-Theoretic and Algorithmic Analyses of Multi-Agent Routing under Crossing Costs

  2026influential citation
• PLS-complete problems with lexicographic cost functions: Max-k-SAT and Abelian Permutation Orbit Minimization

  2025cites this paper
• Computing approximate pure Nash equilibria for weighted congestion games

  2025cites this paper
• Efficient Kernelized Learning in Polyhedral Games Beyond Full-Information: From Colonel Blotto to Congestion Games

  2025cites this paper
• Efficiently Computing Equilibria in Budget-Aggregation Games

  2025cites this paper
• Pure and Strong Nash Equilibrium Computation in Compactly Representable Aggregate Games

  2025cites this paper
• On the Performance of Mildly Greedy Players in k-Coloring Games

  2025cites this paper
• Centralised Decision Support in Maritime Vessel Traffic Services: A Polymatrix Game Solution

  2025cites this paper
• Complexity and Parametric Computation of Equilibria in Atomic Splittable Congestion Games via Weighted Block Laplacians

  2025cites this paper
• On Green Sustainability of Resource Selection Games with Equitable Cost-Sharing

  2024cites this paper
• Nash Equilibria in Two-Resource Congestion Games with Player-Specific Payoff Functions

  2024cites this paper
• Minimizing Rosenthal's Potential in Monotone Congestion Games

  2024cites this paper
• A Unified Model of Congestion Games with Priorities: Two-Sided Markets with Ties, Finite and Non-Affine Delay Functions, and Pure Nash Equilibria

  2024influential citation
• Facility Assignment with Fair Cost Sharing: Equilibrium and Mechanism Design

  2024cites this paper
• Timed Network Games

  2023cites this paper
• Joint Task Offloading and Resource Allocation in Aerial-Terrestrial UAV Networks With Edge and Fog Computing for Post-Disaster Rescue

  2023cites this paper
• Approximate Nash Equilibria Algorithms for Shapley Network Design Games

  2023cites this paper
• Subproject A3: The Market for Services: Incentives, Algorithms, Implementation

  2023cites this paper
• Pure Nash Equilibria in a Generalization of Congestion Games Allowing Resource Failures

  2023cites this paper
• The Complexity of Optimizing Atomic Congestion

  2023cites this paper
• A Smoothed FPTAS for Equilibria in Congestion Games

  2023influential citation
• Complexity of equilibria in binary public goods games on undirected graphs

  2023cites this paper
• The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich

  2022cites this paper
• Project Games

  2022cites this paper
• The price of Anarchy in series-parallel network congestion games

  2022cites this paper
• Computing Better Approximate Pure Nash Equilibria in Cut Games via Semidefinite Programming

  2022cites this paper
• Equilibria in Multiclass and Multidimensional Atomic Congestion Games

  2022cites this paper
• On the Smoothed Complexity of Combinatorial Local Search

  2022cites this paper
• Sampling Equilibria: Fast No-Regret Learning in Structured Games

  2022cites this paper
• On the Impact of Player Capability on Congestion Games

  2022cites this paper
• On the Impact of Singleton Strategies in Congestion Games

  2022cites this paper
• $\frac{\rho}{1-\epsilon}$-approximate pure Nash equilibria algorithms for weighted congestion games and their runtimes

  2022influential citation
• ScholarlyCommons ScholarlyCommons

  2021cites this paper
• The Competitive Pickup and Delivery Orienteering Problem for Balancing Car-Sharing Systems

  2021cites this paper
• Sampling from the Gibbs Distribution in Congestion Games

  2021cites this paper
• On Sharding Open Blockchains with Smart Contracts

  2020cites this paper
• Theory and Applications of Models of Computation: 16th International Conference, TAMC 2020, Changsha, China, October 18–20, 2020, Proceedings

  2020cites this paper
• Pure Nash Equilibria in Resource Graph Games

  2020cites this paper
• Improving approximate pure Nash equilibria in congestion games

  2020cites this paper
• Communication complexity of Nash equilibrium in potential games (extended abstract)

  2020cites this paper
• Settling the complexity of Nash equilibrium in congestion games

  2020cites this paper
• Existence and Complexity of Approximate Equilibria in Weighted Congestion Games

  2020cites this paper
• Node-Max-Cut and the Complexity of Equilibrium in Linear Weighted Congestion Games

  2020cites this paper
• Complexity and Approximability of Optimal Resource Allocation and Nash Equilibrium over Networks

  2020cites this paper
• Algorithmic Game Theory: 13th International Symposium, SAGT 2020, Augsburg, Germany, September 16–18, 2020, Proceedings

  2020cites this paper
• Equilibrium Inefficiency in Resource Buying Games with Load-Dependent Costs

  2020cites this paper
• Nash Social Welfare in Selfish and Online Load Balancing

  2020cites this paper
• Optimal matroid bases with intersection constraints: valuated matroids, M-convex functions, and their applications

  2020cites this paper
• Computation and efficiency of potential function minimizers of combinatorial congestion games

  2020cites this paper
• Leadership in Congestion Games: Multiple User Classes and Non-Singleton Actions (Extended Version)

  2019cites this paper
• Wireless and Computing Resource Allocation for Selfish Computation Offloading in Edge Computing

  2019cites this paper
• Generalizations of weighted matroid congestion games: pure Nash equilibrium, sensitivity analysis, and discrete convex function

  2019cites this paper
• Decentralized beneficiary behavior in humanitarian supply chains: models, performance bounds, and coordination mechanisms

  2019cites this paper
• Optimal Price of Anarchy in Cost-Sharing Games

  2019cites this paper
• When Nash met Markov: Novel results for pure Nash equilibria and the switch Markov chain

  2019influential citation
• Coordination Games on Weighted Directed Graphs

  2019cites this paper
• Node Max-Cut and Computing Equilibria in Linear Weighted Congestion Games

  2019cites this paper
• Pricing in Resource Allocation Games Based on Duality Gaps

  2019cites this paper
• Combinatorial optimization with interaction costs: Complexity and solvable cases

  2019cites this paper
• Joint Management of Wireless and Computing Resources for Computation Offloading in Mobile Edge Clouds

  2019cites this paper
• Uniqueness and computation of equilibria in resource allocation games

  2019cites this paper
• Approximate pure nash equilibria in congestion, opinion formation and facility location games

  2019cites this paper
• Dynamic Taxes for Polynomial Congestion Games

  2019cites this paper
• Pricing in Resource Allocation Games Based on Lagrangean Duality and Convexification.

  2019cites this paper
• Computing Equilibria in Congestion Games

  2018cites this paper
• Cost-sharing games in real-time scheduling systems

  2018cites this paper
• Distributed control and game design: From strategic agents to programmable machines

  2018cites this paper
• The Price of Stability of Weighted Congestion Games

  2018influential citation
• Approximation Algorithms in Allocation, Scheduling and Pricing

  2018cites this paper
• An Improved Algorithm for Computing Approximate Equilibria in Weighted Congestion Games

  2018cites this paper
• Efficient Estimation of Equilibria of Large Congestion Games with Heterogeneous Players

  2018cites this paper
• G T ] 8 A ug 2 01 8 Equilibrium Computation in Resource Allocation Games

  2018cites this paper
• Utility Design for Distributed Resource Allocation—Part II: Applications to Submodular, Covering, and Supermodular Problems

  2018cites this paper
• Complexity and Parametric Computation of Equilibria in Atomic Splittable Congestion Games via Weighted Block Laplacians

  2018influential citation
• Computing Approximate Equilibria in Weighted Congestion Games via Best-Responses

  2018cites this paper
• Equilibrium Computation in Atomic Splittable Routing Games with Convex Cost Functions

  2018cites this paper
• Leadership in Singleton Congestion Games

  2018cites this paper
• Distributed resource allocation through utility design - Part II: applications to submodular, supermodular and set covering problems

  2018influential citation
• Computing Equilibria in Atomic Splittable Polymatroid Congestion Games with Convex Costs

  2018cites this paper
• Leadership in Singleton Congestion Games: What is Hard and What is Easy

  2018cites this paper
• Potential Function Minimizers of Combinatorial Congestion Games: Efficiency and Computation

  2017influential citation
• Computing Approximate Pure Nash Equilibria in Shapley Value Weighted Congestion Games

  2017influential citation
• Congestion Games with Complementarities

  2017cites this paper
• Network Movement Games

  2017cites this paper
• Price of anarchy and an approximation algorithm for the binary-preference capacitated selfish replication game

  2017cites this paper
• Smoothed Analysis of Local Search for the Maximum-Cut Problem

  2017cites this paper
• Brief Announcement: Approximation Algorithms for Unsplittable Resource Allocation Problems with Diseconomies of Scale

  2017cites this paper
• Combinatorial Optimization Problems with Interaction Costs: Complexity and Solvable Cases

  2017cites this paper
• Finding equilibria in linear service-providing games

  2016cites this paper
• Efficient Local Search in Coordination Games on Graphs

  2016cites this paper
• Congestion games with mixed objectives

  2016cites this paper
• Equilibrium Computation in Atomic Splittable Singleton Congestion Games

  2016cites this paper
• Best-Response Dynamics in Combinatorial Auctions with Item Bidding

  2016cites this paper
• Algorithmic, Game Theoretic and Learning Theoretic Aspects of Distributed Optimization

  2016cites this paper
• The Complexity of Coordination

  2016cites this paper
• A logarithmic approximation for polymatroid congestion games

  2016cites this paper
• Complexity and Optimality of the Best Response Algorithm in Random Potential Games

  2016cites this paper
• Quality of equilibria in resource allocation games

  2016cites this paper
• Multi-user computation offloading as Multiple Knapsack Problem for 5G Mobile Edge Computing

  2016cites this paper