science

Minimum-cost spanning tree game

Minimum-cost spanning tree game is a science topic covered in the lgStudy science library. This page brings together a partial reference excerpt, illustrations, worked examples, real-world applications and a short study plan, so you can understand Minimum-cost spanning tree game rather than just read about it. In short: A minimum-cost spanning-tree game (MCST game) is a kind of a cooperative game. In an MCST game, each player is a node in a complete graph.

Key takeaways

Minimum-cost spanning tree game belongs to science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Minimum-cost spanning tree game to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Minimum-cost spanning tree game from memory before moving on to harder problems.

Reference excerpt

A minimum-cost spanning-tree game (MCST game) is a kind of a cooperative game. In an MCST game, each player is a node in a complete graph. 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. Each edge in the graph has a cost, and the players build the minimum cost spanning tree. 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 of every MCST game is non-empty. The nucleolus is the unique point in the intersection of the core and the kernel. 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(n2) elementary operations for computing each additional point in the core. In general MCST games, computing the nucleolus is NP-hard; the proof is by reduction from the minimum set cover problem. There is an algorithm that computes the nucleolus in time O(n3|B|), where B is the set of relevant coalitions (in general, |B|=2n, but in some special cases, only a subset of the coalitions are relevant). If the underlying network is a tree, then the nucleolus can be computed in O(n3) time, and the Shapley value 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.

References

Worked examples

Example 1 — a first encounter with Minimum-cost spanning tree game

Start with the simplest possible case. Write down what Minimum-cost spanning tree game claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Minimum-cost spanning tree game before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Minimum-cost spanning tree game ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Minimum-cost spanning tree game

In research: Minimum-cost spanning tree game appears in science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Minimum-cost spanning tree game in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Minimum-cost spanning tree game is common in secondary-school and first-year university syllabi. It links to neighbouring topics Cooperative games, Spanning tree, so understanding it makes those chapters shorter.
In everyday life: Look for Minimum-cost spanning tree game outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

Ask Teacher Smith questions about this articleOpens your AI tutor with a question about “Minimum-cost spanning tree game” →

Affiliate

Preply — study more efficiently by working with a personal tutor. 50% off.

How to study Minimum-cost spanning tree game in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Minimum-cost spanning tree game means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Minimum-cost spanning tree game out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Minimum-cost spanning tree game in simple terms?

A minimum-cost spanning-tree game (MCST game) is a kind of a cooperative game. In an MCST game, each player is a node in a complete graph.

Why does Minimum-cost spanning tree game matter?

Because it connects several science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Minimum-cost spanning tree game?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Minimum-cost spanning tree game.