Payoff Allocation Methods for Generalized Minimum Spanning Tree Games Seminar
- Time:
- 15:00 - 16:00
- Date:
- 22 February 2017
- Venue:
- The Ketley Room (B54 / level 4)
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.