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

DOI10.1007/978-3-030-35389-6_15MaRDI QIDQ777962zbMATH OpenOpenAlexFDO

Authors Eirini Georgoulaki, Kostas Kollias

Publication date 30 June 2020

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

Mathematics Subject Classification ID

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

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.

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

Cites work

• A class of games possessing pure-strategy Nash equilibria
• Approximating the throughput of multiple machines in real-time scheduling
• Automata, Languages and Programming
• Coordination mechanisms for selfish scheduling
• Cost-sharing games in real-time scheduling systems
• Decentralized utilitarian mechanisms for scheduling games
• Designing network protocols for good equilibria
• Distributed welfare games
• Efficient coordination mechanisms for unrelated machine scheduling
• Exact price of anarchy for polynomial congestion games
• Intrinsic robustness of the price of anarchy
• Network cost-sharing without anonymity
• Optimal coordination mechanisms for unrelated machine scheduling
• Optimal cost sharing for resource selection games
• Optimal cost-sharing in general resource selection games
• Potential games are \textit{necessary} to ensure pure Nash equilibria in cost sharing games
• Real-time scheduling to minimize machine busy times
• Restoring Pure Equilibria to Weighted Congestion Games
• Sharing non-anonymous costs of multiple resources optimally
• The Price of Stability for Network Design with Fair Cost Allocation
• The price of anarchy of finite congestion games
• The price of routing unsplittable flow
• Tight bounds for cost-sharing in weighted congestion games
• Weighted congestion games: price of anarchy, universal worst-case examples, and tightness
• Worst-case equilibria

Cited in

(4)

• Resource-Aware Cost-Sharing Methods for Scheduling Games
• Cost-sharing games in real-time scheduling systems
• 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)