Inefficiency of multiplicative approximate Nash equilibrium for scheduling games

DOI10.1007/S10878-025-01274-7MaRDI QIDQ7001634zbMATH OpenFDO

Authors Zhu-Yi-Nan Wang, Chen Zhang, Zhiyi Tan

Publication date 4 April 2025

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S10878-025-01274-7

zbMATH Keywords

Nash equilibriumparallel machineprice of anarchyscheduling game

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27) Mathematical programming (90Cxx)

Cites work

• A class of games possessing pure-strategy Nash equilibria
• A linear time approximation algorithm for multiprocessor scheduling
• A survey on algorithms for Nash equilibria in finite normal-form games
• Approximate Nash Equilibria for Multi-player Games
• Convergence time to Nash equilibrium in load balancing
• Coordination mechanisms for selfish scheduling
• Efficient computation of approximate pure Nash equilibria in congestion games
• Load rebalancing games in dynamic systems with migration costs
• Maximizing the minimum load: the cost of selfishness
• On the impact of singleton strategies in congestion games
• On the performance of approximate equilibria in congestion games
• On the price of anarchy of two-stage machine scheduling games
• Performance guarantees of local search for multiprocessor scheduling
• Reducing price of anarchy of selfish task allocation with more selfishness
• Scheduling games with potential penalties on the move of jobs
• Scheduling to Maximize the Minimum Processor Finish Time in a Multiprocessor System
• Selfish load balancing and atomic congestion games
• The complexity of computing a Nash equilibrium
• The price of anarchy for utilitarian scheduling games on related machines
• The price of anarchy of finite congestion games
• The price of routing unsplittable flow
• The Santa Claus problem
• Tight bounds for selfish and greedy load balancing
• Tighter price of anarchy for selfish task allocation on selfish machines
• Worst-case equilibria

This page was built for publication: Inefficiency of multiplicative approximate Nash equilibrium for scheduling games

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