# Incentives against Max-Min Fairness in a Centralized Resource System

Authors: Zheng Chen; Zhaoquan Gu; Yuexuan Wang
Journal: Wireless Communications and Mobile Computing
 (2021)

---

## Abstract

Resource allocating mechanisms draw much attention from various areas, and exploring the truthfulness of these mechanisms is a very hot topic. In this paper, we focus on the max-min fair allocation in a centralized resource system and explore whether the allocation is truthful when a node behaves strategically. The max-min fair allocation enables nodes receive appropriate resources, and we introduce an efficient algorithm to find out the allocation. To explore whether the allocation is truthful, we analyze how the allocation varies when a new node is added to the system, and we discuss whether the node can gain more resources if it misreports its resource demands. Surprisingly, if a node misrepresents itself by creating several fictitious nodes but keeps the sum of these nodes’ resource demands the same, the node can achieve more resources evidently. We further present some illustrative examples to verify the results, and we show that a node can achieve1.83 times resource if it misrepresents itself as two nodes. Finally, we discuss the influence of node’s misrepresenting behavior in tree graph: some child nodes gain fewer resources even if their parent node gains more resources by creating two fictitious nodes.


---

## Body

## 1. Introduction

Fairly allocating limited resources (such as fossil fuels, clean water, and cyber source) has been widely studied. With so many competing needs and demands, lots of relevant works have been done. In early 1940s, considering the notion of proportionality, Steinhaus put forward a method to ensuren participants receive at least 1/n of each participant’s own value for getting everything [1]. In a 1958 book of mathematical, Gamow and Stern [2] introduce the formal notion of “envy-freeness,” in which participants preferring to keep their own allocation to swapping with other participants. Since then, research in this area has aroused widespread concern and has been applied to solve many important real-world problems [3–5].Motivated by sharing economy concepts [6], nodes in a multiagent system may take strategic behaviors to gain larger utility. In [7], it proves that designing a truthful mechanism that guarantees a market equilibrium outcome in general is impossible when an agent has the incentive to misreport its information (such as its resource amount or demand). Some extant works also show that the truthfulness of resource allocating mechanisms cannot hold for a cheating node [8, 9]. However, the impossibility theorem proposed in [7] is not always correct for some restricted settings. For example, the proportional sharing mechanism is proved to be robust to agents’ cheating, including an agent misreporting its resource or the connectivity with the rest of network [10, 11].In this paper, we explore the truthfulness of resource allocation in a restricted setting. We consider a centralized resource system where only a central controller holds the resources that can be allocated to other nodes. Each node reports its resource demand to the controller who is in charge of allocating appropriate resources to the node. For example, each computer in a cluster of data center may require some resources while the central controller would make a fair resource allocation to all computers. In order to evaluate the fairness of a resource allocation, we adopt the concept ofmax-min fairness (a widely used concept in networks, such as window flow central protocols [12], packer-switched network [13], and data network [14]) and explore whether the max-min fair allocation in the centralized resource system could be truthful if a node behaves strategically.To begin with, we study the property of max-min fair allocation and introduce an efficient algorithm to find out the resource allocation mechanism. Afterwards, we explore how the nodes would be affected if a new node is connected to the controller. To study the truthfulness of the max-min fair allocation, we assume the new node could misreport its resource demand, and we analyze how this behavior changes the other nodes’ allocation. In addition, we explore the effect of a novel splitting strategy that is proposed in recent work [15], where a node misrepresents itself by creating several fictitious agents but keeps the sum of the nodes’ resource demand unchanged.We summarize the contributions of the paper as follows:(1)
We introduce a simple and straightforward algorithm to find out the max-min fair allocation in a centralized resource system(2)
When a new node is connected to the controller, we analyze how much resource the new node could receive and how the other nodes’ resource would be affected(3)
We explore the truthfulness of the max-min fair allocation. If the new node misreports its resource demand, we show that it cannot gain more resources through this strategic behavior(4)
We analyze the effect of node’s misrepresenting behavior. By splitting itself into multiple nodes, a node could gain more resources in the allocation. Specifically, if a node is split into two nodes, it can achieve about two times resource compared to the allocation that it is honest under some special situations(5)
We analyze the effect of node’s misrepresenting behavior for its child nodes on tree graph. Resources are passed down from the root node layer by layer. By splitting itself into two nodes, its child node gains fewer resources in the allocation under some special situations even if it received more resources from its parent nodeWe also present some numerical examples to illustrate these interesting results, and the examples show that the splitting strategy could indeed help a node gain about1.83 times resource if it is split into two nodes (as shown in Table 1). What is more, some numerical examples are presented to show the influence of parent’s splitting strategy on its child on tree graph. Some children gain fewer resources by its parent’s splitting strategy.Table 1
The max-min allocation aftervδ is split into two nodes.
Nodeimitixcvixcvi·tiuiv1353153v2454204v35105505v4757357v58585/12≈7.083425/1285/12v69585/12≈7.083425/1285/12vp18185/12≈7.08385/1285/12vp29185/12≈7.08385/1285/12The rest of the paper is organized as follows. The next section lists some related works about truthfulness of resource exchanging and allocation mechanisms. The preliminaries are introduced in Section3. We present the efficient algorithm that finds out the max-min fair allocation in Section 4. When a new node is connected to the controller, we analyze the change of the allocation in Section 5. The truthfulness of the allocation is discussed in Section 6 if the new node misreports its resource, while the splitting strategy that could help gain more resources is analyzed in Section 7. The effect of node’s splitting strategy for its child nodes on tree is analyzed in Section 8. Finally, we present some numerical examples in Section 9 and conclude the paper in Section 10.


## 2. Related Work

