Seminar Abstract 【On the Core of Minimum Cost Forest Games】 ------------------------------ Speaker: 梅澤 正史 Affiliation: 筑波大学 社会工学系 Date and Time: 2003. 9. 9 (Tue), 4:30 - 6:00 p.m. Place: 3F1136 Chair: 秋山 英三 ------------------------------ Abstract: Research in cost allocation arising from networks has been mostly focused on a tree network with one supplier and many customers. Kuipers [1997] formulates a general model with multiple suppliers and a network, which is not necessarily a tree. Our analysis is built on his model. Each supplier offers a different type of service to the customers, and each customer wishes to be connected with the suppliers that he needs. The characteristic function game, called minimum cost forest game, is deduced from minimum costs for constructing subnetworks. The core of this game may be empty. By introducing an equivalence relation on the set of customers, we provide sufficient conditions to have a nonempty core. It is shown that the game has a nonempty core as long as the optimal grand network is a forest which is composed of the collection of the minimum cost spanning trees on the above equivalence classes. It is further shown that, whenever the game consists of at most two equivalence classes, the core is nonempty. A network with more than two equivalence classes may have an empty core. Finally, it is shown that the same conditions are sufficient for the nonemptiness of the core when the feasibility of the network is restricted in a certain manner.