A new stable and more responsive cost sharing solution for minimum cost spanning tree problems

doi:10.1016/j.geb.2011.09.002

Games and Economic Behavior

Volume 75, Issue 1, May 2012, Pages 402-412

https://doi.org/10.1016/j.geb.2011.09.002 Get rights and content

Abstract

Minimum cost spanning tree (mcst) problems try to connect agents efficiently to a source when agents are located at different points in space and the cost of using an edge is fixed. We introduce a new cost sharing solution that always selects a point in the core and that is more responsive to changes than the well-studied folk solution. The paper shows a sufficient condition for the concavity of the stand-alone cost game. Modifying the game to make sure the condition is satisfied and then taking the Shapley value gives the new solution.

Highlights

► A new cost sharing solution is defined for the case where locations are private property. ► The new cost sharing solution is in the core and is more responsive to changes and asymmetries than the folk solution. ► A sufficient condition for concavity of the stand-alone cost game with private property is given.

References (14)

G. Bergantinos et al.
A fair rule in minimum cost spanning tree problems
J. Econ. Theory
(2007)
G. Bergantinos et al.
Additivity in minimum cost spanning tree problems
J. Math. Econ.
(2009)
A. Bogomolnaia et al.
Sharing the cost of a minimal cost spanning tree: Beyond the folk solution
Games Econ. Behav.
(2010)
B. Dutta et al.
Cost monotonicity, consistency and minimum cost spanning tree games
Games Econ. Behav.
(2004)
A. Kar
Axiomatization of the Shapley value on minimum cost spanning tree games
Games Econ. Behav.
(2002)
S. Tijs et al.
Obligation rules for msct situations and their monotonicity properties
Europ. J. Operations Res.
(2006)
Ando, K., 2010. Computation of the Shapley value of minimum cost spanning tree games: P-hardness and polynomial cases....

There are more references available in the full text version of this article.

Cited by (46)

