Inefficiency of the Nash equilibrium for selfish machine covering on two hierarchical uniform machines

DOI10.1016/J.IPL.2015.06.005MaRDI QIDQ2353644zbMATH OpenOpenAlexFDO

Authors Yong Wu, Min Ji, T. C. Edwin Cheng

Publication date 15 July 2015

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2015.06.005

zbMATH Keywords

hierarchyNash equilibriumprice of anarchyprice of stabilityscheduling

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Noncooperative games (91A10) Hierarchical games (including Stackelberg games) (91A65)

Recommendations

• Inefficiency of equilibria for the machine covering game on uniform machines
• Efficiency of dual equilibria in selfish task allocation to selfish machines
• The cost of selfishness for maximizing the minimum load on uniformly related machines
• Bounding the inefficiency of Nash equilibria in games with finitely many players
• Tighter price of anarchy for selfish task allocation on selfish machines
• Inapproximability results for approximate Nash equilibria
• Efficient Nash equilibria on semilattices
• Incompatibility of efficiency and strategyproofness in the random assignment setting with indifferences
• Inapproximability of Nash equilibrium

Cites work

• A linear time approximation algorithm for multiprocessor scheduling
• Convergence time to Nash equilibrium in load balancing
• Coordination mechanism for selfish scheduling under a grade of service provision
• Equilibria for two parallel links: the strong price of anarchy versus the price of anarchy
• How bad is selfish routing?
• scientific article; zbMATH DE number 2038735 (Why is no real title available?)
• Inefficiency of equilibria for the machine covering game on uniform machines
• Inefficiency of Nash equilibria with parallel processing policy
• Maximizing the minimum load: the cost of selfishness
• On-line load balancing in a hierarchical server topology
• Performance guarantees of local search for multiprocessor scheduling
• Scheduling to Maximize the Minimum Processor Finish Time in a Multiprocessor System
• Strong price of anarchy
• Strong Price of Anarchy for Machine Load Balancing
• The cost of selfishness for maximizing the minimum load on uniformly related machines
• The price of anarchy on uniformly related machines revisited
• The Price of Stability for Network Design with Fair Cost Allocation
• Tight bounds for worst-case equilibria
• Worst-case equilibria

Cited in

(3)

• Efficiency of dual equilibria in selfish task allocation to selfish machines
• Price of anarchy of scheduling games on hierarchical machines with quadratic social cost
• Inefficiency of equilibria for the machine covering game on uniform machines

This page was built for publication: Inefficiency of the Nash equilibrium for selfish machine covering on two hierarchical uniform machines

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