Decision SupportCost allocation in asymmetric trees
Introduction
The study on the structure of service networks (such as power grids, gas pipelines, telecommunications or transportation infrastructures) has become more and more important. Those networks are costly (some times that cost is the amount to pay for its construction, and some other times it refers to the needed money for its maintenance). Quite often the structure of the network is a tree, because it allows to have all agents connected in the cheapest way. The problem of allocation the cost of a network, and particularly of a tree, has been widely studied in the literature.
Let us consider the simplest problem we may define, that is, two agents with a link connecting them. To divide the cost of the link equally between the two extremes, is a quite reasonable outcome when there is no more information and agents are assumed to be homogeneous. However, there are many cases where that homogeneity does not apply, and the link is much more important for one of the agents than for the other. The electrical interconnection between France and Spain is a quite illustrative example of this situation. These two countries decided to communicate their national power grid with a link crossing the Pyrenees. The cost of this connection has to be split between both countries, taking into account that Spain will obtain more beneficial than France from the construction of the link. This is because France produces enough electricity to cover, in case of failure in Spain, both its own demand and the Spanish one. The question then arises: How should the cost of the new connection be distributed between France and Spain considering all the elements? Similar questions emerge in the construction of the gas pipelines between Europe and Africa or Russia and Germany. Another situation that reflects this asymmetry is the network of aqueducts and pipelines that bring water from the rainy regions to the arid areas. The first ones use to have enough water to cover its demand and to even send the surplus to where it is needed, whereas the arid regions hardly have enough resource to fulfilled its own demand. Until which point is fair to oblige to the rainy areas to contribute to the cost of the pipelines? This paper deals with these situations, where the agents in the tree are asymmetric. This asymmetry will be induced by different demand and production for different agents.
In its general formulation, we consider a set of agents, each of them able to produce and demand a service like water. All agents are connected to each other forming a tree. Through this tree agents can send and receive water (or any other good). Hence, if the production of one agent fails, its demand can still be satisfied by obtaining the water from another agent. This can be obviously done only if the production of the other agent is high enough to compensate the failure. We assume that the tree is given and that each link of the tree has an associated cost that should be paid by the agents. This cost could be interpreted as a construction cost, maintenance cost (the tree already exists there but there are recurring maintenance costs, otherwise cannot be operative) or usage cost (the tree is there but we must pay a cost for using it). To sum up, a problem has five elements: a set of agents, a tree that describes the communication structure, a cost function that sets the cost of each link, a vector of demands (one demand for each agent), and a vector of productions (one production for each agent). A rule is a mechanism to distribute the cost of the tree among the agents.
Our paper belongs to literature on the axiomatic analysis of cost allocation rules. Some papers of this literature focus on general problems like Moulin and Shenker, 1992, Sprumont, 1998, Tijs and Driessen, 1986. Other papers study some particular situations associated with networks, like Estevez-Fernandez, 2012, Moulin and Laigret, 2011, Norde et al., 2002. Other papers focus on situations associated with a tree, like Bird, 1976, Bogomolnaia et al., 2010, Littlechild and Owen, 1973, Ni and Wang, 2007.
The particular case of trees has been a focal point (mostly because it is the most efficient way to communicate all the agents, regardless other aspects like flows and capacities). In the so-called minimum cost spanning problem several agents (nodes) need a good (water, for example) which can only be provided by a special node called the source (a water tank, for example). Thus, agents have to be connected to the source. Bird (1976), probably the seminal paper on this field, studies how to share the cost of a given tree among its nodes. Several papers came after in this field, proposing new solutions and analyzing the properties such solutions may satisfy. We can mention, for instance, the papers of Kar, 2002, Dutta and Kar, 2004, Tijs et al., 2006, Bergantiños and Vidal-Puga, 2007, Bergantiños and Vidal-Puga, 2010, Bergantiños and Lorenzo-Freire, 2008, Bogomolnaia and Moulin, 2010, Bergantiños et al., 2011, Hougaard and Tvede, 2012, Trudeau, 2012. In a parallel way other papers propose rules in problems arising from extensions of the minimum cost spanning tree problem. For instance, Fernandez, Hinojosa, and Puerto (2004) study multicriteria cost spanning tree games; Bergantiños and Gómez-Rúa (2010) study situations where agents are grouped; Dutta and Mishra (2012) study situations where costs are asymmetric; and Bergantiños et al., 2012, Bergantiños et al., 2014 study situations where the computation of the optimal tree is NP hard. In this paper we consider situations where each node can provide the service. Thus each node has a demand and a capacity production. As far as we are aware no other work has studied the problem presented in this paper. A real example captured by our model, but not by the previous ones, is the transfer of water from Tagus river to Segura river in Spain.
Our paper belongs to literature on the axiomatic analysis of cost allocation rules in networks. See Sharkey, 1995, Thomson, 2001 for two surveys of this literature. In the axiomatic method, rules are justified in terms of the axioms they fulfill. In general, suitable combinations of desirable axioms are used to differentiate among rules. Thus, we introduce a collection of axioms that are adequate for the framework we study.
The first group of axioms are: Fairness for two agents says that, when there are only two agents and one link between them, the cost of the connection is paid by the agent that gets profit from its existence. Symmetry states that symmetric agents should pay the same. Independence reallocation requires that if the cost of connecting two individuals is zero, both cannot benefit from reallocating productions and demands between themselves. Network-cost independence of extra costs refers to how to allocate punctual increments of the cost of a single link. Our first result identifies the rule that satisfies these four axioms. We call it the equal division across components rule, which works as follows. For each link l, if we remove l from the tree we have two connected components. The cost of l is divided among the components following the idea of fairness for two agents, but applied to each component. We compute the aggregate production and demand of both components. If the link is profitable for only one component, then this component pays the cost. If the link is profitable for both or nobody, then each component pays half of the cost. Once this is done, the payment of each component is equally allocated among the agents belonging to it. We apply the same reasoning to all the links of the tree and the contribution of an agent is the sum of his contributions in the removal of all links.
The second group of axioms we propose is the following. Cost additivity simply says that the rule is additive with respect to the cost function. Stand alone core states that the rule must select allocation within the core (whenever the core is not empty). An agent is safe in a tree when, in case of failure of his production, the other agents can fulfill its demand. After the removal of a link in the tree, the safe status of an agent may change. Balanced contributions with respect to the safe status requires that if the cost of a link increases, all agents with the same status with respect to such a link should be affected in the same way. In our second result we characterize the rule that fulfills the three previous properties. We call it the equal safety rule. This rule also specifies how to divide the cost of each single link. Now, the cost of a link is equally split among all the agents for whom such a link is necessary for their safety. If some link is not necessary for any agent then, the cost of the link is equally divided among all the agents. Again, the contribution of an agent is the sum of his contributions to all links of the tree.
We apply both rules to the design of a tariff system for the water transferred from Tagus river to Segura river in Spain. Even both rules are different, in this particular case coincide.
The rest of the paper is structured as follows. In Section 2 we present the model and the elements of the problem. In Section 3 we introduce the axioms we use in the rest of the paper. Sections 4 The equal division across components rule, 5 The equal safety rule are devoted to the characterizations we aforementioned. Finally, Section 6 concludes.
Section snippets
Model
Let be the (infinite) set of possible agents and . Usually we take where . A network g is a collection of unordered pairs in N, i.e., . When there is no room for confusion we denote the elements of g simply as ij instead of . The agents involved in the network are called nodes, while the pairs ij are called links. Given a network g, the set of links and nodes of g are denoted by and respectively. Given denotes the
Properties
In this section we introduce several properties that rules may satisfy. Most of them will be used later in the axiomatic characterizations.
The first property refers to a very simple situation. Suppose that there are only two agents and one link between them. Assume that the link is only profitable for one agent, then this agent pays the whole cost of the link. If the link is profitable for both or neither (recall that we are assuming that t is given), the cost of the link is equally divided
The equal division across components rule
In this section we introduce the equal division across components rule (EC, for short). We also provide an axiomatic characterization of this rule by mean of fairness for two agents, network-cost independence of extra costs, symmetry, and independence reallocation.
A very intuitive procedure to share the cost of the whole tree is to do it link by link, that is, we choose a link and we divide its cost among all the agents in N. We clarify this idea in the example below. Example 4.1 In the
The equal safety rule
We now introduce a new rule, called the equal safety rule (ES rule, for short). Our main result is a characterization of this rule in terms of stand alone core, balanced contributions with respect to safe status, and cost additivity.
Similarly to the solution we presented in the previous section, the equal safety rule, is based on deciding which is the contribution of each agent to every single link. More specifically, the cost of a link is equally split among all the agents for whom such a link
Concluding remarks
In this paper we study how to allocate the cost of a tree where agents are heterogenous. The heterogeneity emerges as a consequence of the different levels of production and consumption of a good. The model we propose has five elements, a set of agents, a tree that represents the possibilities of communication among the agents, a cost function, and the production and demand of each agent. The goal is to determine how to divide the overall cost of the tree among the agents taking into account
Acknowledgements
We thank J. Vidal-Puga, two anonymous referees, and the participants in the VIII Workshop on Social Decisions (Málaga) for their useful comments. Financial support from Spanish Government through Grants ECO2008-03484-C02-01, ECO2011-23460, and ECO2011-29355 is gratefully acknowledged. We also acknowledge financial support from Junta de Andalucía through Grants SEJ5980, SEJ4941, and Grupo PAIDI SEJ426.
References (27)
- et al.
A cost allocation rule for k-hop minimum cost spanning tree problems
Operations Research Letters
(2012) - et al.
A new rule for source connection problems
European Journal of Operational Research
(2014) - et al.
Optimistic weighted Shapley rules in minimum cost spanning tree problems
European Journal of Operational Research
(2008) - et al.
A generalization of obligation rules for minimum cost spanning tree problems
European Journal of Operational Research
(2011) - et al.
A fair rule in minimum cost spanning tree problems
Journal of Economic Theory
(2007) - et al.
Realizing fair outcomes in minimum cost spanning tree problems through non-cooperative mechanisms
European Journal of Operational Research
(2010) - et al.
Sharing the cost of a capacity network
Games and Economic Behavior
(2010) - et al.
Cost monotonicity, consistency and minimum cost spanning tree games
Games and Economic Behavior
(2004) - et al.
Minimum cost arborescences
Games and Economic Behavior
(2012) A game theoretical approach to sharing penalties and rewards in projects
European Journal of Operational Research
(2012)
Multi-criteria minimum cost spanning tree games
European Journal of Operational Research
Truth-telling and Nash equilibria in minimum cost spanning tree models
European Journal of Operational Research
Axiomatization of the Shapley value on minimum cost spanning tree games
Games and Economic Behavior
Cited by (8)
Sharing cost of network among users with differentiated willingness to pay
2023, Games and Economic BehaviorTrouble comes in threes: Core stability in minimum cost connection networks
2022, European Journal of Operational ResearchCitation Excerpt :The standard approach to fair division has been to formulate an associated cooperative game (see e.g., Peleg & Sudhölter, 2007) and use solution concepts from game theory such as the core and the Shapley value to guide allocation of costs and revenues. Since the seminal papers by Claus and Kleitman (1973) and Bird (1976), the minimum cost spanning tree model and its many variations have been particularly popular topics in cost and revenue sharing in networks (see e.g. Bergantiños & Martinez, 2014; Bergantiños & Vidal-Puga, 2007; Bogomolnaia, Holzman, & Moulin, 2010; Bogomolnaia & Moulin, 2010; Granot & Huberman, 1981; Hougaard, Moulin, & Østerdal, 2010; Tijs, Branzei, Moretti, & Norde, 2006; Trudeau, 2012; Trudeau, 2013). Implementation of minimum cost spanning trees has been studied in Bergantiños and Lorenzo (2004, 2005), Bergantiños and Vidal-Puga (2010), and Hougaard and Tvede (2012).
Loss allocation in energy transmission networks
2017, Games and Economic BehaviorCitation Excerpt :In Estevez-Fernandez (2012) it is allocated the penalty of delaying a project. In Bergantiños and Martínez (2014) it is allocated the maintenance cost of a network connecting some agents. In all these problems, and also in this paper, some cost allocation rules are studied in terms of the properties they satisfy.
Fair division of costs in green energy markets
2017, EnergyCitation Excerpt :Additionally, since this paper assumes that the exchange of electricity happens automatically, the grid in this paper is a so-called smart grid, which relates to integration of communication technologies into electrical power grids to make them “smarter”, see e.g. Ref. [9]. There is an extensive literature on cost allocation in networks (see e.g. Refs. [14], [17]): typically the network configuration plays a key role in the sense that agents' allocated share depends on their location in the network, see e.g., [3]. Such an approach is obvious for many types of networks, when there are no externalities between agents and costs are related directly to network usage.
Axiomatization of the counting rule for cost-sharing with possibly redundant items
2022, Social Choice and Welfare
- 1
Tel.: +34 987 29 1911; fax: +34 987 29 1746.