A Note on the Balancedness and the Concavity of Highway Games

Research output: Working paperDiscussion paperOther research output

305 Downloads (Pure)


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.
Original languageEnglish
Place of PublicationTilburg
PublisherOperations research
Number of pages14
Publication statusPublished - 2008

Publication series

NameCentER Discussion Paper


  • cooperative games
  • highway games
  • cost sharing


Dive into the research topics of 'A Note on the Balancedness and the Concavity of Highway Games'. Together they form a unique fingerprint.

Cite this