On the Nucleolus of Shortest Path Games

We study a type of cooperative games introduced in [8] 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. Our development is done on a directed graph, but it can be extended to undirected graphs and to similar games defined on the nodes of a graph.