### 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.

Original language | English |
---|---|

Place of Publication | Tilburg |

Publisher | Operations research |

Number of pages | 14 |

Volume | 2008-29 |

Publication status | Published - 2008 |

### Publication series

Name | CentER Discussion Paper |
---|---|

Volume | 2008-29 |

### Keywords

- cooperative games
- highway games
- cost sharing

## Fingerprint 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

Ciftci, B. B., Borm, P. E. M., & Hamers, H. J. M. (2008).

*A Note on the Balancedness and the Concavity of Highway Games*. (CentER Discussion Paper; Vol. 2008-29). Operations research.