Cost-sharing games in real-time scheduling systems

Tami Tamir ()
Additional contact information
Tami Tamir: Reichman University

International Journal of Game Theory, 2023, vol. 52, issue 1, No 11, 273-301

Abstract: Abstract We apply non-cooperative game theory to analyze the server’s activation cost in real-time scheduling systems. An instance of the game consists of a single server and a set of unit-length jobs. Every job needs to be processed along a specified time interval, defined by the job’s release-time and due-date. Jobs may also have variable weights, which specify the amount of resource they require. We assume that jobs are controlled by selfish agents who act to minimize their own cost, rather than to optimize any global objective. The jobs processed in a specific time-slot cover the server’s activation cost in this slot, with the cost being shared proportionally to the jobs’ weights. Known results on cost-sharing games do not exploit the special interval-structure of the strategy space in our game, and are therefore not tight. We present a complete analysis of equilibrium existence, computation, and inefficiency in real-time scheduling cost-sharing games. Our tight analysis covers various classes of instances, and distinguishes between unilateral and coordinated deviations.

Keywords: Cost-sharing games; Real-time scheduling; Equilibrium inefficiency; Equilibrium computation; Coordinated deviations (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s00182-022-00819-y 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:jogath:v:52:y:2023:i:1:d:10.1007_s00182-022-00819-y

Ordering information: This journal article can be ordered from
http://www.springer. ... eory/journal/182/PS2

DOI: 10.1007/s00182-022-00819-y

Access Statistics for this article

International Journal of Game Theory is currently edited by Shmuel Zamir, Vijay Krishna and Bernhard von Stengel

More articles in International Journal of Game Theory from Springer, Game Theory Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().