The star network is generic and representative for many communication or economic networks. For example, the star network is commonly used in clustering of multityped heterogeneous networks [16], which extend the classical clustering on bityped heterogeneous networks [17]. Various networks have been mapped to the star networks [18], and we study the problem on the star network.There are lots of researches about resource allocation in centralized system. One of the most critical resource allocating problems is the cake-cutting problem that is dividing a birthday cake among several children. During the World War II, Steinhaus, Knaster et al. [1] initiated the study of fair cake-cutting algorithms. How to help players achieve fair allocations is one of the most important strands in cake-cutting problem. Since then, a large number of related studies have emerged [5, 19, 20].In resource exchange networks, max-min fairness is a simple and well-recognized approach to define a fair allocation in network [21–24], which has been widely adopted in economics [15, 25]. It is also used in ant colony algorithm for load balancing in could systems [26], and it is combined with convolutional neural networks for image classification [27].In resource exchange networks, agents may be strategic, which makes the truthfulness of allocation mechanism being of paramount importance. In order to gain larger utility, an agent may misreport its true information, which may affect the market equilibrium. In [7], the authors prove that it is impossible to design a truthful mechanism that guarantees a market equilibrium outcome in general. In a Fisher market game with linear utility, agents can unilaterally deviate and get a better payoff [8]. Even more specifically, agents may double its benefit by strategic behaviors [9]. Therefore, we also discuss about the truthfulness of the max-min fair allocation in a star network in this paper.Generally, there are two types of agent strategic behaviors: misreporting its own resource amount and cheating on its connectivity with the rest of the network. By cheating on the connectivity, such as a missing edge or splitting a node into multiple nodes may affect the resource allocation mechanism. In [28], it examines the incentive problem in mechanism design in Internet applications or peer-to-peer systems when an agent misrepresents itself by creating several fictitious agents, which is also called false name bid. In [29], it measures how an agent gains if it deviates from its truthful behavior. In [30], it shows that agents’ selfish behavior may contribute to the loss of social efficiency in Nash equilibrium in comparison to social optimality. In this paper, we adopt the splitting strategy to gain more resources in a star network.


## 3. Preliminaries

Consider a centralized resource systemG=V,E where a central node c holds the resources Wc that can be allocated to the other nodes E\c=v1,v2,⋯,vn. For any node vi,i∈1,n, denote mi as the largest amount of resource vi can receive (we regard it as resource demand or resource limitation). Considering an allocation mechanism, denote xcvi as the amount of resources node vi receives from the central node, xcvi≤mi; denote ti≥1 as the resource transfer rate due to the link quality between the nodes. We assume that the resources would decay along the link, and thus, the central node actually allocates xcvi·ti resources to node vi (in traditional resource exchange or allocation mechanisms, we can set ti=1). Hence, ∑i=1nxcvi·ti≤Wc. Denote ui as the utility of node vi after receiving the resources from the central node, which can be represented by ui=fxcvi where f· is a monotone increasing function. For simplicity, we assume ui=xcvi in this paper and denote U=u1,u2,⋯,un as the utility vector. To explore the effect of nodes’ strategic behavior, we denote sv as the reported strategy of node v, s⟶=sv1,sv2,⋯,svn as the nodes’ reported strategy profile and s⟶−v=sv1,sv2,⋯,sv−1,sv+1,⋯,svn as the profile without node v. We denote Uvsv,s⟶−v as the utility of node v when it reports its strategy as sv. The problem is to explore the truthfulness of the centralized max-min fair resource allocation problem. First, we are to find a max-min fair allocation vector X⟵cv=xcv1,xcv2,⋯,xcvn. To begin with, we introduce the property of max-min fairness.Definition 1 (see [31]).
A vectorx⟵ is a max-min fair vector on set χ if and only if for all y⟵∈χ, if there exists s∈1,2,⋯,n such that ys>xs, there must exist t∈1,2,⋯,n such that yt<xt<xs.The definition of a max-min fair vector reveals that increasing some element of a max-min fair vectorx⟶ must be at the expense of decreasing some smaller (or equal) element of the vector.Definition 2 (see [32]).
A setχ is max-min achievable if there exists a max-min fair vector on χ.The following proposition shows the uniqueness property of the max-min fair vector. If we can find out a max-min fair vector, it is the unique one.Proposition 3 (see [31]).
If a max-min fair vector exists on a setχ, then it is unique.Definition 4.
A mechanism is truthful if no agent can benefit strictly from misreporting its amount of resource irrespective of what is reported by other agents.
Formally, given a nodev with true strategy sv∗ and the profile s⟶=sv,s⟶−v, it holds that for any reported strategy sv,
(1)Uvsv,s⟶−v≤Uvsv∗,s⟶−v.In this paper, we first design a mechanism that finds out the max-min fair utility vector in a centralized resource system. Then, we explore the effect of two strategic behavior: misreporting and misrepresenting. We formalize the problems as:Problem 5.
Considering a centralized resource systemG=V,E where the central node holds resource Wc that can be allocated to n nodes v1,v2,⋯,vn. The problem is to design an allocation mechanism such that the utility vector U=u1,u2,⋯,un is the max-min fair vector.The problem is equivalent to finding out the max-min fair allocation vectorXcv⟶=xcv1,xcv2,⋯,xcvn. If one node vi gets more resources through another allocation mechanism, another node vj who receives fewer resources than vi (i.e., xcvj<xcvi) would get resources fewer than xcvj in the new mechanism; this implies that increasing a node’s resource of the max-min fair allocation would reduce a node’s resource who originally receives fewer resources.The max-min fair allocation mechanism could ensure the fairness among the nodes. When the system changes, such as a new node is connected to the central node, how many resources the new node should receive and will the other nodes be affected? This is the second problem we study. We formulate the problem as follows.Problem 6.
Considering a centralized resource systemG=V,E and the max-min fair allocation vector Xcv∗⟶=xcv1∗,xcv2∗,⋯,xcvn∗, if a new node vδ with resource limitation mδ and transfer rate tδ is connected to the central node, find out the max-min fair allocation vector Xcv⟶=xcv1,xcv2,⋯,xcvn,xcvδ and how the nodes are affected.In practice, some nodes may cheat to gain more resources. A simple cheating strategy is to misreport its resource limitationmδ. We also analyze the truthfulness of the new node in Problem 6 and show that misreporting cannot help gain more resources (see Section 6). Therefore, we propose the splitting strategy to gain more resources as the following problem.Problem 7.
Considering a centralized resource systemG=V,E, if a new node is connected to the central node with resource limitation mδ and transfer rate tδ, we denote the max-min fair allocation vector as Xcv⟶=xcv1,xcv2,⋯,xcvn,xcvδ. If the node is assumed to be split into two nodes vnp1,vnp2 with resource limitations mnp1,mnp2 (mnp1+mnp2=mδ) and the same transfer rate tδ, find out the max-min fair allocation and analyze whether the node can gain more resources (xcvnp1+xcvnp2) compared to the received resource of the original allocation (xcvδ).


