Cost-allocation problems for fuzzy agents in a fixed-tree network

The cost-allocation problem in a network considers a group of agents where each agent needs to be connected to a source either directly or via other agents. A feasible network connects all of these agents to the source and the costs for using all the links in the network are known. Cooperation of the agents is assumed in order to reduce the cost. In graph theory, classic algorithms that search for minimum spanning trees enable all the cheapest trees to be found for the agents. Claus and Kleitman (1973) introduce a second problem once a minimum spanning tree is chosen: how to allocate the minimum cost among the agents. This problem is known as the minimum cost spanning tree problem. Bird (1976) defined a rule to allocate the cost for this problem. This rule has been analyzed in several studies in the literature, including axiomatizations and generalizations (Feltkamp et al. 2000;Dutta and Kar 2004 ; Hougaart et al. 2013). Numerous rules have been defined for the minimum cost spanning tree problem: Granot and Huberman (1984), Feltkamp et al. (1994), Kar (2002), Dutta and Kar 2004, Bergantiños and Vidal-Puga (2007), Bogomolnaia et al. (2010), Juarez and Kumar (2013) or Norde (2019). A related problem introduced in Meggido (1978) describes the allocation of maintenance and usage costs of a fixed-tree network. This problem is called fixed tree cost-allocation problem and it has also been studied in Granot et al. (1996), and Koster et al. (2002) in the context of game theory. Bird’s rule (Bird 1976; Ertan et al. 2020) is based on a particular solution for each fixed minimum cost spanning tree of the network and then, it can also be used also for this problem. Several interesting families of rules that contain Bird’s rule have been defined. Chun and Lee (2012) introduced sequential contributions rules as a family of rules following a certain sequential way to determine the payoffs of the agents. In this context, Bird’s rule is named the sequential full contributions rule. Gellekom (2000) and Bergantiños and Gómez-Rúa (2010) introduced populations on the nodes in both problems, by assuming that there is a set of agents in each vertex (this population can also be empty).

This paper deals with cost-allocation problems in a fixed-tree. We propose a new generalization of the problem in the following sense. In the classic model, it is supposed that agents stay in the same node for the whole period of use and that these agents are using the network full time. However, an agent may not use the network all the time or to use it a third of the time in one node and the rest in another node. For instance, the clients in an intranet using mobile cloud computing can use applications in different points of the network. The population set in each vertex is now a fuzzy set. There exist other kind of solutions to this problem, such as in Dai et al. (2016).

In Sect. 2 several necessary preliminaries regarding fuzzy sets and the Choquet integral are given. Section 3 is dedicated to introducing cost-allocation problems in a fixed-tree with populations and a Bird’s rule for these situations is defined. The main problem is presented in Sect. 4. The position of the agents on the nodes is now variable. This kind of situation is known as a cost-allocation problem in a fixed-tree with fuzzy agents. Our objective in the next sections is to define a Bird’s rule as an extension of the classic rule (Sect. 5) and get an axiomatization of this rule (Sect. 6). Finally we have a section dedicated to discussion and conclusions.

Let N be a finite set. A fuzzy set (Zadeh 1965) s in N is determined by a membership function \( \tau _s:N\rightarrow \left[ 0,1\right] \) where \(\tau _s(i)\) is named the membership level of \(i\in N\) in s. The family of fuzzy sets in N is denoted as \(\left[ 0,1\right] ^{N}\). Each (crisp) subset \(S\subseteq N\) is also a fuzzy set with membership function \(e^{S}\), \(e^S\left( i\right) =1\) if \(i\in S\), and is \(e^{S}\left( i\right) =0\) otherwise. Specifically, we denote \(e^{\emptyset }=0\). The support of \( s\in [0,1]^N\) is \(\mathrm {supp}\left( s\right) =\left\{ i\in N:\tau _s\left( i\right) \ne 0\right\} \) and the image of \(\tau \) is the setIn this paper, the operators \(\wedge ,\vee \) are used as the minimum and the maximum, respectively. For all \(s_1,s_2\in [0,1]^N\), the standard operations between fuzzy sets become:If \(s\in [0,1]^N\), then \(\vee s=\vee \{\tau _s(i):i\in N\}\). If \(\uplambda \in (0,1]\) and \(s\in [0,1]^N\), then the \(\uplambda \)-cut is the crisp set Choquet (1953) introduced capacity as a monotonic set function \(v:2^N\rightarrow {\mathbb {R}}\) which verifies \(v(\emptyset )=0\). The Choquet integral with regard to a capacity is used as a way of measuring the expected utility of a fuzzy event. This integral was extended in de Waegenaere and Wakker (2001) to include capacities without monotonicity (non-monotonic capacities). Let v be a non-monotonic capacity, the (signed) Choquet integral of \(s\in [0,1]^N\) with regard to v is defined aswhere \(im(s)=\{\uplambda _1<\cdots <\uplambda _m\}\), \(\uplambda _0=0\), and \([s]_k=[s]_{\uplambda _k}\) for each \(k=1,...,m\). The properties of the Choquet integral that will be used include the following.

