Tight bounds for selfish and greedy load balancing

DOI10.1007/s00453-010-9427-8zbMath1237.91049OpenAlexW2041462779MaRDI QIDQ644806

Panagiotis Kanellopoulos, Luca Moscardelli, Christos Kaklamanis, Michele Flammini, Ioannis Caragiannis

Publication date: 7 November 2011

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.727.1152

zbMATH Keywords

online algorithmscongestion gamesload balancingprice of anarchyprice of stability

Mathematics Subject Classification ID

Noncooperative games (91A10) Games involving graphs (91A43) Other game-theoretic models (91A40) Online algorithms; streaming algorithms (68W27)

Related Items (35)

Unnamed Item ⋮ On Stackelberg Strategies in Affine Congestion Games ⋮ A Selective Tour Through Congestion Games ⋮ On the performance of mildly greedy players in cut games ⋮ Social context congestion games ⋮ Reducing price of anarchy of selfish task allocation with more selfishness ⋮ Price of anarchy for parallel link networks with generalized mean objective ⋮ Inefficiency of pure Nash equilibria in series-parallel network congestion games ⋮ The power of one evil secret agent ⋮ Scheduling games with rank-based utilities ⋮ Using Temporal Dummy Players in Cost-Sharing Games ⋮ Exact price of anarchy for weighted congestion games with two players ⋮ Unnamed Item ⋮ The price of stability for undirected broadcast network design with fair cost allocation is constant ⋮ Tight Bounds for Online Vector Scheduling ⋮ On approximate pure Nash equilibria in weighted congestion games with polynomial latencies ⋮ Non-atomic one-round walks in congestion games ⋮ Computation and efficiency of potential function minimizers of combinatorial congestion games ⋮ The impact of social ignorance on weighted congestion games ⋮ Congestion games with priority-based scheduling ⋮ A unifying tool for bounding the quality of non-cooperative solutions in weighted congestion games ⋮ The price of anarchy of affine congestion games with similar strategies ⋮ Load rebalancing games in dynamic systems with migration costs ⋮ Decentralized utilitarian mechanisms for scheduling games ⋮ Unnamed Item ⋮ Cost-sharing games in real-time scheduling systems ⋮ Greedy is optimal for online restricted assignment and smart grid scheduling for unit size jobs ⋮ Cost-sharing games in real-time scheduling systems ⋮ On Approximate Pure Nash Equilibria in Weighted Congestion Games with Polynomial Latencies ⋮ On Stackelberg strategies in affine congestion games ⋮ The Price of Stability of Weighted Congestion Games ⋮ The Price of Stability of Weighted Congestion Games ⋮ Some anomalies of farsighted strategic behavior ⋮ On the sequential price of anarchy of isolation games ⋮ Performance guarantees of local search for minsum scheduling problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The structure and complexity of Nash equilibria for a selfish routing game
• The price of anarchy for polynomial social cost
• Selfish load balancing and atomic congestion games
• A new model for selfish routing
• Nash equilibria in discrete routing games with convex latency functions
• The price of selfish routing
• Approximation schemes for scheduling on parallel machines
• Approximate equilibria and ball fusion
• Potential games
• Bounding the inefficiency of equilibria in nonatomic congestion games
• A class of games possessing pure-strategy Nash equilibria
• Selfish unsplittable flows
• How bad is selfish routing?
• The Price of Stability for Network Design with Fair Cost Allocation
• The complexity of pure Nash equilibria
• Convex programming for scheduling unrelated parallel machines
• The price of anarchy of finite congestion games
• Network Games with Atomic Players
• Worst-Case Analysis of a Placement Algorithm Related to Storage Allocation
• Record Allocation for Minimizing Expected Retrieval Costs on Drum-Like Storage Devices
• Scheduling Parallel Machines On-Line
• Algorithms, games, and the internet
• Online load balancing and network flow
• Exact Price of Anarchy for Polynomial Congestion Games
• Convergence and Approximation in Potential Games
• Algorithms – ESA 2005
• Computing Nash equilibria for scheduling on restricted parallel links
• The Price of Routing Unsplittable Flow
• Ancient and new algorithms for load balancing in the \(\ell_p\) norm

This page was built for publication: Tight bounds for selfish and greedy load balancing