The Price of Routing Unsplittable Flow

DOI10.1145/1060590.1060599zbMath1192.90099OpenAlexW2017227260MaRDI QIDQ5901105

Baruch Awerbuch, Amir Epstein, Yossi Azar

Publication date: 16 August 2010

Published in: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1060590.1060599

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Games involving graphs (91A43) Traffic problems in operations research (90B20) Discrete location and assignment (90B80)

Related Items (88)

Cost-Sharing in Generalised Selfish Routing ⋮ Partition Equilibrium Always Exists in Resource Selection Games ⋮ On the Inefficiency of Equilibria in Linear Bottleneck Congestion Games ⋮ Strong equilibrium in cost sharing connection games ⋮ Coordination mechanisms ⋮ Atomic routing games on maximum congestion ⋮ Tight Bounds for Cost-Sharing in Weighted Congestion Games ⋮ Competitive online multicommodity routing ⋮ The line planning routing game ⋮ The Price of Matching with Metric Preferences ⋮ Greedy distributed optimization of multi-commodity flows ⋮ On Stackelberg Strategies in Affine Congestion Games ⋮ The Curse of Sequentiality in Routing Games ⋮ A game-theoretic algorithm for non-linear single-path routing problems ⋮ A Selective Tour Through Congestion Games ⋮ Collusion in atomic splittable routing games ⋮ The price of anarchy for polynomial social cost ⋮ On a generalized Cournot oligopolistic competition game ⋮ Partition equilibrium always exists in resource selection games ⋮ The quality of equilibria for set packing and throughput scheduling games ⋮ Social context congestion games ⋮ The equivalence of uniform and Shapley value-based cost allocations in a specific game ⋮ The price of anarchy in loss systems ⋮ Equilibria in routing games with edge priorities ⋮ Inefficiency of pure Nash equilibria in series-parallel network congestion games ⋮ Optimal Cost-Sharing in General Resource Selection Games ⋮ The price of anarchy in series-parallel network congestion games ⋮ Exact price of anarchy for weighted congestion games with two players ⋮ Unnamed Item ⋮ Local and global price of anarchy of graphical games ⋮ Convergence to approximate Nash equilibria in congestion games ⋮ The strong price of anarchy of linear bottleneck congestion games ⋮ On the performance of approximate equilibria in congestion games ⋮ Smart routing of electric vehicles for load balancing in smart grids ⋮ Efficiency analysis of load balancing games with and without activation costs ⋮ Graphical congestion games ⋮ Convergence and approximation in potential games ⋮ Pairwise cooperations in selfish ring routing for minimax linear latency ⋮ Congestion games with failures ⋮ Tight bounds for selfish and greedy load balancing ⋮ Performance of one-round walks in linear congestion games ⋮ Stability vs. optimality in selfish ring routing ⋮ On best response dynamics in weighted congestion games with polynomial delays ⋮ Non-atomic one-round walks in congestion games ⋮ Design of price mechanisms for network resource allocation via price of anarchy ⋮ Scheduling to maximize participation ⋮ Computation and efficiency of potential function minimizers of combinatorial congestion games ⋮ Restoring Pure Equilibria to Weighted Congestion Games ⋮ A new model for selfish routing ⋮ Selfish routing with incomplete information ⋮ Nash equilibria in discrete routing games with convex latency functions ⋮ Colocating tasks in data centers using a side-effects performance model ⋮ The impact of social ignorance on weighted congestion games ⋮ Non-cooperative facility location and covering games ⋮ How to find Nash equilibria with extreme total latency in network congestion games? ⋮ Stackelberg strategies and collusion in network games with splittable flow ⋮ The price of atomic selfish ring routing ⋮ Congestion games with priority-based scheduling ⋮ Stackelberg strategies for atomic congestion games ⋮ Congestion games with linearly independent paths: convergence time and price of anarchy ⋮ Competitive routing over time ⋮ Malicious Bayesian Congestion Games ⋮ Stackelberg Strategies and Collusion in Network Games with Splittable Flow ⋮ A unifying tool for bounding the quality of non-cooperative solutions in weighted congestion games ⋮ Equilibrium strategies for multiple interdictors on a common network ⋮ Scheduling to Maximize Participation ⋮ Network Games with Quantum Strategies ⋮ Network design with weighted players ⋮ Decentralized utilitarian mechanisms for scheduling games ⋮ On the Existence of Pure Nash Equilibria in Weighted Congestion Games ⋮ Nonadaptive Selfish Routing with Online Demands ⋮ The Influence of Link Restrictions on (Random) Selfish Routing ⋮ Congestion Games with Linearly Independent Paths: Convergence Time and Price of Anarchy ⋮ Atomic Congestion Games: Fast, Myopic and Concurrent ⋮ The Local and Global Price of Anarchy of Graphical Games ⋮ The sequential price of anarchy for affine congestion games with few players ⋮ Unnamed Item ⋮ On the Robustness of the Approximate Price of Anarchy in Generalized Congestion Games ⋮ Efficiency of Equilibria in Uniform Matroid Congestion Games ⋮ Efficient graph topologies in network routing games ⋮ Management of Variable Data Streams in Networks ⋮ Efficiency of atomic splittable selfish routing with polynomial cost functions ⋮ How hard is it to find extreme Nash equilibria in network congestion games? ⋮ On Stackelberg strategies in affine congestion games ⋮ On the Price of Anarchy of cost-sharing in real-time scheduling systems ⋮ Atomic congestion games with random players: network equilibrium and the price of anarchy ⋮ Non-blind strategies in timed network congestion games ⋮ On the sequential price of anarchy of isolation games

This page was built for publication: The Price of Routing Unsplittable Flow