A fixed-tree network that connects a set of nodes with a source is assumed. The cost-allocation problem for this network determines how to allocate the costs for the usage or for maintenance by a group of clients. These problems commonly identify nodes and agents, by establishing one agent in each node. Bearing our objective in mind, however, these problems need to be applied in a wider sense. According to Gellekom (2000), each node contains a determined population of agents, and some of these populations can be empty.

We describe first the network. Given a finite set V, we denote \(LV=\{\{p,q\}:p,q\in V,p\ne q\}\) as the set of unordered pairs of different elements in V. A graph is a pair (V, L) where V is a finite set of nodes and \(L\subseteq LV\) is a set of links. A sequence of k different nodes \((p_{1},...,p_{k})\) is a path in the graph if \(\{p_{l},p_{l+1}\}\in L\) for \(l=1,...,k-1\). The graph is connected if for all \( p,q\in V\) with \(p\ne q\) there is a path \((p_{1},...,p_{k})\) in which \(p_{1}=p\) and \( p_{k}=q \). We say that (V, L) is cycle-free if, for every two different connected nodes \(p,q\in N\), there is only one path connecting p and q. A rooted tree (hereinafter, tree) is a connected cycle-free graph with a particular node \(\theta \), known as the source. We represent a tree as the graph \(g=(V\cup \{\theta \},L)\). The selection of a source determines a partial ordering over V, where \(p<_{g}q\) if p is in the unique path from \(\theta \) to q.

With a fixed \(p\in V\), we denote \(V^p=\{q\in V: q\le _g p\}\) and \(V_p=\{q\in V: q\ge _g p\}\). The height of a node \(p\in V\) in the tree is \(h_g(p)=|V^p|-1\). Each link \(\{p,q\}\in L\) is written as pq where p is the lowest node (initial node), and q the highest node (the end node). Furthermore, link pq is usually identified with its end node as \(pq=l_q\) since there is only one link with this condition. If \(p\in V\setminus \{\theta \}\), then \(g^p\) is the chain up to p, namely the unique path from \(\theta \) to p (also a tree), with set the intermediate nodes \(V^p\) and the corresponding links. Also \(g_p\) is the subtree from p, namely that uses all the nodes in \(V_p\), their corresponding links except \(l_p\), and now takes p as its source (see Fig. 1). Given a node \(p\in V\), there is only one node \(q\in V\cup \{\theta \}\) satisfying \(qp\in L\), since g is acyclic.

A cost-allocation problem in a fixed-tree is \(\gamma =(N,g,c,d)\), where N is a finite set of n agents using a network represented by a tree g, and where \(c:V\rightarrow {\mathbb {R}}_+\) is a cost function yielding the cost for usage for a certain period of the corresponding link \(l_p\) for each node p (different to the source). If \(|V|=r\) then \(d=\{S_1,...,S_r\}\) is a partition of N that determines the position of the agents in the network. Partition d can be represented by a matrix \(d=(d_{pi})_{r\times n}\) where \(d_{pi}=1\) if \(i\in S_p\) and \(d_{pi}=0\) otherwise, and where \(\sum _{p\in V}d_{pi}=1\) for all \(i\in N\). This kind of matrix is named partition matrix of N over V. For each \(p\in V\), set \(S_p\) is the group of those agents using p during the period. Set \(S_p\) can be empty. If we have only one agent placed in a vertex p, then this agent must pay the cost for using the corresponding links from the source to p, that is, the cost is \(\sum _{q\in V^p}c(q)\). Given \(\gamma =(N,g,c,d)\) a cost-allocation problem in a fixed-tree, we denote by \(V(\gamma )=\{p\in V: S_p\ne \emptyset \}\) and therefore the cost to allocate isA solution for a cost-allocation problem \(\gamma \) in a fixed network is a vector containing the payment that each agent must make to cover the cost of the problem, namely the vector is an allocation of \(c(\gamma )\) among the agents. There are numerous allocation rules giving a solution for each cost-allocation problem in a fixed tree. Bird (1976) introduced a rule in the context of the minimum cost spanning tree problems. We define Bird’s rule for our case in an easy way. If \(\gamma =(N,g,c,d)\) is a cost-allocation problem in a fixed tree then for each \(p\in V\) we denote \(V_p^{min}\) as the minimal nodes in \(V_p\cap V(\gamma )\) with regard to the ordering \(<_{\gamma }\), and \(N_p^{min}=\cup _{q\in V_p^{min}}N_q\). Observe that if \(p\in V(\gamma )\) then \(V_p^{min}=\{p\}\) and \(N_p^{min}=N_p\), otherwise \(V_p(\gamma )\) is the set of those nodes closest to p moving away from p, and \(N_p(\gamma )\) is the set of their populations. The sequential full contributions rule (Bird’s rule) defines for \(\gamma \) the paymentfor all \(i\in N\). This rule supposes that the cost of a link is paid by the agents in the first nodes from p moving away from the source (full contributions). Hence, although other agents may need this link in more remote nodes (because p lies on in the only path from \(\theta \)) they do not have to pay for using \(l_p\).

