ON THE CONCAVITY OF DELIVERY GAMES

Delivery games, introduced by Hamers, Borm, van de Leensel and Tijs in 1994, are combinatorial optimization games that arise from delivery p roblems closely related to the Chinese postman problem (CPP). They sho wed that delivery games are not necessarily balanced. For delivery pro blems corresponding to the class of bridge-connected Euler graphs they showed that the related games are balanced. This paper focuses on the concavity property for delivery games. A delivery game arising from a delivery model corresponding to a bridge-connected Euler graph need n ot be concave. The main result will be that for delivery problems corr esponding to the class of bridge-connected cyclic graphs, which is a s ubclass of the class of bridge-connected Euler graphs, the related del ivery games are concave, Further, we discuss some extreme points of th e core and the tau-value for this class of concave delivery games. (C) 1997 Elsevier Science B.V.