Approximate strong equilibria in job scheduling games with two uniformly related machines

DOI10.1016/j.dam.2013.02.035zbMath1287.90022OpenAlexW1990100369MaRDI QIDQ2446828

Tami Tamir, Michal Feldman, Leah Epstein, Marcin Witkowski, Łukasz Witkowski

Publication date: 22 April 2014

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2013.02.035

zbMATH Keywords

schedulinggamesapproximate strong Nash equilibrium

Mathematics Subject Classification ID

2-person games (91A05) Applications of game theory (91A80) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Strong stability of Nash equilibria in load balancing games
• Equilibria for two parallel links: the strong price of anarchy versus the price of anarchy
• Strong equilibrium in cost sharing connection games
• The structure and complexity of Nash equilibria for a selfish routing game
• Coordination mechanisms
• Strong price of anarchy
• Equilibria in load balancing games
• Strong equilibrium in congestion games
• Network structure and strong equilibrium in route selection games.
• Crowding games are sequentially solvable
• New approximation bounds for LPT scheduling
• Performance Guarantees of Local Search for Multiprocessor Scheduling
• Tight bounds for worst-case equilibria
• How bad is selfish routing?
• Scheduling Independent Tasks on Uniform Processors
• Approximate Strong Equilibrium in Job Scheduling Games
• On the Value of Coordination in Network Design
• Tighter Bounds for LPT Scheduling on Uniform Processors
• Bounds for List Schedules on Uniform Processors
• Exact and Approximate Algorithms for Scheduling Nonidentical Processors
• Bounds for LPT Schedules on Uniform Processors
• A Parametric Worst Case Analysis of the LPT Heuristic for Two Uniform Machines
• On-line routing of virtual circuits with applications to load balancing and machine scheduling
• All-norm approximation algorithms
• Algorithms, games, and the internet
• Network formation games with local coalitions
• Strong Price of Anarchy for Machine Load Balancing
• Bounds for Certain Multiprocessing Anomalies
• Bounds on Multiprocessing Timing Anomalies
• Randomized on-line scheduling on two uniform machines

This page was built for publication: Approximate strong equilibria in job scheduling games with two uniformly related machines