## 4. The Max-Min Fair Allocation Algorithm

We present the max-min fair allocation algorithm as Algorithm1. The input of the algorithm is the resource limitation of each node m⟶=m1,m2,⋯,mn and the resource transfer rates t1,t2,⋯,tn. The algorithm is to find the max-min fair vector U⟶=u1,u2,⋯,un, which is equivalent to the allocation vector X⟶cv=xcv1,xcv2,⋯,xcvn.As depicted inAlgorithm1, m⟶ is firstly sorted by increasing order (line 3) and denotes the corresponding nodes as v1′,v2′,⋯,vn′ where mi′≤mj′ for any i<j. The resources are allocated to nodes from v1′ to vn′ according to lines 5-9. There are two situations: if the resources are adequate enough (line 5), node vi′ can receive the resources that are up to its limitation mi′ (line 6), or it is set as line 8. We show that the correctness of the algorithm by verifying the allocation vector X⟶cv=xcv1,⋯,xcvn (corresponding to the utility vector U⟶=u1,u2,⋯,un) is the max-min fair vector.Theorem 8.
The output vector of Algorithm1 is the max-min fair vector.Proof.
For simplicity, we assume the input vectorm⟶ is already ordered such that vi′=vi. We prove the theorem from two situations.☐For the first case, supposeWc≥∑j=1ntjmj, which implies the central node has enough resources to ensure all nodes’ resource demands can be satisfied. Thus, Xcv⟶=m1,m2,⋯,mn. According to the definition of max-min vector, any element of the Xcv⟶ can not be larger; hence, Xcv⟶ is the max-min fair vector.Algorithm 1: The max-min fair allocation algorithm.
1: Inputm⟶=m1,m2,⋯,mn,t⟶=t1,t2,⋯,tn2: OutputU⟶=u1,u2,⋯,un3: Sortm⟶ by increasing order as m′⟶=m1′,m2′,⋯,mn′, where m1′,≤mj′,∀i<j; denote the corresponding nodes as v1′,v2′,⋯,vn′;4:fori⟵1tondo5:if∑j=1i−1tj′·mj′+mi′,∑j=intj′≤Wcthen6:xcvi′=mi′7:else8:fork⟵itondo9:xcvk′=Wc−∑j=1i−1tj′·mj′/∑j=intj′, uk′=xcvk′10:end for11:  break;12:end if13:ui′=xcvi′;14:end forFor the second case, supposeWc<∑j=1ntjmj; there must exists i∈1,n such that ∀j<i, xcvj=mj, and xcvi=Wc−∑j=1i−1tjmj/∑j=intj<mj since Algorithm 1 computes xcvi sequentially from i=1 to i=n. Then, we derive the output of Algorithm 1 as
(2)X⟶cv=m1,⋯,mi−1,Wc−∑j=1i−1tjmj∑j=intj,⋯,Wc−∑j=1i−1tjmj∑j=intj.For any other allocation vectorX⟶cv∗=xcv1∗,⋯,xcvn∗, if there exists s∈1,n such that xcvs∗>xcvs, for any t∈1,n satisfying xcvt<xcvs, suppose xcvt∗≥xcvt; then, we have xcv1∗t1+⋯+xcvn∗tn>xcv1t1+⋯+xcvntn=Wc, which leads to a contradiction since the allocation exceeds the amount of all resources Wc. Therefore, there exists t∈1,n such that xcvt∗<xcvt<xcvs. By Definition 1, X⟶cv is the max-min fair vector.Combining the two cases, the theorem holds.From Proposition3, the max-min fair vector is unique, and Algorithm 1 can find out the vector efficiently. We analyze the complexity of Algorithm 1 briefly. The complexity of sorting on line 3 is Onlogn, and the complexity of computing each xcvi in each step (lines 5-9) is O1. Thus, the complexity of the algorithm is Onlogn+n=Onlogn. In [32], the Max-Min Programming Algorithm (MP) is proposed to find the smallest element of the max-min fair vector by solving several linear programming. The complexity of MP algorithm is OnLPn,m where LPn,m is the complexity of a linear program. Considering the problem we study in the paper, MP algorithm can be applied to find out the max-min allocation vector, but it works much slower than Algorithm 1. In the following parts, we adopt our algorithm to find out the max-min allocation mechanism when a new node is inserted or a node is split into multiple nodes.


## 5. Resource Allocation Varies for a New Node

