Approximate Strong Equilibrium in Job Scheduling Games

DOI10.1007/978-3-540-79309-0_7zbMATH Open1136.91334arXiv1401.3494OpenAlexW1676535044MaRDI QIDQ5459972FDOQ5459972

Michal Feldman, Tami Tamir

Publication date: 2 May 2008

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

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.

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)

Cites Work

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

Cited In (7)

• Multitask \(n\)-vehicle exploration problem: complexity and algorithm
• 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
• On the stability analysis of switched nonlinear systems with time varying delay under arbitrary switching
• 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)