Stability in shortest path problems

We study three remarkable cost sharing rules in the context of shortest path problems, where agents have demands that can only be supplied by a source in a network. The demander rule requires each demander to pay the cost of their cheapest connection to the source. The supplier rule charges to each demander the cost of the second-cheapest connection and splits the excess payment equally between her access suppliers. The alexia rule averages out the lexicographic allocations, each of which allows suppliers to extract rent in some pre-specified order. We show that all three rules are anonymous and demand-additive core selections. Moreover, with three or more agents, the demander rule is characterized by core selection and a specific version of cost additivity. Finally, convex combinations of the demander rule and the supplier rule are axiomatized using core selection, a second version of cost additivity and two additional axioms that ensure the fair compensation of intermediaries.