In a centralized resource systemG=V,E with the max-min fair allocation vector Xcv∗⟶=xcv1∗,xcv2∗,⋯,xcvn∗, if a new node vδ is connected to the central node whose resource limitation is mδ and transfer rate is tδ, denote the max-min fair allocation vector of the new system as Xcv⟶=xcv1,xcv2,⋯,xcvn,xcvδ. We analyze the relationship between Xcv∗⟶ and Xcv⟶, which implies how the nodes’ resources change regarding to the new inserted node.LetR be the spare resources under the max-min fair allocation vector Xcv∗⟶ before the new node is inserted; we formulate it as
(3)R=Wc−∑j=1nxcvjtj.For simplicity, we suppose the nodes’ resource limitations satisfym1≤m2≤⋯≤mn. We analyze how the max-min fair allocation changes when node vδ is added to the system from two cases:
(i)
Case 1. R≥tδmδ(ii)
Case 2. 0≤R<tδmδTo begin with, we introduce a property of the max-min allocation mechanism which implies that the nodes with fewer received resources remain the same if a node with more resources does not change.Property 9.
In the max-min allocation, if there existsk∈1,n such that xcvk=mk, for all i∈1,k, xcvi=mi.Proof.
Suppose there existsi∈1,k satisfying xcvi<mi, according to the allocation algorithm (Algorithm 1),
(4)∑j=1i−1tjmj+mi∑j=intj>Wc,since i<k, we can derive
(5)∑j=1k−1tjmj+mk∑j=kntj=∑j=1i−1tjmj+∑j=ik−1tjmj+mk∑j=kntj≥∑j=1i−1tjmj+mi∑j=intj>Wc,hence xvuk<mk, which makes a contradiction.☐We analyze how the max-min fair allocation varies for the first case.Theorem 10.
IfR≥tδmδ, the new allocation holds xcvδ=mδ, and xcvi=mi does not change when the new node vδ is inserted.Proof.
WhenR≥tδmδ, the spare resources are enough. It is obvious that Wc≥tδmδ+∑j=1ntjmj. Suppose there exists i satisfying mi−1≤mδ≤mk (if mδ≤m1, we let m0=0, and such i exists), we derive
(6)∑j=1i−1tjmj+tδmδ+mδ∑j=intj≤tδmδ+∑j=1ntjmj≤Wc.
According to lines 5-8 of Algorithm1, xcvδ=mδ. From Property 9, xcvj=mj when 1≤j≤i−1, mj≤mδ. For any k∈i,n where mk≥mδ, we can compute
(7)mδtδ+∑j=1k−1tjmj+mk∑j=kntj≤mδtδ+∑j=1ntjmj≤Wc.
Hence,(8)mk≤Wc−∑j=1k−1tjmj−mδtδ∑j=kntj,from lines 5-8 of Algorithm 1, xcvk=mk. The proof for the special cases mδ≤m1 and mδ≥mn is similar, and we omit the details. Combining these aspects, the theorem holds.☐We then analyze how the max-min fair allocation varies for the second case when0≤R<tδmδ. First, we find out a threshold r such that the nodes with resources fewer than r do not change their received resources (Lemma 11). Then, we analyze the change of nodes who received resources larger than r from two cases: mδ>r (Lemma 12) and mδ≤r (Lemma 13). Finally, we compute the allocated resources of the new inserted node vδ (Lemma14).Lemma 11.
IfR<tδmδ, there exists r=Wc−∑j=1i−1tjmj/∑j=intj+tδ such that any node vi,i∈1,n satisfying mi≤r, xcvi=mi under the new max-min fair allocation vector.Proof.
Supposem1≤m2≤⋯≤mi−1≤r≤mi≤⋯≤mn, we derive
(9)∑j=1i−2tjmj+mi−1∑j=i−1ntj+tδmi−1≤Wc,hence
(10)mi−1≤Wc−∑j=1i−2tjmjtδ+∑j=i−1ntj.
Then, we find the largest integeri−1 satisfying the above inequality, and we derive
(11)r∑j=intj+tδ=Wc−∑j=1i−1tjmj.
Thus, we figure out the threshold valuer as
(12)r=Wc−∑j=1i−1tjmj∑j=intj+tδ.
Sincexcvi−1=mi−1, for any node vk with mk≤mi−1≤r, xcvk=mk by property 5. The lemma holds.☐It is easy to check that the nodevk with mk≤r received resources xcvk∗=mk in the original allocation vector before the new node is inserted. Finding out the threshold value r, these nodes’ received resources do not change. For the nodes vk with mk<r, we analyze them from two cases: mδ>r and mδ≤r.Lemma 12.
IfR<tδmδ, mδ>r=Wc−∑j=1i−1tjmj/∑j=intj+tδ, for any node vi,i∈1,n satisfying mi>r, xcvi<xcvi∗≤mi under the new max-min fair allocation vector.Proof.
First, we show thatxcvi<mi under the new max-min fair allocation for any node vi satisfying mi>r. This means the threshold r divides the nodes into two subsets; one subset contains nodes that receive resources up to its limitation as Lemma 11, while the other subset consists of nodes with resource limitation larger than r and cannot receive resources up to its limitation.
Suppose there exists a nodevk such that mk>r and xcvk=mk. According to Property 9, node vi (v∈1,k−1) receives resources xcvi=mi.
There are two cases:mk≥mδ and mk<mδ. For the first case that mk≥mδ, we drive
(13)∑j=1k−1tjmj+mδtδ+mk∑j=kntj>∑j=1k−1tjmj+rtδ+r∑j=kntj=Wc,which is a contradiction. When mδ>mk, we can deduce a contradiction similarly. Therefore, xcvi<mi for node vi with mi>r.
Then, we show that nodevi with mi>r receives fewer resources compared to the original max-min fair allocation; that is, xcvi<xcvi∗. Denote xcvi∗=α, suppose xcvi≥xcvi∗=α, we can derive
(14)∑j=1i−1tjmj+mαtδ+α∑j=intj>∑j=1i−1tjmj+α∑j=intj>Wc,which is a contradiction.
Combining the two sides,xcvi<xcvi∗≤mi holds.☐Lemma12 implies that if the new node’s resource limitation is large mδ>r, all nodes with large resources limitation (mi>r) have to reduce its received resources. If mδ≤r, fewer nodes have to reduce its resources, and we show it in the next lemma.Lemma 13.
IfR<tδmδ, mδ≤r=Wc−∑j=1i−1tjmj/∑j=intj+tδ, there exists r1≥r such that the following two results hold:
(i)
If nodevi satisfies mi>r1, xcvi<xcvi∗≤mi(ii)
If nodevi satisfies mi≤r1, xcvi=xcvi∗=miProof.
Ifmδ≤r, there exists i1≤i2 such that m1≤m2≤⋯≤mi1−1≤mδ≤⋯≤mi2−1≤r≤mi2≤⋯≤mn; we have
(15)∑j=1i2−1tjmj+mδtδ+mi2−1∑j=i2ntj≤∑j=1i2−1tjmj+rtδ+∑j=i2ntj≤Wc,thus xcvi2−1=mi2−1. According to Property 9, xcvk=mk if k≤i2−1, which implies xcvδ=mδ. Since R<tδmδ, nodes with more resources would reduce its resources, and there must exist r1≥mi2−1 such that xcvk=xcvk∗=mk if mk≤r1 (nodes do not change their resources), and xcvk<xcvk∗≤mk if mk>r1 (nodes reduce their resources).
Next, we show that the valuer1≥r. It is clear that if r1≥mi2, r1>r. Suppose mi2−1≤r1<mi2, we derive
(16)r1∑j=i2ntj+mδtδ=Wc−∑j=1i2−1tjmj,combining the formulation of r, we show that
(17)r1−r∑j=i2ntj=r−mδtδ≥0.
Thus,r1≥r holds. It is easy to check node vk with mk≤r1 receives resources xcvk∗=mk in the original allocation. Finding out the threshold value r1, these nodes’ received resources do not change. Under the new max-min fair allocation, the node vk with mk>r1 receives resources xcvk<xcvk∗≤mk, and the proof is similar to that of Lemma 12.☐Lemma 14.
IfR<tδmδ, there exists r=Wc−∑j=1i−1tjmj/∑j=intj+tδ such that xcvδ=mδ if mδ≤r, and xcvδ<mδ if mδ>r.Proof.
According to the proof of Lemma13, xcvδ=mδ if mδ≤r. We show that xcvδ<mδ if mδ>r.
Supposem1≤m2≤⋯≤mi1−1≤r≤⋯≤mi2−1≤mδ≤mi2≤⋯≤mn, if xcvδ=mδ, we derive
(18)∑j=1i2−1tjmj+mδtδ+mδ∑j=i2ntj>∑j=1i2−1tjmj+rtδ+r∑j=intj=Wc,which is a contradiction. Thus, the lemma holds.☐Combining Lemmas11, 12, 13, and 14, we conclude the situation when the spare resources are inadequate 0≤R<tδmδ as Theorem 15.Theorem 15.
If0≤R<tδmδ, there exist two thresholds r,r1 as Lemma 11 and Lemma 13. If mδ>r, the nodes satisfy:
(19)xcvi=xcvi∗ifmi≤r,xcvi<xcvi∗≤miifmi>r,xcvδ<mδ.
Ifmδ≤r, the nodes satisfy:
(20)xcvi=xcvi∗ifmi≤r1,xcvi<xcvi∗≤miifmi>r1,xcvδ=mδ.


