Scheduling games with machine-dependent priority lists

DOI10.1007/978-3-030-35389-6_21zbMATH Open1435.90072arXiv1909.10199OpenAlexW2990205799MaRDI QIDQ5896089FDOQ5896089

Vipin Ravindran Vijayalakshmi, Tami Tamir, Marc Schröder

Publication date: 30 June 2020

Published in: Theoretical Computer Science, Web and Internet Economics (Search for Journal in Brave)

Abstract: We consider a scheduling game on parallel related machines, in which jobs try to minimize their completion time by choosing a machine to be processed on. Each machine uses an individual priority list to decide on the order according to which the jobs on the machine are processed. We prove that it is NP-hard to decide if a pure Nash equilibrium exists and characterize four classes of instances in which a pure Nash equilibrium is guaranteed to exist. For each of these classes, we give an algorithm that computes a Nash equilibrium, we prove that best-response dynamics converge to a Nash equilibrium, and we bound the inefficiency of Nash equilibria with respect to the makespan of the schedule and the sum of completion times. In addition, we show that although a pure Nash equilibrium is guaranteed to exist in instances with identical machines, it is NP-hard to approximate the best Nash equilibrium with respect to both objectives. We finally extend our results to a more general model in which jobs pick subsets of machines.

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

Recommendations

• Scheduling games with machine-dependent priority lists
• Scheduling games with rank-based utilities
• Mixed coordination mechanisms for scheduling games on hierarchical machines
• Scheduling game with machine modification in the random setting
• Coordination mechanisms for scheduling games with machine modification
• A coordination mechanism for a scheduling game with parallel-batching machines
• Scheduling games on uniform machines with activation cost
• Sequential solutions in machine scheduling games
• Classifications, advances and prospects of scheduling games
• Pareto-optimal algorithms for scheduling games on parallel-batching machines with activation cost

zbMATH Keywords

price of anarchyequilibrium inefficiencyscheduling gamespriority lists

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Applications of game theory (91A80) Potential and congestion games (91A14) Algorithmic game theory and complexity (91A68)

Cites Work

• Worst-case equilibria
• A class of games possessing pure-strategy Nash equilibria
• Maximum bounded 3-dimensional matching is MAX SNP-complete
• Tight bounds for worst-case equilibria
• The Price of Stability for Network Design with Fair Cost Allocation
• Bounds for Certain Multiprocessing Anomalies
• Coordination mechanisms for selfish scheduling
• Bounds for List Schedules on Uniform Processors
• Heuristic Algorithms for Scheduling Independent Tasks on Nonidentical Processors
• Nonpreemptive coordination mechanisms for identical machines
• Automata, Languages and Programming
• Title not available (Why is that?)
• Tradeoffs in worst-case equilibria
• Congestion games with capacitated resources
• Computing Nash equilibria for scheduling on restricted parallel links
• Worst-case Nash equilibria in restricted routing
• Title not available (Why is that?)
• Non-clairvoyant scheduling games
• Decentralized utilitarian mechanisms for scheduling games
• Intrinsic Robustness of the Price of Anarchy
• The price of anarchy for utilitarian scheduling games on related machines
• Coordination Mechanisms, Cost-Sharing, and Approximation Algorithms for Scheduling
• Efficiency of equilibria in restricted uniform machine scheduling with total weighted completion time as social cost
• A Unified Approach to Congestion Games and Two-Sided Markets
• Congestion games with priority-based scheduling

Cited In (7)

• Race scheduling games
• Minimizing total completion time with machine-dependent priority lists
• Scheduling games with rank-based utilities
• Scheduling games with machine-dependent priority lists
• Classifications, advances and prospects of scheduling games
• Congestion games with priority-based scheduling
• Integer programming methods to identify Nash equilibrium solutions for platform-based scheduling games

This page was built for publication: Scheduling games with machine-dependent priority lists

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