Approximate Strong Equilibrium in Job Scheduling Games

DOI10.1007/978-3-540-79309-0_7MaRDI QIDQ5459972zbMATH OpenOpenAlexFDO

Authors Michal Feldman, Tami Tamir

Publication date 2 May 2008

Published in Algorithmic Game Theory (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Other game-theoretic models (91A40)

Abstract: A Nash Equilibrium (NE) is a strategy profile resilient to unilateral deviations, and is predominantly used in the analysis of multiagent systems. A downside of NE is that it is not necessarily stable against deviations by coalitions. Yet, as we show in this paper, in some cases, NE does exhibit stability against coalitional deviations, in that the benefits from a joint deviation are bounded. In this sense, NE approximates strong equilibrium. Coalition formation is a key issue in multiagent systems. We provide a framework for quantifying the stability and the performance of various assignment policies and solution concepts in the face of coalitional deviations. Within this framework we evaluate a given configuration according to three measures: (i) IR_min: the maximal number alpha, such that there exists a coalition in which the minimal improvement ratio among the coalition members is alpha, (ii) IR_max: the maximal number alpha, such that there exists a coalition in which the maximal improvement ratio among the coalition members is alpha, and (iii) DR_max: the maximal possible damage ratio of an agent outside the coalition. We analyze these measures in job scheduling games on identical machines. In particular, we provide upper and lower bounds for the above three measures for both NE and the well-known assignment rule Longest Processing Time (LPT). Our results indicate that LPT performs better than a general NE. However, LPT is not the best possible approximation. In particular, we present a polynomial time approximation scheme (PTAS) for the makespan minimization problem which provides a schedule with IR_min of 1+epsilon for any given epsilon. With respect to computational complexity, we show that given an NE on m >= 3 identical machines or m >= 2 unrelated machines, it is NP-hard to determine whether a given coalition can deviate such that every member decreases its cost.

Recommendations

• Approximate strong equilibrium in job scheduling games
• Approximate strong equilibria in job scheduling games with two uniformly related machines
• Strong stability of Nash equilibria in load balancing games
• Equilibria in load balancing games
• Strong price of anarchy

Cites work

• 5th conference on optimization techniques. Part II
• A linear time approximation algorithm for multiprocessor scheduling
• Algorithms – ESA 2005
• Algorithms, games, and the internet
• Approximate Strong Equilibrium in Job Scheduling Games
• Approximation and Online Algorithms
• Automata, Languages and Programming
• Bounds on Multiprocessing Timing Anomalies
• Coalition-proof Nash equilibria. I: Concepts
• Crowding games are sequentially solvable
• How bad is selfish routing?
• scientific article; zbMATH DE number 5764884 (Why is no real title available?)
• scientific article; zbMATH DE number 1757968 (Why is no real title available?)
• scientific article; zbMATH DE number 2119691 (Why is no real title available?)
• Near-optimal network design with selfish agents
• Network formation games with local coalitions
• Network structure and strong equilibrium in route selection games.
• On a network creation game
• On nash equilibria for a network creation game
• Strong equilibrium in congestion games
• Strong equilibrium in cost sharing connection games
• Strong price of anarchy
• Strong Price of Anarchy for Machine Load Balancing
• The Price of Stability for Network Design with Fair Cost Allocation
• Worst-case equilibria

Cited in

(10)

• Equilibria in load balancing games
• On the stability analysis of switched nonlinear systems with time varying delay under arbitrary switching
• Approximate strong equilibria in job scheduling games with two uniformly related machines
• Optimal Coordination Mechanisms for Multi-job Scheduling Games
• Pareto efficiency and approximate Pareto efficiency in routing and load balancing games
• Approximate strong equilibrium in job scheduling games
• Multitask n-vehicle exploration problem: complexity and algorithm
• Strong stability of Nash equilibria in load balancing games
• Approximate Strong Equilibrium in Job Scheduling Games
• Selfish bin covering

This page was built for publication: Approximate Strong Equilibrium in Job Scheduling Games

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