## 6. Truthfulness against the Misreporting Strategy

In this section, we analyze the truthfulness of the max-min fair allocation. DenoteX⟶cv=xcv1,xcv2,⋯,xcvi−1,xcvδ,xcvi,xcvn as the allocation after the new node vδ is inserted. Denote M⟶=m1,m2,⋯,mi−1,mδ,mi,⋯,mn as the resource limitation vector where the new node’s limitation suits mi−1≤mδ≤mi. Denote M⟶−u=m1,m2,⋯,mn as the vector before the new node is inserted. We study how the allocation varies when the new node misreports its resource limitation.As shown in the previous section, the allocated resourcesxcvδ of the new node vδ can be regarded as a function of mδ when M⟶−u is fixed. Suppose the new node misreports its resource limitation as mnt; we analyze the effect from two situations R≥tδmδ (the spare resources are adequate) or R<tδmδ.Lemma 16.
WhenR≥tδmδ, if the new node reports fewer resources mnt∈0,mδ,xcvδ=mnt; if the node reports more resources (mnt∈mδ,+∞), at most r−mδ resources would be wasted where r=Wc−∑j=1i−1tjmj/∑intj+tδ.Proof.
According to Theorem 2,xcvδ=mnt for any mnt∈0,mδ under the max-min fair allocation; this implies that the node would receive fewer resources if it reports fewer. If the node reports more resources, the central node may allocate more resources, but the resources beyond its true limitation would be wasted. From Lemma 11, the largest amount of resources that the new node could receive is r=Wc−∑j=1i−1tjmj/∑intj+tδ; therefore, at most r−mδ resources would be wasted.☐Lemma 17.
WhenR<tδmδ, there exists a real number r2 satisfying the following conditions:
(i)
Ifmδ≤r2, for any mnt∈0,mδ, xcvδ is a monotonically increasing function of mnt and no resource is wasted; for any mnt∈mδ,+∞, at most r2−mδ resources are wasted(ii)
Ifmδ>r2, for any mnt∈0,mδ, xcvδ=mnt; for any mnt∈r2,+∞,xcvδ=r2<mδ; therefore, no resources are wastedProof.
To begin with, we derive the value ofr2 by the following three cases:
(1)
IfR≥tδmn, r2=R/tδ(2)
Ifm1∑j=1ntj+tδ≥Wc, r2=Wc/∑j=1ntj+tδ(3)
IfR<tδmn and m1∑j=1ntj+tδ<Wc, from Lemma 11 to derive r2=Wc−∑j=1i−1tjmj/∑j=intj+tδ☐For simplicity, we only show the proof sketch of the third case. According to Lemma11, when mnt∈0,r2,xcvδ=mnt, thus xcvδ is a monotonically increasing function of mnt. Regardless of what value mnt the new node reports, the received resources cannot be larger than r2. Hence, if mδ≥r2 and mnt∈r2,+∞, xcvδ=r2<mδ, and no resource is wasted. However, when mδ≤r2 and mnt∈r2,+∞, the new node receives more resources than its true limitation, causing at most r2−mδ resources wasted. Thus, the lemma holds. The proof of the other two cases are similar, and we omit the details.According to Lemmas16 and 17, the new node misreport that its resource limitation cannot gain more resources, and some resources would be wasted under some circumstances.


## 7. Truthfulness against the Spitting Strategy

