Rui S. Shibasaki, Mourad Baiou, et al.
ITOR
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.
Rui S. Shibasaki, Mourad Baiou, et al.
ITOR
Radu Marinescu, Haifeng Qian, et al.
NeurIPS 2022
Mourad Baiou, Francisco Barahona
SIAM Journal on Discrete Mathematics
Francisco Barahona
Operations Research Letters