On the Price of Anarchy of cost-sharing in real-time scheduling systems

DOI10.1007/978-3-030-35389-6_15zbMATH Open1435.90068arXiv1907.05926OpenAlexW2991031009MaRDI QIDQ777962FDOQ777962

Eirini Georgoulaki, Kostas Kollias

Publication date: 30 June 2020

Abstract: We study cost-sharing games in real-time scheduling systems where the activation cost of the server at any given time is a function of its load. We focus on monomial cost functions and consider both the case when the degree is less than one (inducing positive externalities for the jobs) and when it is greater than one (inducing negative externalities for the jobs). For the former case, we provide tight price of anarchy bounds which show that the price of anarchy grows to infinity as a polynomial of the number of jobs in the game. For the latter, we observe that existing results provide constant and tight (asymptotically in the degree of the monomial) bounds on the price of anarchy. We then switch our attention to improving the price of anarchy by means of a simple coordination mechanism that has no knowledge of the instance. We show that our mechanism reduces the price of anarchy of games with $n$ jobs and unit activation costs from $Theta(sqrtn)$ to $2$. We also show that for a restricted class of instances a similar improvement is achieved for monomial activation costs. This is not the case, however, for unrestricted instances of monomial costs for which we prove that the price of anarchy remains super-constant for our mechanism.

Full work available at URL: https://arxiv.org/abs/1907.05926

Recommendations

• Cost-sharing games in real-time scheduling systems
• Cost-sharing games in real-time scheduling systems
• Improved price of anarchy for machine scheduling games with coordination mechanisms
• scientific article; zbMATH DE number 6906899
• Price of anarchy in parallel processing

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Applications of game theory (91A80)

Cites Work

• Worst-case equilibria
• A class of games possessing pure-strategy Nash equilibria
• Tight Bounds for Cost-Sharing in Weighted Congestion Games
• The Price of Stability for Network Design with Fair Cost Allocation
• The price of anarchy of finite congestion games
• Coordination mechanisms for selfish scheduling
• Restoring Pure Equilibria to Weighted Congestion Games
• Designing Network Protocols for Good Equilibria
• Optimal Cost Sharing for Resource Selection Games
• Network Cost-Sharing without Anonymity
• Approximating the throughput of multiple machines in real-time scheduling
• The Price of Routing Unsplittable Flow
• Efficient coordination mechanisms for unrelated machine scheduling
• Optimal Coordination Mechanisms for Unrelated Machine Scheduling
• Automata, Languages and Programming
• A model for minimizing active processor time
• Potential Games Are Necessary to Ensure Pure Nash Equilibria in Cost Sharing Games
• Weighted Congestion Games: Price of Anarchy, Universal Worst-Case Examples, and Tightness
• Real-time scheduling to minimize machine busy times
• Exact Price of Anarchy for Polynomial Congestion Games
• Decentralized utilitarian mechanisms for scheduling games
• Sharing Non-anonymous Costs of Multiple Resources Optimally
• Optimal Cost-Sharing in General Resource Selection Games
• Intrinsic Robustness of the Price of Anarchy
• Distributed Welfare Games
• Cost-sharing games in real-time scheduling systems

Cited In (2)

• Cost-sharing games in real-time scheduling systems
• Arbitrary profit sharing in federated learning utility games

This page was built for publication: On the Price of Anarchy of cost-sharing in real-time scheduling systems

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