The previous section shows that a node cannot gain more resources by misreporting its resource limitation. In this section, we propose a novel method which may help the node receive more resources. Suppose a new node’s resource limitation ismδ; it reports to the central node that two nodes are inserted, and the sum of their resource limitations is mδ. This implies that the node is assumed to be split into two nodes with resource limitations mnp1,mnp2, and mnp1+mnp2=mδ; we call this splitting strategy. We analyze when the node could achieve more resources through this method.There are four cases according to the values ofmδ (the resource limitation of the new node), mn (the largest resource limitation of the original nodes), and R (the spare resources before the new node is inserted, Equation (3)):
(i)
Case 1:R≥tδmδ(ii)
Case 2:R<tδmδ and R≥2tδmn(iii)
Case 3:R<tδmδ and R<2tδmnIn this section, we show that the new node cannot gain more resources for the first two cases (Lemmas18 and 19), but it can gain more resources for cases 3 (Lemma 20). Denote the two virtual nodes of vδ as vnp1,vnp2 and the received resources as xcvnp1,xcvnp2, respectively. Denote the received resources of node vδ as xcvδ if it does not report two nodes. We show the following lemmas:Lemma 18.
IfR≥tδmδ, the splitting strategy has no effect to the new node, i.e., xcvnp1+xcvnp2=xcvδ.Proof.
Without loss of generality, supposemnp1≤mnp2 and m1≤m2≤⋯≤mk1≤mnp1≤⋯≤mnp2≤mk2≤⋯≤mn. When node vnp1 is inserted, we derive
(21)∑j=1k1tjmj+mnp1tδ+∑k1+1ntjmj<∑j=1ntjmj+mδtδ≤Wc,then xcvnp1=mnp1. When node vnp2 is inserted, we derive
(22)∑j=1k1tjmj+mnp1tδ+∑j=k1+1k2−1tjmj+mnp2tδ+∑j=k2ntjmj<∑j=1ntjmj+mnp1+mnp2tδ≤∑j=1ntjmj+mδtδ≤Wc,then xcvnp2=mnp2. Therefore, xcvnp1+xcvnp2=mnp1+mnp2=mδ=xcvδ, which implies that the new node cannot gain more resources through the splitting strategy.☐Lemma 19.
IfR<tδmδ and R≥2tδmn, the splitting strategy has no effect to the new node, i.e., xcvnp1+xcvnp2=xcvδ; thus, there is still no need to split the node.Proof.
SinceR<tδmδ and R≥2tδmn, we derive tδmδ>2tδmn, which implies mδ>2mn. Without loss of generality, suppose mnp1≤mnp2, there are two cases
(1)
mnp1≤mn<mnp2 and mnp1+mnp2=mδ>2mn(2)
mn<mnp1≤mnp2 and mnp1+mnp2=mδ>2mn
Ifmnp1≤mn<mnp2, suppose m1≤m2≤⋯≤mi−1≤mnp1≤mi≤⋯≤mn<mnp2; notice that
(23)Wc≥∑j=1ntjmj+2tδmn>∑j=1i−1tjmj+tδmnp1+mnp1∑j=i−1ntj.
When nodevnp1 is inserted, xcvnp1=mnp1. When node vnp2 is inserted, from tδmδ>Wc−∑j=1nmjtj, we have
(24)tδmnp2>Wc−tδmnp1−∑j=1ntjmj,thus the allocated resources are
(25)xcvnp2=Wc−tδmnp1−∑j=1ntjmjtδ.
Combining two nodes’ resources,xcvnp1+xcvnp2=mnp1+Wc−tδmnp1−∑j=1ntjmj/tδ=Wc−∑j=1ntjmj/tδ=xcvδ.
For the second case,mn<mnp1≤mnp2 and mnp1+mnp2>2mn; notice that after the two nodes are inserted, for any node vi,i∈1,n, xcvi=mi. If Wc−∑j=1ntjmj≥2tδmnp1, we derive
(26)xcvnp1=mnp1,xcvnp2=Wc−∑j=1ntjmj−tδmnp1tδ.
Therefore,xcvnp1+xcvnp2=Wc−∑j=1ntjmj/tδ=xcvδ. If Wc−∑j=1ntjmj≤2tδmnp1, we derive xcvnp1=xcvnp2=Wc−∑j=1ntjmj/2tδ, thus xcvnp1+xcvnp2=Wc−∑j=1ntjmj/tδ=xcvδ. Combining these cases, the lemma holds.☐Lemma 20.
IfR<tδmδ and R<2tδmn, the new node can increase the received resources through the splitting method. For some special situations, the received resources could be about two times, i.e., xcvnp1+xcvnp2≈2xcvδ.Proof.
IfR<tδmδ and R<2tδmn, there exists m∗ such that the largest amount of resources two nodes can receive is 2m∗. Suppose m1≤m2≤⋯≤mi−1≤m∗≤mi≤⋯≤mn; similar as Lemma 11, we derive
(27)∑j=1i−2tjmj+mi−1∑j=i−1ntj+2tδmi−1≤Wc.
Thus,mi−1≤Wc−∑j=1i−2tjmj/2tδ+∑j=i−1ntj, and we can find the largest value i−1 such that mi−1≤m∗ and mi≥m∗. Since ∑j=1i−1tjmj+m∗∑j=intj+2tδm∗=Wc, we derive
(28)m∗=Wc−∑j=1i−1tjmj2tδ+∑j=intj.
According to Algorithm1, if m∗≤mnp1≤mnp2, xcvnp1=xcvnp2=m∗. If mnp1≤m∗≤mnp2, we show that the sum of two nodes’ resources is no more than 2m∗.
Supposem1≤m2≤⋯≤mi1≤mnp1≤⋯≤m∗≤⋯≤mi2≤mnp2≤⋯≤mn, it is easy to get xcvnp1=mnp1 and xcvnp2≥m∗. We analyze the maximum value xcvnp2 can achieve. Combining the inequality ∑j=1i1tjmj+tδmnp1+∑j=i1+1i2tjmj+xcvnp2tδ+xcvnp2∑j=i2+1ntj≤Wc. and the equation ∑j=1i−1tjmj+m∗∑j=intj+2tδm∗=Wc, we derive
(29)mnp1+xcvnp2−2m∗tδ≤∑j=1i−1tjmj+m∗∑j=intj−∑j=1i2tjmj+xcvnp2∑j=i2+1ntj≤0.
Hence,xcvnp1+xcvnp2≤mnp1+xcvnp2≤2m∗. We then analyze when the xcvnp1+xcvnp2=2m∗.
Ifmnp2>m∗, i≤i2 and mnp1+xcvnp2−2m∗tδ<0 (Equation (29)), the sum of two nodes’ resources cannot be 2m∗. When xcvnp2=m∗, we can derive xcvnp1+xcvnp2=mnp1+xcvnp2=2m∗. If the node is not split, the received resources is xcvδ=Wc−∑j=1i1−1tj/tδ+∑j=i1ntj. Since m∗=Wc−∑j=1i−1tjmj/2tδ+∑j=intj (see Equation (28)), if tδ<<∑j=1ntj, we derive i1=i, and the received resources of two split nodes are 2m∗≈2xcvδ, which implies that the node can receive about 2 times resources compared to the original allocation. Therefore, the lemma holds.☐From the lemma, we know that the new node can achieve more resources by the splitting strategy. For some special situations, the node can gain appropriate two times resources compared to a honest node. Combining Lemmas18, 19, and 20, we conclude the theorem as follows:If the spare resources are adequate (R≥tδmδ) or inadequate (R<tδmδ) but suits R≥2tδmn, the splitting strategy has no effect on the new node. If the spare resources suit R<tδmδ and R<2tδmn, the node can gain more resources (xcvnp1+xcvnp2>xcvδ), and in some special situations, the resources can be about two times (xcvnp1+xcvnp2≈2xcvδ).