Stable cores in information graph games
2022, Games and Economic Behavior
Citation Excerpt :
As a consequence of the above theorem, the only concave information graph games are those which associated saturated information graph is cycle-complete. This parallels a result in Trudeau (2012) (see Theorem 2 and Lemma A.1) that shows that the only concave elementary mcst games with no irrelevant arcs are those with a cycle-complete graph. Moreover, we have shown that, for information graph games, concavity is not only sufficient for the stability of the core but it is also a necessary condition.
In an information graph situation, a finite set of agents and a source are the set of nodes of an undirected graph with the property that two adjacent nodes can share information at no cost. The source has some information (or technology), and agents in the same component as the source can reach this information for free. In other components, some agent must pay a unitary cost to obtain the information. We prove that the core of the derived information graph game is a von Neumann-Morgenstern stable set if and only if the information graph is cycle-complete, or equivalently if the game is concave. Otherwise, whether there always exists a stable set is an open question. If the information graph consists of a ring that contains the source, a stable set always exists and it is the core of a related situation where one edge has been deleted.
Trouble comes in threes: Core stability in minimum cost connection networks
2022, European Journal of Operational Research
We consider a generalization of the Minimum Cost Spanning Tree (MCST) model, called the Minimum Cost Connection Network (MCCN) model, where network users have connection demands in the form of a pair of nodes they want connected directly or indirectly. For a fixed network, which satisfies all connection demands, the problem consists of allocating the total cost of the network among its users. Thereby every MCCN problem induces a cooperative cost game where the cost of every coalition of users is the cost of an efficient network satisfying the demand of the users in the coalition. Unlike the MCST-model, we show that the core of the induced cost game in the MCCN-model can be empty even when all locations are demanded. We therefore consider sufficient conditions for non-empty core. It is shown that: when the efficient network and the demand graph (i.e. the graph consisting of the direct connections between the pairs of demanded nodes) consist of the same components, the induced cost game has non-empty core (Theorem 1); and, when the demand graph consists of at most two components, the induced cost game has non-empty core (Theorem 2).
Compromising to share the revenues from broadcasting sports leagues
2021, Journal of Economic Behavior and Organization
Citation Excerpt :
Thus, the parallelism with our result is strong. Something similar happens in minimum cost spanning tree problems, where Trudeau (2014) characterizes the convex combination of the folk rule (e.g., Bergantiños and Vidal-Puga, 2007) and the so-called cycle-complete rule (e.g., Trudeau, 2012), also making use of additivity. Compromises between the proportional and constrained equal-award rules (thus, satisfying the standard non-negativity condition for claims problems) have also been considered by Thomson (2015a,b).
We study the problem of sharing the revenues raised from the collective sale of broadcasting rights for sports leagues. We characterize the sharing rules satisfying three basic and intuitive axioms: symmetry, additivity and maximum aspirations. They convey a natural compromise between two focal rules, arising from polar estimations of teams’ loyal viewers. We also show that these compromise ruleshave further interesting properties, such as allowing for the existence of a majority voting equilibrium. We bring some of the testable implications from our axiomatic analysis to the real case of European football leagues.
Allocating extra revenues from broadcasting sports leagues
2020, Journal of Mathematical Economics
Citation Excerpt :
This sale is often collective, which generates an interesting problem of resource allocation, akin to well-known problems already analyzed in the game-theory literature. Instances are airport problems (e.g., Littlechild and Owen, 1973; Hu et al., 2012), bankruptcy problems (e.g., O’Neill, 1982; Thomson, 2019), telecommunications problems (e.g., Nouweland van den et al., 1996), museum pass problems (e.g., Ginsburgh and Zang, 2003; Bergantiños and Moreno-Ternero, 2015), cost sharing in minimum cost spanning tree problems (e.g., Bergantiños and Vidal-Puga, 2007; Trudeau, 2012), or labeled network games (e.g., Algaba et al., 2020a,b). In a recent paper (Bergantiños and Moreno-Ternero, 2020a), we introduced a formal model to analyze the problem of sharing the revenues from broadcasting sports leagues among participating teams.
We consider the problem of sharing the revenues from broadcasting sports leagues among participating teams. We introduce axioms formalizing alternative ways of allocating the extra revenue obtained from additional viewers. We show that, combined with some other standard axioms, they provide axiomatic characterizations of three focal rules for this problem: the uniform rule, the equal-split rule and concede-and-divide.
Clique games: A family of games with coincidence between the nucleolus and the Shapley value
2020, Mathematical Social Sciences
We introduce a new family of cooperative games for which there is coincidence between the nucleolus and the Shapley value. These so-called clique games are such that agents are divided into cliques, with the value created by a coalition linearly increasing with the number of agents belonging to the same clique. Agents can belong to multiple cliques, but for a pair of cliques, at most a single agent belongs to their intersection. Finally, if two agents do not belong to the same clique, there is at most one way to link the two agents through a chain of agents, with any two non-adjacent agents in the chain belonging to disjoint sets of cliques. We examine multiple games defined on graphs that provide a fertile ground for applications of our results.
The degree and cost adjusted folk solution for minimum cost spanning tree games
2019, Games and Economic Behavior
In this paper two cost sharing solutions for minimum cost spanning tree problems are introduced, the degree adjusted folk solution and the cost adjusted folk solution. These solutions overcome the problem of the classical reductionist folk solution as they have considerable strict ranking power, without breaking established axioms. As such they provide an affirmative answer to an open question, put forward in Bogomolnaia and Moulin (2010).

View all citing articles on Scopus

^☆: Thanks to Hervé Moulin and anonymous referees for precious comments. Financial support from the Social Sciences and Humanities Research Council of Canada is acknowledged.

View full text

A new stable and more responsive cost sharing solution for minimum cost spanning tree problems☆

Abstract

Highlights

J. Econ. Theory

J. Math. Econ.

Games Econ. Behav.

Games Econ. Behav.

Games Econ. Behav.

Europ. J. Operations Res.