Computing Nash equilibria for scheduling on restricted parallel links

DOI10.1145/1007352.1007446zbMath1192.90072OpenAlexW2103802594MaRDI QIDQ5901071

Marios Mavronicolas, Martin Gairing, Burkhard Monien, Thomas Lücking

Publication date: 15 August 2010

Published in: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.86.1754

Mathematics Subject Classification ID

Noncooperative games (91A10) Deterministic scheduling theory in operations research (90B35) Approximation algorithms (68W25)

Related Items (26)

The shortest first coordination mechanism for a scheduling game with parallel-batching machines ⋮ Bottleneck Congestion Games with Logarithmic Price of Anarchy ⋮ The structure and complexity of Nash equilibria for a selfish routing game ⋮ Atomic routing games on maximum congestion ⋮ A faster combinatorial approximation algorithm for scheduling unrelated parallel machines ⋮ Worst-case Nash equilibria in restricted routing ⋮ Nonpreemptive coordination mechanisms for identical machines ⋮ On the structure and complexity of worst-case equilibria ⋮ Reducing price of anarchy of selfish task allocation with more selfishness ⋮ Congestion games with capacitated resources ⋮ Tight bounds for selfish and greedy load balancing ⋮ Non-clairvoyant scheduling games ⋮ Inefficiency of Nash equilibria with parallel processing policy ⋮ Multiindex resource distributions for hierarchical systems ⋮ A coordination mechanism for a scheduling game with parallel-batching machines ⋮ A new model for selfish routing ⋮ Nash equilibria in discrete routing games with convex latency functions ⋮ Mixed Nash equilibria in selfish routing problems with dynamic constraints ⋮ Evolutionary equilibrium in Bayesian routing games: specialization and niche formation ⋮ Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree ⋮ Price of anarchy in parallel processing ⋮ The Influence of Link Restrictions on (Random) Selfish Routing ⋮ Pure Nash equilibria in player-specific and weighted congestion games ⋮ Coordination mechanisms for selfish scheduling ⋮ Project games ⋮ A strategic approach to multiple estate division problems

This page was built for publication: Computing Nash equilibria for scheduling on restricted parallel links