## 8. Truthfulness against Splitting Strategy in Tree Graph

In the previous section, we show that a node can gain more resources by the splitting strategy in the centralized resource system. However, in the hierarchy, resources are passed down layer by layer. The node cannot obtain resources from the original node that owns the resources but receives resources from other adjacent nodes. In this section, we will study how the splitting behavior of the parent node affects the child nodes. Suppose a nodevr has several child nodes vpi,i∈1,k1, the limitation of which is mpi. Node vpt has several child node vcj,j∈1,k2. Node vpθ reports to its parent node vr that two nodes vpθ1 and vpθ2 are inserted and the sum of their resource limitation is mpt. We analyze the influence of node vpi’s splitting strategy on its child node vcj’s received resources. xij is the resources node vi allocates to node vj. Wr is the resources of node vr. Let Rr be the spare resources after node vr allocates its resources to its child node vci except node vct. We formulate it as Rr=Wr−∑i∈1,pθ−1⋃pθ+1,k1xpitpi.Lemma 21.
If the spare resourcesRr are adequate(Rr≥tpθmpθ) or inadequate(Rr<tpθmpθ) but suits R≥2tpθmk1, there are three cases:
(i)
Case 1. Wpθ>∑i=1k2mcitci; there exists a splitting strategy for node vpθ to increase node vci’s received resources(ii)
Case 2. Wpθ≤mc1∑i=1k2tci; no matter how node vpθ splits, node vci’s received resources do not change(iii)
Case 3. mc1∑i=1k2tci<Wpθ≤∑i=1k2mcitci; there exists two real number r and r1 satisfying the following: (a) there exists a real number r1=Wpθ/2∑i=1i1−1tcimci+mci1∑i=i1k2tci satisfying if mci≤r1, vci’s received resources increase and (b) there exists a real number r such that if mci≥r, vci’s received resources decreaseProof.
Suppose nodevpθ reports two false node vpθ1 and vpθ2 to node vr. Consider case 1 if Wpθ≥∑i=1k2mcitci. Let Wpθ1 and Wpθ2 be the amount of resources two false nodes vpθ1 and vpθ2 receive from node vr. If Wpθ1=∑i=1k2mtcitci and Wpθ2=Wpθ−∑i=1k2mtcitci. Therefore, xpθ1=mci,xpθ2≥0. xpθ1+xpθ2≥mci=xpθ. vci’s received resources increase. Consider case 2 if Wpθ≤mc1∑i=1k2tci, xpθ1ci=Wpθ1/∑i=1k2tci, xpθ2ci=Wpθ2/∑i=1k2tci, xpθci=xpθ1ci+xpθ2ci. Node vci’s received resource does not change. Consider case 3 (a): suppose Wpθ1>Wpθ2, then Wpθ1>Wpθ/2 and Wpθ2<Wpθ/2. There must exists a real number r2≥r1 such that any node vci,i∈1,k2 satisfying mci≤r2, xpθ1=mci=xpθ, and xpθ2>0 under the new max-min fair allocation vector. xpθ1+xpθ2>xpθ. vci’s received resources increase. Consider case 3 (b): for node vpθ1’s allocation, there exists an integer i1∗∈0,k2 such that xpθ1ci=mci,i∈1,i1∗−1 and xpθ1ci<mci,i∈i1∗,k2. Similarly, for node vpθ2’s allocation, there exists an integer i2∗∈0,k2 such that xpθ1ci=mci,i∈1,i2∗−1 and xpθ1ci<mci,i∈i2∗,k2. If Wpθ1>Wpθ2, then i1∗>i2∗. For node vpθ’s allocation, we derive
(30)Wpθ−∑j=1i1∗−1tjmj=∑j=i1∗i∗−1tjmj+xpθcj∑j=i∗k2tj.
For false nodesvpθ1’s and vpθ2’s allocation, we derive
(31)Wpθ1−∑j=1i1∗−1tjmj=xpθ1cj∑j=i1∗k2tj,(32)Wpθ2−∑j=1i2∗−1tjmj−xpθ2cj∑j=i2∗i1∗−1tj=xpθ2cj∑j=i1∗k2tj.
Combining Equation (30), Equation (31), and Equation (32), we derive
(33)xpθ1cj+xpθ2cj∑j=i1∗k2tj<∑j=i1∗i∗−1tjmj+xpθcj∑j=i∗k2tj.
Therefore,xpθ1cj+xpθ2cj<xpθcj; otherwise, we derive ∑j=i1∗i∗−1tjmj+xpθcj∑j=i∗k2tj≤xpθcj∑j=i1∗k2tj≤xpθ1cj+xpθ2cj∑j=i1∗k2tj, which makes a contradiction. Thus, the lemma holds.☐By a similar method, the following lemma can be derived.Lemma 22.
If the spare resources suitRr<tpθmpθ and Rr<2tpθmk1, there are three cases:
(i)
Case 1. Wpθ>∑i=1k2mcitci or Wpθ≤mc1∑i=1k2tci; node vci can gain more resources by vpθ’s splitting strategy(ii)
Case 2. mc1∑i=1k2tci<Wpθ≤∑i=1k2mcitci; there exists two real number r and r1 satisfying (a) if mci≥r, vci’s received resources decrease (tpθ>>∑j∈1,pθ−1⋃pθ+1,k1tj) or increase (tpθ<<∑j∈1,pθ−1⋃pθ+1,k1tj), and (b) there exists a real number r1=Wpθ/2∑i=1i1−1tcimci+mci1∑i=i1k2tci satisfying: if mci≤r1, vci’s received resources increaseFrom Lemmas21 and 22, we know that if grandparent node’s resources are adequate, node’s resources can not increase by parent’s splitting strategy in most scenarios. However, if grandparent node’s resources are inadequate, in most cases, node’s resources can increase by parent’s splitting strategy.


