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

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21730%2F20%3A00334717" target="_blank" >RIV/68407700:21730/20:00334717 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1007/s10479-019-03235-w" target="_blank" >https://doi.org/10.1007/s10479-019-03235-w</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s10479-019-03235-w" target="_blank" >10.1007/s10479-019-03235-w</a>

Jazyk výsledku

angličtina

Název v původním jazyce

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

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

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

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/EF15_003%2F0000466" target="_blank" >EF15_003/0000466: Umělá inteligence a uvažování</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2020

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Annals of Operations Research

ISSN

0254-5330

e-ISSN

1572-9338

Svazek periodika

285

Číslo periodika v rámci svazku

April

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

23

Strana od-do

97-119

Kód UT WoS článku

000527867200005

EID výsledku v databázi Scopus

2-s2.0-85064658450