@techreport{89305e0b28d74becb45c2b2ba9764038,

title = "A Note on the Balancedness and the Concavity of Highway Games",

abstract = "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.",

keywords = "cooperative games, highway games, cost sharing",

author = "B.B. Ciftci and P.E.M. Borm and H.J.M. Hamers",

note = "Subsequently published in European Journal of Operational Research, 2010 (rt) Pagination: 14",

year = "2008",

language = "English",

volume = "2008-29",

series = "CentER Discussion Paper",

publisher = "Operations research",

type = "WorkingPaper",

institution = "Operations research",

}