## 9. Numerical Examples

In this section, we present some numerical examples to illustrate these results. As shown in Figure1(a), six nodes are connected to the central node in the system, and m,t (resource limitation, transfer rate) is depicted on each edge. For example, node v1 has m1=3,t1=5. Assume the amount of all resources the central node holds is Wc=205.Figure 1
A centralized resource system: six nodes are connected to the central node; a new nodevδ is inserted with mδ=17,tδ=1; the node is split into two nodes vp1,vp2 with mp1=8,mp2=9.
(a)
Six nodes in the system(b)
Nodevδ is inserted(c)
vδ splits into two nodes vp1,vp2By Algorithm1, the max-min allocation is listed in Table 2 where ui is the utility of the node which is equal to the received resources xcvi; xcvi·ti is the resources the central node allocates. There is no spare resource since R=Wc−∑i=16xcviti=0. As shown in Figure 1(b), if a new node vδ is inserted with mδ=17,tδ=1, the max-min allocation is presented as Table 3. Nodes v5,v6 receive fewer resources since their resources are allocated to the new node. If the node misreports its limitation mδ, it cannot gain more resources, and some resources would be wasted.Table 2
The max-min fair allocation of six nodes.
Nodeimitixcvixcvi·tiuiv1353153v2454204v35105505v4757357v5858408v6959459Table 3
The max-min allocation aftervδ is inserted.
Nodeimitixcvixcvi·tiuiv1353153v2454204v35105505v4757357v58585/11≈7.727425/1185/11v69585/11≈7.727425/1185/11vδ17185/11≈7.72785/1185/11In order to gain more resources, the new node splits itself into two nodesvp1,vp2 such that mp1=8,mp2=9 (mp1+mp2=mδ=17) (as shown in Figure 1(c)). The max-min allocation is presented in Table 1; nodes v5,v6 receive fewer resources, and nodes vp1,vp2 both receive 85/12 resources. Therefore, with the splitting strategy, the new node receives resources xcvp1+xcvp2=85/6≈14.166. Compared to the received resources in Table 3, the splitting strategy achieves 14.166/7.727≈1.83 times that of the original allocation.Next, we present an example to illustrate splitting strategy in tree graph.The overall amount of nodevr is Wr=100. As shown in Figure 2, node vr allocates its resources to its child vpi,i∈1,4. The resource demand m and resource transfer rate t are shown in Table 4. The amount of resource node vp2’s receives is 24. Once receiving the resources from node vr, node vp2 will allocate its resources to its child vci,i∈1,6. The max-min allocation is presented as Table 5. The amount of resource node vci,i∈3,6 receives is fewer than their resource demand. When node vp2 splits itself into two false node vfp1 and vfp2 (as shown in Figure 3), the overall amount of resources node vci,i∈3,6 receives decreases. For instance, the amount of resource node vp2 allocates to node vc3 is xp2c3=17/5≈3.4. However, the overall resource node vc3 receives from two false nodes vfp1 and vfp2 equals xfp1c3+xfp2c3=22/8≈2.75<3.4 (as presented in Table 6).Figure 2
A tree with rootvr whose resources are passed down to descedant nodes.Table 4
The max-min allocation of nodevr’s resources.
Nodeimpitpixrpivp112212vp2828vp320120vp424124Table 5
The max-min allocation of nodevp2’s resources.
Nodeimcitcixp2civc1111vc2232vc34217/5≈3.4vc45117/5≈3.4vc56117/5≈3.4vc68117/5≈3.4Figure 3
A tree with two false nodesvfp1 and vfp2 whose resources are passed down to descedant nodes.Table 6
The max-min allocation of two false nodesvfp1 and vfp2’s resources.
Nodeimcitcixfp1cixfp2civc11111vc22311/8≈1.37311/8≈1.373vc34211/8≈1.37311/8≈1.373vc45111/8≈1.37311/8≈1.373vc56111/8≈1.37311/8≈1.373vc68111/8≈1.37311/8≈1.373


## 10. Conclusion

In this paper, we study the truthfulness of the max-min fair allocation in a centralized resource system. Max-min fairness is a common adopted concept in evaluating an allocation mechanism. We propose a simple but efficient algorithm to find out the allocation. On the foundation of the algorithm, we analyze how the allocation varies when a new node is added to the system. Furthermore, we explore whether the allocation is truthful against two strategic behaviors. The misreporting strategy cannot affect the allocation while the new node can gain more resources by the splitting strategy. Hence, the max-min allocation mechanism is not truthful especially against the splitting strategy. Finally, we analyze the effect of node’s splitting strategy on its child nodes on tree graph. In some situations, nodes can gain more resources despite the splitting strategy of its parents. It is still an open problem to design a fair and truthful allocation mechanism in a centralized resource system.



---

*Source: 5570104-2021-10-18.xml*