A minimum-cost spanning-tree game (MCST game) is a kind of a

cooperative game Cooperative game may refer to: * Cooperative board game, board games in which players work together to achieve a common goal * Cooperative game theory, in game theory, a game with competition between groups of players and the possibility of coopera ...

. In an MCST game, each player is a node in a

complete graph In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices i ...

. The graph contains an additional node - the ''supply node'' - denoted by ''s''. The goal of the players is that all of them will be connected by a path to ''s''. To this end, they need to construct a

spanning tree In the mathematical field of graph theory, a spanning tree ''T'' of an undirected graph ''G'' is a subgraph that is a tree which includes all of the vertices of ''G''. In general, a graph may have several spanning trees, but a graph that is no ...

. Each edge in the graph has a cost, and the players build the

minimum cost spanning tree A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. T ...

. The question then arises, how to allocate the cost of this MCST among the players? The solution offered by cooperative game theory is to consider the cost of each potential coalition - each subset of the players. The cost of each coalition ''S'' is the minimum cost of a spanning tree connecting only the nodes in ''S'' to the supply node ''s''. The ''value'' of ''S'' is minus the cost of ''S''. Using these definitions, various solution concepts from cooperative game theory can be applied. MCST games were introduced by Bird in 1976.

Properties

* The

core Core or cores may refer to: Science and technology * Core (anatomy), everything except the appendages * Core (laboratory), a highly specialized shared research resource * Core (manufacturing), used in casting and molding * Core (optical fiber ...

of every MCST game is non-empty. * The

nucleolus The nucleolus (; : nucleoli ) is the largest structure in the cell nucleus, nucleus of eukaryote, eukaryotic cell (biology), cells. It is best known as the site of ribosome biogenesis. The nucleolus also participates in the formation of signa ...

is the unique point in the intersection of the

and the

kernel Kernel may refer to: Computing * Kernel (operating system), the central component of most operating systems * Kernel (image processing), a matrix used for image convolution * Compute kernel, in GPGPU programming * Kernel method, in machine learnin ...

. * If the underlying network is a tree, then the nucleolus coincides with the kernel.

Computation

*One solution in the core can be read directly from any minimum cost spanning tree graph associated with the problem. * There is an algorithm that requires O(n²) elementary operations for computing each additional point in the core. * In general MCST games, computing the

is NP-hard; the proof is by reduction from the minimum

set cover problem The set cover problem is a classical question in combinatorics, computer science, operations research, and complexity theory. Given a set of elements (henceforth referred to as the universe, specifying all possible elements under considerati ...

. There is an algorithm that computes the nucleolus in time O(''n''³, ''B'', ), where B is the set of relevant coalitions (in general, , B, =2^''n'', but in some special cases, only a subset of the coalitions are relevant). * If the underlying network is a

tree In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, e.g., including only woody plants with secondary growth, only ...

, then the nucleolus can be computed in O(''n''³) time, and the

Shapley value In cooperative game theory, the Shapley value is a method (solution concept) for fairly distributing the total gains or costs among a group of players who have collaborated. For example, in a team project where each member contributed differently, ...

can be computed in O(''n'') time. The run-time of computing the nucleolus can be reduced to O(''n'' log ''n'') using efficiently mergeable heaps. In particular cases, the nucleolus can be computed in O(''n'') time.

Spanning forest games

A minimum-cost spanning-forest game (MCSF game) is a generalization of an MCST game, in which multiple supply-nodes are allowed. In general, the core of an MCSF game may be empty. However, if the underlying network is a tree, the core is always non-empty, and core points can be computed in

strongly-polynomial time In computer science, a ''polynomial-time algorithm'' is generally speaking an algorithm whose running time is upper-bounded by some polynomial function of the input size. The definition naturally depends on the computational model, which determin ...

References

{{reflist Cooperative games Spanning tree