Price of anarchy and price of stability in multi-agent project scheduling - LAAS - Laboratoire d'Analyse et d'Architecture des Systèmes Accéder directement au contenu
Article Dans Une Revue Annals of Operations Research Année : 2020

Price of anarchy and price of stability in multi-agent project scheduling

Résumé

We consider a project scheduling environment in which the activities are partitioned among a set of agents. The owner of each activity can decide its length, which is linearly related to its cost within a minimum (crash) and a maximum (normal) length. For each day the project makespan is reduced with respect to its normal value, a reward is offered to the agents, and each agent receives a given ratio of the reward. As in classical game theory, we assume that the agents’ parameters are common knowledge. We study the Nash equilibria of the corresponding non-cooperative game as a desired state where no agent is motivated to change his/her decision. Regarding project makespan as an overall measure of efficiency, here we consider the worst and the best Nash equilibria (i.e., for which makespan is maximum and, respectively, minimum among Nash equilibria). We show that the problem of finding the worst Nash equilibrium is NP-hard (finding the best Nash equilibrium is already known to be strongly NP-hard), and propose an ILP formulation for its computation. We then investigate the values of the price of anarchy and the price of stability in a large sample of realistic size problems and get useful insights for the project owner.
Fichier non déposé

Dates et versions

hal-03009331 , version 1 (17-11-2020)

Identifiants

Citer

Alessandro Agnetis, Cyril Briand, Sandra Ulrich Ngueveu, Přemysl Šůcha. Price of anarchy and price of stability in multi-agent project scheduling. Annals of Operations Research, 2020, 285 (1-2), pp.97-119. ⟨10.1007/s10479-019-03235-w⟩. ⟨hal-03009331⟩
72 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More