Inefficiency of multiplicative approximate Nash equilibrium for scheduling games

Zhuyinan Wang, Chen Zhang and Zhiyi Tan ()
Additional contact information
Zhuyinan Wang: Zhejiang University
Chen Zhang: Zhejiang University
Zhiyi Tan: Zhejiang University

Journal of Combinatorial Optimization, 2025, vol. 49, issue 3, No 3, 21 pages

Abstract: Abstract This paper studies the inefficiency of multiplicative approximate Nash Equilibrium for scheduling games. There is a set of machines and a set of jobs. Each job could choose one machine and be processed by the chosen one. A schedule is a $$\theta $$ θ -NE if no player has the incentive to deviate so that it decreases its cost by a factor larger than $$1+\theta $$ 1 + θ . The $$\theta $$ θ -NE is a generation of Nash Equilibrium and its inefficiency can be measured by the $$\theta $$ θ -PoA, which is also a generalization of the Price of Anarchy. For the game with the social cost of minimizing the makespan, the exact $$\theta $$ θ -PoA for any number of machines and any $$\theta \ge 0$$ θ ≥ 0 is obtained. For the game with the social cost of maximizing the minimum machine load, we present upper and lower bounds on the $$\theta $$ θ -PoA. Tight bounds are provided for cases where the number of machines is between 2 and 7 and for any $$\theta \ge 0$$ θ ≥ 0 .

Keywords: Scheduling game; Price of anarchy; Nash equilibrium; Parallel machine; 90B35; 90C27 (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-025-01274-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:49:y:2025:i:3:d:10.1007_s10878-025-01274-7

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-025-01274-7

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().