An Algorithm to Compute the Nucleolus of Shortest Path Games

Abstract

We study a type of cooperative games introduced in Fragnelli et al. (Math Methods Oper Res 52(2):251–264, 2000) called shortest path games. They 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. We 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.