On Highway Problems

A highway problem is a cost sharing problem that arises if the common resource is an ordered set of sections with fixed costs such that each agent demands consecutive sections. We show that the core, the prenucleolus, and the Shapley value on the class of TU games associated with highway problems possess characterizations related to traditional axiomatizations of the solutions on certain classes of games. However, in the formulation of the employed simple and intuitive properties the associated games do not occur. The main axioms for the core and the nucleolus are consistency properties based on the reduced highway problem that arises from the original highway problem by eliminating any agent of a specific type and using her charge to maintain a certain part of her sections. The Shapley value is characterized with the help of individual independence of outside changes, a property that requires the fee of an agent only depending on the highway problem when truncated to the sections she demands. An alternative characterization is based on the new contraction property. Finally it is shown that the games that are associated with generalized highway problems in which agents may demand non-connected parts are the positive cost games, i.e., nonnegative linear combinations of dual unanimity games