The fuzzy population \(s_p\) in a vertex p represents the membership level of the agents in vertex p, that is, for each \(i\in N\), number \(\tau _p(i)\), is the possibility of finding i in p. From now on we identify each fuzzy set s with its membership function \(\tau _s\) in order to simplify the notation of the paper. Therefore, we use \(\tau \) as s if \(\tau =\tau _s\).

Let \(\varGamma =(N,g,c,\tau )\in {\mathcal {G}}\). We introduce tree g by the adjacency matrix of g, \(e^g=(e^g_{pq})_{(r+1)\times r}\) where \(e^g_{pq}=1\) if \(pq\in L\), and \(e^g_{pq}=0\) otherwise. The first row is for \(\theta \), observe that there are not links with end node \(\theta \) and therefore no new column needs to be added. The fuzzy population \(\tau \) can also be introduced by a matrix \(\tau _{r\times n}\) with \(\tau _{pi}=\tau _p(i)\). Observe that agents can organize their needs for a period in any way. Each option determines a partition by levels of matrix \(\tau \). A partition by levels of \(\tau \) is a finite set of pairs \((\uplambda _k,d_k)_{k=1}^z\) where \(\uplambda _k\in (0,1]\), and \(d_k\) is a partition matrix of a subset \(N^k\) of N over V, that satisfiesNumbers \(\uplambda _k\) represent those moments when certain agents decide to change their positions in the tree. Each \(d_k\) is identified with a cost-allocation tree problem \(\gamma _k=(N^k,g,c,d_k)\) valid for a time of \(\uplambda _k\). The cost of the problem \(\varGamma \) is actually the minimum cost among all of the feasible partitions by levels,We will prove in Proposition 1 that algorithm given below obtains the worth of \(c(\varGamma )\) as a dynamical optimization problem.

During the algorithm process, matrix \(\tau \) changes. The last matrix \(\tau \) with all these changes provides information about the use that each agent of each node to connect with the source.

In Example 2 we first construct the usage matrixwhich is the last one in the algorithm (see Table 1). So, agent 2 needs link \(l_{p_3}\) at level 0.4.

We follow Bird (1976) to define an allocation rule for cost-allocation problems with fuzzy agents in a fixed-tree with the same philosophy: if agents and nodes are identified in a tree network then each agent pays only for his corresponding link (the corresponding link of his node). In the model considered in Sect. 3, the sequential full contributions rule translates this payer role for each node to the minimal non-empty nodes moving away from that node. Observe that, given a fixed node, the agents in nodes that remain at a great distance from the minimal nodes “cop out” of paying for its use. When we have fuzzy agents in each node, agents have different needs. Let \(\varGamma =(N,g,c,\tau )\) be a cost-allocation problem with fuzzy agents in a fixed-tree. Suppose \(p\in V\) with row \(\tau _p\ne 0\). Following Bird’s idea, while agents use the corresponding link \(l_p\) they have to pay and therefore we look for the minimum level in \(s_p\) and all the agents in the support of the fuzzy set must pay for this time. Then we find the next moment in \(s_p\) and agents in the support of the cut for this level pay for the differential time. Hence we are describing a Choquet integral (see Sect. 2). The question is what happens with the rest of agents in the support of \(\tau _p\) while this node is being paid. They can take this time to stay in other nodes in \(V_p\). We propose carrying out these moves by the following method: agents run away from the node covering their times in each height. Returning to Example 2 and take node \(p=p_1\). We consider graph \(g_{p_1}\) and join nodes with the same height as in Fig. 4. This graph is denoted by \(g^*_{p_1}\) (we call it chain of moves).

