Computing Nash equilibria for scheduling on restricted parallel links

DOI10.1007/S00224-009-9191-9MaRDI QIDQ5917951zbMATH OpenOpenAlexFDO

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

Publication date 6 October 2010

Published in Theory of Computing Systems (Search for Journal in Brave)

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

zbMATH Keywords

algorithmic game theorycomputation of Nash equilibriascheduling restricted machinesunsplittable flow

Mathematics Subject Classification ID

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

Recommendations

• Worst-case Nash equilibria in restricted routing
• Theoretical Computer Science
• Routing into two parallel links: Game-theoretic distributed algorithms
• Equilibria for two parallel links: the strong price of anarchy versus the price of anarchy

Cites work

• A faster combinatorial approximation algorithm for scheduling unrelated parallel machines
• A new approach to the maximum-flow problem
• Algorithms, games, and the internet
• An optimal rounding gives a better approximation for scheduling unrelated machines
• Approximation algorithms for scheduling unrelated parallel machines
• Approximation algorithms for single-source unsplittable flow
• Congestion games with player-specific payoff functions
• Equilibrium points in n -person games
• Exact and Approximate Algorithms for Scheduling Nonidentical Processors
• scientific article; zbMATH DE number 1099369 (Why is no real title available?)
• scientific article; zbMATH DE number 2038735 (Why is no real title available?)
• scientific article; zbMATH DE number 2086616 (Why is no real title available?)
• scientific article; zbMATH DE number 3349645 (Why is no real title available?)
• Network flows. Theory, algorithms, and applications.
• Non-cooperative games
• On the single-source unsplittable flow problem
• Structure and complexity of extreme Nash equilibria
• The complexity of computing a Nash equilibrium
• Tradeoffs in worst-case equilibria
• Worst-case equilibria

Cited in

(7)

• Decentralized utilitarian mechanisms for scheduling games
• Optimal coordination mechanisms for unrelated machine scheduling
• Performance guarantees of jump neighborhoods on restricted related parallel machines
• Monotonicity of equilibria in nonatomic congestion games
• An improved bound for the price of anarchy for related machine scheduling
• Coordination mechanisms with rank-based utilities
• Nash equilibria in competitive project scheduling

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

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