Interdependent Scheduling Games

Abeliuk, Andres; Aziz, Haris; Berbeglia, Gerardo; Gaspers, Serge; Kalina, Petr; Mattei, Nicholas; Peters, Dominik; Stursberg, Paul; Van Hentenryck, Pascal; Walsh, Toby

Interdependent Scheduling Games

Andrés Abeliuk, Haris Aziz, Gerardo Berbeglia, Serge Gaspers, Petr Kalina, Nicholas Mattei, Dominik Peters, Paul Stursberg, Pascal Van Hentenryck, Toby Walsh

Download BibTeX Cite

Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. Pages 2-8.

Abstract

We propose a model of interdependent scheduling games in which each player controls a set of services that they schedule independently. A player is free to schedule his own services at any time; however, each of these services only begins to accrue reward for the player when all predecessor services, which may or may not be controlled by the same player, have been activated. This model, where players have interdependent services, is motivated by the problems faced in planning and coordinating large-scale infrastructures, e.g., restoring electricity and gas to residents after a natural disaster or providing medical care in a crisis when different agencies are responsible for the delivery of staff, equipment, and medicine. We undertake a game-theoretic analysis of this setting and in particular consider the issues of welfare maximization, computing best responses, Nash dynamics, and existence and computation of Nash equilibria.

Andres Abeliuk, Haris Aziz, Gerardo Berbeglia, Serge Gaspers, Petr Kalina, Nicholas Mattei, Dominik Peters, Paul Stursberg, Pascal Van Hentenryck, and Toby Walsh. 2016. Interdependent Scheduling Games. In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16. IJCAI, 2–8. https://ijcai.org/proceedings/2016/8

@inproceedings{ijcai2016p8,
  title     = {Interdependent Scheduling Games},
  author    = {Abeliuk, Andres and Aziz, Haris and Berbeglia, Gerardo and Gaspers, Serge and Kalina, Petr and Mattei, Nicholas and Peters, Dominik and Stursberg, Paul and Van Hentenryck, Pascal and Walsh, Toby},
  booktitle = {Proceedings of the Twenty-Fifth International Joint Conference on
               Artificial Intelligence, {IJCAI-16}},
  publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
  editor    = {Subbarao Kambhampati},
  pages     = {2--8},
  year      = {2016},
  month     = {7},
  url       = {https://ijcai.org/proceedings/2016/8},
}

TY  - CPAPER
TI  - Interdependent Scheduling Games
AU  - Abeliuk, Andres
AU  - Aziz, Haris
AU  - Berbeglia, Gerardo
AU  - Gaspers, Serge
AU  - Kalina, Petr
AU  - Mattei, Nicholas
AU  - Peters, Dominik
AU  - Stursberg, Paul
AU  - Van Hentenryck, Pascal
AU  - Walsh, Toby
T2  - Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16
PB  - AAAI Press / International Joint Conferences on Artificial Intelligence
PY  - 2016
SP  - 2
EP  - 8
UR  - https://ijcai.org/proceedings/2016/8
ER  -