We transform \(\tau \) only to allocate the cost of link \(l_{p_1}\) into the matrixrepresenting the projection of \(\tau \) to the chain of \(p_1\). For 0.3, node \(p_1\) is inhabited by agents \(\{1,2\}\); following Bird, 0.15 of \(c(p_1)=12\) must therefore be paid by each of these players. Subsequently, only agent 1 stays at vertex \(p_1\). In this time, agent 3 uses any node in the following height (node 2 or 3) and he does not have to pay for node \(p_1\). At level 0.3, agent 2 changes his position and is now in any node in the second height, as is agent 3. So, the only inhabitant in node \(p_1\) is agent 1, who must pay for the link for \(0.5-0.3=0.2\) time. Meanwhile agents 2 and 3 use nodes in the second height and the next height if necessary. Hence, agent 1 pays for 0.35 time and agent 2 for 0.15. In this first step, we change matrix \(\tau ^{p_1}\)Now \(V_p^{min}\) (this set was defined in the crisp case, it is analogous with fuzzy agents) are in the second height and the corresponding agents must pay forvertices \(\{p_2,p_3\}\). Hence, they can be studied as only one vertex (see Fig. 4) and any option can therefore be used to delete time in the same height. The process is repeated. Coalition \(\{2,3\}\) pays until 0.4 and then 2 moves to the third height. Agent 1 is now in the last height and spends his needs of \(l_{p_1}\) in that height. Agent 1 then pays no more. After 0.4 the only inhabitant in the second height is agent 3, who pays for the use of \(l_{p_1}\) with coefficient 0.1. Agent 2 now uses the last height and then no longer has to pay for \(l_{p_1}\). We obtainTo the above payments, 0.2 is added to agent 2 and 0.3 to agent 3. Agents have to pay for this node \(c(p_1)\cdot \max \{\tau ^{use}_{1i} \}=12\) and this payment is allocated as \(12\cdot (0.35,0.35,0.3)=(4.2,4.2,3.6)\). The process is repeated with each node. The idea can be formalized.

First, we formalize the concept of chain of moves in a node.

Second we introduce the capacity to allocate the payment equitably.

Finally, an algorithm is introduced to decrease time in a tree from a node. We consider \(t=(t_i)_{i\in N}\in [0,1]^N\) as a vector with the time that can be reduced for each agent.

A Bird’s rule for fuzzy agents is designed using capacities \(v_i\) for the agents, the algorithm WALK, and the chains of moves.

In this section, we introduce several properties of the fuzzy sequential full contributions rule. These properties will be used as axioms to determine the rule.

Let f be a rule for cost-allocation tree problems with fuzzy agents, namely a function that obtains a payoff vector \(f(\varGamma )\in {\mathbb {R}}^N\) for each \(\varGamma =(N,g,c,\tau )\). Obviously, we are searching for an allocation of the cost of the problem.

Efficiency. Rule f satisfies efficiency if, for all \(\varGamma \in {\mathcal {G}}\), it holdsA node \(p\in V\) is called non-free in \(\varGamma \) if \(\sum _{q\in V^p}c(q)>0\), namely not all the links in the path from the root to p have no cost. An agent \(i\in N\) is a null agent in \(\varGamma \) if \(\tau _{pi}=0\) for all non-free node p. Null agents pay nothing.

Null agent. If \(i\in N\) is a null agent in \(\varGamma =(N,g,c,\tau )\) then \(f_i(\varGamma )=0\).

If two agents have the same needs in all of the non-free nodes of the tree, then we can suppose that they should pay the same quantity.

Equal treatment. If \(i,j\in N\) satisfy \(\tau _{pi}=\tau _{pj}\) for every non-free node \(p\in V\) in a problem \(\varGamma =(N,g,c,\tau )\) then \(f_i(\varGamma )=f_j(\varGamma )\).

The following property implies good mathematical condition. Additivity implies a differentiated treatment for each problem even if the agents, the tree, and their needs are the same.

