An algorithm to compute the nucleolus of shortest path games (Q1999962): Difference between revisions

Cooperative game theory deals with coalitions who coordinate their actions and pool their winnings. The authors study a type of cooperative games introduced in [\textit{V. Fragnelli} et al., Math. Methods Oper. Res. 52, No. 2, 251--264 (2000; Zbl 1103.91313)] called shortest path games. Fragnelli et al. (2000) arise on a network that has two special nodes $s$ and $t$. A coalition corresponds to a set of arcs and it receives a reward if it can connect $s$ and $t$. A coalition also incurs a cost for each arc that it uses to connect $s$ and $t$, thus the coalition must choose a path of minimum cost among all the arcs that it controls. These games are relevant to logistics, communication, or supply-chain networks. The authors give a polynomial combinatorial algorithm to compute the nucleolus. This vector reflects the relative importance of each arc to ensure the connectivity between $s$ and $t$. To my understanding, the paper is a very valuable and a nice piece of work for cooperative game theory. The paper's contents is widely innovative and pioneering. Many ideas are quite smart. Further, the authors give a quite good literature review. Further, the paper is organized in an attentive way. Purpose of the paper is given perfectly. Mathematical formulas and detailed proofs of the results are explained evidently. Finally, the paper is very well motivated, structured, written; theory, methods and applications vary in an appropriate way. I fully recommend the paper for researchers and graduate students in the area.