Payoff Allocation Methods for Generalized Minimum Spanning Tree Games Seminar

Event details

The minimum-cost spanning tree game is a particular class of cooperative games defined on a graph, where each player owns a vertex. Solutions of the game represent ways to distribute the total cost of a minimum-cost spanning tree among all the players. When we partition the graph into clusters, the generalised minimum spanning tree problem is to determine a minimum-cost tree including exactly one vertex from each cluster. The paper introduces and studies the generalised minimum spanning tree game and some of its properties. We propose a constraint generation algorithm to calculate a stable payoff distribution and present some computational results obtained using the proposed algorithm.