EUVIMEDEUVIMED entdecken
Crossref

Interval Scheduling Games with Color-Based Concurrent Jobs

Vipin Ravindran Vijayalakshmi, Marc Schröder, Tami Tamir

ACM Transactions on Economics and Computation · 22.08.2026

DOI: 10.1145/3842393 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Economics and Computation, online erschienen am 22.08.2026. Verfasst von Vipin Ravindran Vijayalakshmi und 2 weiteren Autor:innen. Die Arbeit nennt 34 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We consider a game theoretic variant of an interval scheduling problem. Every job is associated with a length, a weight, and a color. Each player controls all the jobs of a specific color, and needs to decide on a processing interval for each of its jobs. Jobs of the same color can be processed simultaneously by the machine. A job is covered if the machine is configured to its color during its whole processing interval. The goal of the machine is to maximize the sum of weights of all covered jobs, and the goal of each player is to maximize the sum of weights of covered jobs from its color. The study of this game is motivated by several applications like antenna scheduling for wireless networks. We first show that given a strategy profile of the players, the machine scheduling problem can be solved in polynomial time. We then study the game from the players’ point of view. We analyze the existence of Nash equilibria, its computation, and inefficiency. We distinguish between instances of the classical interval scheduling problem, in which every player controls a single job, and instances in which color sets may include multiple jobs.

Zitieren

APA

Vijayalakshmi, V. R., Schröder, M., & Tamir, T. (2026). Interval Scheduling Games with Color-Based Concurrent Jobs. ACM Transactions on Economics and Computation. https://doi.org/10.1145/3842393

Vancouver

Vijayalakshmi VR, Schröder M, Tamir T. Interval Scheduling Games with Color-Based Concurrent Jobs. ACM Transactions on Economics and Computation. 2026. doi:10.1145/3842393

BibTeX
@article{Vijayalakshmi2026,
  author = {Vijayalakshmi, Vipin Ravindran and Schröder, Marc and Tamir, Tami},
  title = {Interval Scheduling Games with Color-Based Concurrent Jobs},
  journal = {ACM Transactions on Economics and Computation},
  year = {2026},
  doi = {10.1145/3842393}
}
Kostenlos starten →