A Note on the Balancedness and the Concavity of Highway Games

A highway problem is determined by a connected graph which provides all potential entry and exit vertices and all possible edges that can be constructed between vertices, a cost function on the edges of the graph and a set of players, each in need of constructing a connection between a specific entry and exit vertex. Mosquera and Zarzuelo (2006) introduce highway problems and the corresponding cooperative cost games called high- way games to address the problem of fair allocation of the construction costs in case the underlying graph is a chain. In this note, we study the concavity and the balancedness of highway games on more general graphs. A graph G is called highway-game concave if for each highway problem in which G is the underlying graph the corresponding highway game is concave. The main result of our study is that a graph is highway-game concave if and only if it is weakly triangular. Moreover, we provide sufficient conditions on highway problems defined on cyclic graphs such that the corresponding highway games are balanced.