Additivity. For all \(\varGamma , \varGamma '\in {\mathcal {G}}\) with \(\varGamma =(N,g,c,\tau )\) and \(\varGamma '=(N,g,c',\tau )\)where \(\varGamma +\varGamma '=(N,g,c+c',\tau )\).

The contraction property in cost problems in trees describes when it is possible to contract a link by adding information from the last node to the first node. Let \(\varGamma =(N,g,c,\tau )\in {\mathcal {G}}\). Suppose that \(p\in V\) with \(c(p)\ne 0\) and \(\tau _p=0\) satisfies \(c(q)=0\) if \(q<_g p\) or \(h_{g_p}(q)=1\): that is, it is a minimal non-null node (with non-empty support in \(\tau \)) in the tree and its nearest nodes are null. In this situation the elimination of the nodes is possible in the first height from p by contraction; we call a node under these conditions as node in a contraction situation. If p is a node in a contraction situation, then we denote \(\varGamma '=(N,g',c',\tau ')\) such thatThis notation may be cumbersome but the concept can be viewed in a simple way with a diagram, see Fig. 5.

Height contraction. Following the above notation, for all \(\varGamma =(N,g,c,\tau )\in {\mathcal {G}}\) and \(p\in V\) in a contraction situation, it holds \(f(\varGamma )=f(\varGamma ')\).

The last axiom is based on a known property of Bird’s rule: consistency in the first node (Chun and Lee 2012). However, in our case, the first node is considered to be the first step of payoff. We assume a problem \(\varGamma =(N,g,c,\tau )\) with only one node p satisfying \(c(p)\ne 0\). Let \(\text {im}(\tau _p)=\{\uplambda _1<...<\uplambda _m\}\) and \(M(p)=\{i\in N: \tau _{pi}=\uplambda _m\}\). We now introduce the following two new problems: \(\varGamma ^{node\, p}=(N,g,c,\tau ^{\text {node }p})\) and \(\varGamma ^{step\,1}=(N,g,c,\tau ^{step\,1})\), whereObserve the new problems after the first step in the next example. Figure 6 has a unique node \(p_1\) with non-null cost.

Consistency dictates that, in the example, 0.2 of \(c(p_1)\) must be paid only by agent 1.

Consistency in the first step Let \(\varGamma =(N,g,c,\tau )\in {\mathcal {G}}\) with only one non-null cost c(p). Following the above notation,We now prove that our rule satisfies all the properties.

Now we prove that there is only one rule that satisfies these properties.

In this paper we have presented a new problem related to the maintenance of a network used by several agents. Once a minimum cost tree network is constructed the problem to be solved is how to distribute the costs due to the use of the network among the users. The classical form problem has been posed with a fixed population of agents at each node of the tree, Granot et al. (1996) assumed that there was a single player at each vertex while ? introduced the idea that at a vertex there may be a certain population. In reality, the incorporation of more than one agent in a node does not mean an important variation in the model, but this second version also allowed the appearance of vertices without population, which modified the formulation of the distribution rules and their axiomatizations. Our model generalizes both (an empty p node means in our case to take the fuzzy set with membership function \(\tau _p=0\)) but also allows to analyze situations where agents have interests distributed over the set of nodes during the maintenance billing time. The construction of Bird’s rule for this case is a sample of how to approach the elaboration of partitioning solutions for these situations and the complications they entail from the algorithmic and axiomatic point of view.

The situation we have posed is restricted to considering known fixed costs per full-time billing period and assuming that the costs of any percentage of different usage have a proportional cost. Therefore such cost can be generalized either by an increasing cost function over the interval [0, 1] or even with a fuzzy-valued cost function.

As mentioned above, the article focuses on maintenance costs once the tree is already built. An interesting problem that opens up in the future is to pose the same situation of agents with distributed interests in the vertices for the previous elaboration of the network, i.e. a new version of the problem of sharing the costs of elaborating a minimum-cost spanning tree. The problem of finding a minimum cost spanning tree has been studied with fuzzy costs in Janiak and Kasperski (2008); Zhou et al. (2016) or Dehpande and Chaudhari (2020) while the distribution of the costs of such a tree by cooperative game theory has been addressed (with interval payments) by Moretti et al. (2011). The situation that may arise in view of the article is obviously not the same. In fact, it would not change the first step, i.e. finding a minimum cost tree to build the network. But the formulation of the cost sharing rule should be modified, since in this case the object represented by a fuzzy set is not the cost, but the situation of the agents.

The model can also be exported to problems not necessarily related to networks, such as the minimum cost consensus model (Gong et al. 2021). This article gives as an example the problem of finding a fair charge between coal companies and the State for the cost of ecological damage. Consideration could be given to taking into account as real agents the investors behind the companies, among whom there may be some with stakes in several of them.