Finding socially best spanning trees

This article combines Social Choice Theory with Discrete Optimization. We assume that individuals have preferences over edges of a graph that need to be aggregated. The goal is to find a socially ‘best’ spanning tree in the graph. As ranking all spanning trees is becoming infeasible even for small numbers of vertices and/or edges of a graph, our interest lies in finding algorithms that determine a socially ‘best’ spanning tree in a simple manner. This problem is closely related to the minimum (or maximum) spanning tree problem in Discrete Optimization. Our main result shows that for the various underlying ranking rules on the set of spanning trees discussed in this article, the sets of ‘best’ spanning trees coincide. Moreover, a greedy algorithm based on a transitive group ranking on the set of edges will always provide such a ‘best’ spanning tree.