Truthfulness of a Proportional Sharing Mechanism in Resource Exchange

1 Introduction

The rapid growth of the wireless and mobile Internet has provided an opportunity for wide applications of exchanging resources or services over networks, which go beyond the peerto-peer (P2P) bandwidth sharing idea. In a traditional P2P network, each peer is both a supplier and a consumer of resources. Resources (such as processing power, disk storage or network bandwidth) are shared among multiple interconnected peers who use a mechanism to make a portion of their resources directly available to other network participants in a distributed management system [Schollmeier, 2001].

The successes of the resource exchange networks highly depend on the efficient resource utilization. A P2P system can be modeled as a pure exchange economy in which each user brings its own divisible resources to the market and exchanges its resources with its neighbors to derive utility. Formally, the system is modeled as an undirected graph G, where each node i represents a peer with wi units of divisible resources (or weight) to be distributed among its neighbors. The utility ui is determined by the total amount of resources obtained from its neighbors. An efficient allocation in such an exchange economy can be characterized by the market equilibrium. On the other hand, to encourage users to contribute more, a fair allocation rule is essential. Ideally a user should receive as much as it gives. However, such perfect reciprocation may not be feasible due to the network structure. Then a proportional fairness mechanism is a natural approximation. Under this mechanism, each peer provides each neighbor a portion of its contribution in proportion to what it receives from its neighbors. Recently, Wu and Zhang [Wu and Zhang, 2007] showed that the market equilibrium obtained by a combinatorial method, called bottleneck decomposition is a proportional fair solution. They also showed the proportional dynamics converged to this equilibrium for linear utility functions under mild conditions.

However, agents are strategic. The market equilibrium is determined by agents' reported information rather than their true information. An agent may have the incentive to misreport its information if it is profitable. Hurwicz [Hurwicz, 1972] showed that it is impossible to design a truthful mechanism that guarantees a market equilibrium outcome in general. Even in a Fisher market game with linear utility, it was shown that an agent may derive a better payoff [Adsul et al., 2010], more specifically, may double its benefit by strategic behaviors [Chen et al., 2014]. The resource exchange game studied in a P2P setting is a special case of Arrow-Debreu market where agents are only interested in their neighbors' resources and only care about the total amount of resources received. Hurwicz's impossibility theorem may not hold for restricted settings. A recent work [Cheng et al., 2015] discussed the issue of agents' manipulations by cheating on their connectivity information. The authors proved that the proportional sharing mechanism is robust to such manipulations. As utlilities are determined by allocation that depends on agents' weights and the network structure, the strategic manipulations of an agent can only be misreporting its weight or/and misreporting its connection edges in the network. This work leaves a clear open question whether an agent could lie on the amount of resources it can offer. In this paper, we solve this open problem and prove the truthfulness of the proportional sharing mechanism. It shows that the proportional sharing mechanism is truthful, fair and Pareto efficient.

Technical Contributions

Our approach builds on a network bottleneck decomposition structure initially designed for the analysis of the connection of fairness (proportional sharing) and competitiveness (market equilibrium) [Wu and Zhang, 2007] and then the nonmanipulability [Cheng et al., 2015]. For a given subset of agents, the total resources of their neighbors has a key importance on their eventual gains with respect to their own total resources. The concept of bottleneck captures the ratio of those two by finding a subset with this ratio at the minimum value. Recursively applying this operation, the bottleneck decomposition of G is obtained.

The bottleneck decomposition of G and the utility of agent u depends on the reported weight xu by u, given the other agents' weights. With the increasing of xu, we characterize the change process of bottleneck decomposition and prove the monotonically nondecreasing property of the utility function of u. Therefore, the desirable truthfulness of the proportional sharing mechanism follows.

Related Works

The classical economists and algorithmic game theorists have made an extensive study of competitive equilibrium [Arrow and Debreu, 1954], in terms of computation for prices and allocation [Lange, 1967], complexity and approximation [Papadimitriou, 2001; Deng et al., 2002; Devanur et al., 2002; Jain, 2007; Ye, 2008; Duan et al., 2016]. Those works have started to have an influence in resource allocation among multiple agents, especially in the important implementations for the Internet enabled economic, management and social activities. How to fairly redistribute and share those resources have become an important issue with more and more online platforms which facilitate the exchange of commodities and services [GetRidApp, ; Homeexchang, ; Nestia, ; Swap, ]

The automated process through information and communication technology for Internet applications in such problems has made it possible for the agents to make their best moves. Hence manipulating one's own private information becomes a possibility. Some of the recent theoretical studies have been in this direction such as recent studies on agent incentives in the Fisher market equilibrium for linear market [Adsul et al., 2010; Chen et al., 2014] and for constant elasticity of substitution market [Branzei, 2014].

The proportional sharing mechanism has been extensively studied in the exchange economy model. Compared to other allocation mechanism, the proportional sharing mechanism is simple, computational efficient and fair. Some of previous work [Feldman et al., 2009; Zhang, 2005] focus on the pricetaking scheme. But in the resource exchange/sharing model, money is no longer needed as a medium and the non-pricetaking scheme is considered in our paper and [Wu and Zhang, 2007; Cheng et al., 2015].

2 Preliminaries

In this section, we model the resource exchange setting by an undirected graph G = (V↪E;w). Each vertex u 2 V represents an agent with an upload resource amount (weight) wu > 0 to be exchanged with its neighbors. Let Γ(u) be the neighborhood of u, i.e. the set of vertices adjacent to u in G. And fuv is denoted as the fraction of resource u allocated to its neighbor v. Obviously, 0  fuv  1 and the resource vertex u provides to v is wufuv. F = (fuv)u↪v2E is called a feasible allocation if Pv2Γ(u) fuv = 1, that means u allocates all its resource out. The utility of agent u is defined as Uu(F) = Pv2Γ(u) fvuwv, i.e. all received resource from its neighborhood Γ(u).

2.1 Bottleneck Decomposition

Consider an undirected connected graph G = (V↪ E; w) with weight w : V ! R+. For any set S ✓ V , we define w(S) = Pu2S w(u) and Γ(S) = [u2SΓ(u). It is possible that S \ Γ(S) 6= ;. Define ↵(S) = w(Γ(S))◁w(S), referred to as the inclusive expansion ratio of S, or the ↵-ratio of S for short.

Definition 1 (Maximal Bottleneck) A vertex subset B ✓ V is called a bottleneck of G if ↵(B) = minS✓V ↵(S). B is a maximal bottleneck if for any subset e B, B ⇢ e B ✓ V implies ↵( e B) ≥ ↵(B). (B↪ Γ(B)) is called the maximal bottleneck pair in V .

Definition 2 (Bottleneck Decomposition) Given

G = (V↪E;w). Start with V1 = V , G1 = G and i = 1. Find the maximal bottleneck Bi of Gi and let Gi+1 be the induced subgraph on the vertex set Vi+1 = Vi - (Bi [ Ci), where Ci = Γ(Bi) \ Vi, the neighbor set of Bi in the subgraph Gi. Repeat if Gi+1 6= ; and set k = i if Gi+1 = ;. Then we call B = ¶(B1↪C1)↪ · · · ↪ (Bk↪Ck)♦ the bottleneck decomposition of G, ↵i the i-th ↵-ratio and < ↵i = w(Ci) w(Bi) : i = 1↪ 2↪ · · · ↪ k > the ↵-ratio vector.

As stated in [Wu and Zhang, 2007], the problem of computing the bottleneck decomposition can be solved by the parametric maximum flow algorithm in a polynomial time. Further, they also derived some properties of the bottleneck decomposition as follows.

Proposition 3 ([Wu and Zhang, 2007]) Given graph G, the bottleneck decomposition of G is unique and

1. 0 < ↵1 < ↵2 < · · · < ↵k  1;

(3) if B ✓ Vi and C = Γ(B) \ Vi, then w(C) ∩ w(B) ≥ ↵i, where if the equality holds, then B ✓ Bi and C ✓ Ci.

(2) if ↵i = 1, then i = k and Bi = Ci; otherwise Bi is an independent set and Bi \ Ci = ;;

For the third claim in Proposition 3, we name such a pair of (B↪ C) with B ✓ Vi and C = Γ(B) \ Vi as a candidate pair in Vi for convenience.

2.2 BDMechanism

Given bottleneck decomposition, an allocation mechanism [Wu and Zhang, 2007] can be determined by distinguishing three cases. For convenience, we call such an allocation mechanism BD Mechanism.

BD Mechanism:

• ÷ For ↵i < 1, consider the bipartite graph bGi = (Bi↪Ci;Ei) where Ei = (Bi ⇥ Ci) \ E. By Proposition 3-(2), Bi is an independent set in G. Let b fuv be the amount of bandwidth that vertex u 2 Bi upload to v 2 Ci along edge (u↪ v) 2 Ei. By the maxflow min-cut theorem, there exists flow b fuv ≥ 0 for u 2 Bi and v 2 Ci such that Pv2Γ(u)\Ci b fuv = wu and Pu2Γ(v)\Bi b fuv = wv◁↵i. Let b fvu = ↵i b fuv which means that Pu2Γ(v)\Bi b fvu = wv.
• ÷ When Bk = Ck with ↵k = 1, similarly we construct a bipartite graph bG = (Bk↪B0k ;E0k ) such that

B0k is a copy of Bk. There is an edge (u↪ v0 ) 2 E0k if and only if (u↪ v) 2 E[Bk]. By Hall's theorem, for any edge (u↪ v) 2 E[Bk], there exists flow b fuv0 such that Pv02Γ(u)\B0k b fuv0 = wu and b fuv0 = b fvu0 . Let fuv0 .

define b It is clear that BD Mechanism assigns all resource of each agent to its neighbors from the same pair, that is all available resources exchanged along edges in Bi ⇥ Ci, i = 1↪ · · · ↪ k. In terms of "fairness" and "efficiency", BD Mechanism is exactly a proportional sharing mechanism.

• b fuv = b ÷ For any other edge, (u↪ v) 62 Bi ⇥ Ci, i = 1↪ 2↪ · · · ↪ k, fuv = 0

Definition 4 (Proportional SharingMechanism) For each vertex u, the allocation (fuv : v 2 Γ(u)) of its resource wu is proportional to what it receives from its neighbors (wv · fvu : Γ(u)). That is fuv = fvuwv Pk2Γ(u) fkuwk ▷

Proposition 5 ([Wu and Zhang, 2007]) BDMechanism is a proportional sharing mechanism.

As stated before, the P2P system can be modeled an exchange economy where each agent u sells its own divisible resource and use the money earned through trading to buy its neighbors' resource. An efficient allocation in such an exchange economy can be characterized by the market equilibrium. Given a bottleneck decomposition, if a price vector P is well defined as: pu = ↵iwu, if u 2 Bi; and pu = wu otherwise, then such a price vector combining the allocation F obtained from BD Mechanism satisfying

Proposition 6 ([Wu and Zhang, 2007]) (P,F) is a market equilibrium, where F = (fuv) is obtained from BD Mechanism.

2.3 Resource Exchange Game

From a system design point of view, though BD Mechanism shall allocate resources among interconnected participants fairly and efficiently it is unknown whether an agent is willing to follow such a distributed network mechanism at the execution level. Can agents make strategic moves for gains in their utilities? Specific to the resource exchange model, the resources all agents have are their private information. They may manipulate BD Mechanism by misreporting the resource they own. We call such a problem with incentive factors the resource exchange game.

In the resource exchange game, let the resource amount reported by agent u be xu 2 (0↪wu]. The reason why xu cannot exceed the true bandwidth wu is that each agent must upload all its reported resource to its neighbors. The collection x = (x1↪ x2↪ · · · ↪ xn) is referred to as the weight profile and x-u = (x1↪ · · · ↪ xu-1↪ xu+1↪ · · · ↪ xn) is the weight profile without agent u. Thus x = (xu↪ x-u). Let the bottleneck decomposition be B(x) = ¶(B1(x)↪ C1(x))↪ · · · ↪ (Bk(x)↪ Ck(x))♦ and BD Mechanism outputs an allocation F(x) based on the given weight profile x. The utility of agent u written as Uu(x) is [Wu and Zhang,

where ↵i(x) is the i-th ↵ ratio according to weight profile x. For mechanism design, the notion of truthfulness is perhaps the most important concept.

Definition 7 A mechanism is truthful if no agent can benefit strictly from misreporting its resource amount irrespective of what is reported by other agents. Formally, given agent u and profile x = (xu↪ x-u), it holds that for any x-u

It is obvious that truthfully reporting resource amount wu is the dominant strategy for each agent u in the resource exchange game, if a mechanism is truthful.

3 Truthfulness of BDMechanism

As we know, the bottleneck decomposition of G depends on the structure of network and the resource all agents have. So for any agent u and any weight profile x-u, the bottleneck decomposition B of G shall change with the reported resource xu. Thus B can be viewed as a function of xu if x-u is fixed. On the other hand, we observe that bottleneck decomposition of G could be the same when xu falls in an interval. Based on such an observation, we partition interval (0↪ wu] into several disjoint subintervals ¶hai↪ bii♦i and construct a series of bottleneck decompositions ¶Bi ♦i such that when xu 2 hai↪ bii, B(xu↪ x-u) = Bi = ¶(Bi1 ↪C i1 )↪ · · · ↪ (Biki ↪C iki)♦. W.l.o.g., assume that 0 < ai  bi = ai+1  bi+1. We use symbol "hi" to denote the subinterval, because hai↪ bii could be one of five forms [ai↪ bi], [ai↪ bi), (ai↪ bi], (ai↪ bi) and ai = bi. If ai = bi, then hai↪ bii contains exactly one point which can be viewed as a special closed interval. Further, in order to keep the oneto-one correspondence between the subintervals and the bottleneck decompositions, we use ai and bi to denote the left and right endpoints of the i-th subinterval, respectively. Thus for any two adjacent interval hai↪ bii and hai+1↪ bi+1i, there are only two cases: 1. hai↪ bi] and (ai+1↪ bi+1i; 2. hai↪ bi) and [ai+1↪ bi+1i; depending on which interval contains the break point ai+1 = bi.

In the sequel, we first characterize the pairs agent u belongs to in adjacent Bi and Bi+1 in Subsection 3.1. Then the monotonicity of utility functions is derived by such useful characterizations in Subsection 3.2.

3.1 Characterization of ¶Bi♦

In order to show the structure properties of bottleneck decomposition B in-depth, we redefine the bottleneck decomposition in more detail below.

Definition 8 (Bottleneck Decomposition) Let Bi = ¶(Bi1 ↪ C i1 )↪ · · · ↪ (Biki ↪ C iki )♦ be the bottleneck decomposition of graph G when xu 2 hai↪ bii and let the ↵-ratio of (Bi j ↪ C i j ) be ↵ij = w(C i j )◁w(Bi j ), j = 1↪ · · · ↪ ki . For pair (Bi j ↪ C i j ) with ↵ij < 1, each vertex in Bi j (or C i j ) is called a B-class (or C-class) vertex. For the special case Biki = C iki , i.e., ↵iki = 1, all vertices in Biki are categorized as both B-class and C-class. Define V i 1 = V , V i j+1 = V i j - (Bi j [ C i j ) for j = 1↪ · · · ↪ ki - 1 and Gij for the induced subgraph on V i j .

Note that a vertex in V i ki with ↵iki = 1 could simultaneously be B-class and C-class, in the case Biki = C iki . Moreover to highlight the ↵-ratio of pairs (Bi j ↪ C i j ) containing agent u, we denote it ↵ij (xu). Further, if V i h = V i+1 h for some index h, then the maximal bottleneck pair in V i h or V i+1 h just is a candidate pair in the other. So Proposition 3-(3) can be applied on those candidate pairs. In the subsequent discussions, such a technique will be used repeatedly.

In the following, we assume that u 2 Bi j [ C i j and u 2 Bi+1 ` [ C i+1 ` in Bi and Bi+1 respectively. As we know, the bottleneck decomposition of G changes because of the reported resource of agent u. Agent u's strategic move is only able to influence such pairs which are decomposed after pairs that u is in. But those with index less than j and ` still keep the same. So

Lemma 9 For any agent u, if u 2 Bi j [C i j and u 2 Bi+1 ` [ C i+1 ` in Bi and Bi+1 respectively, then V i h = V i+1 h for each h = 1↪ 2↪ · · · ↪ min¶j↪ `♦.

Since agent u may be a B-class vertex or C-class vertex in Bi and Bi+1 respectively, there are totally 4 cases: u 2 Bi j \C i+1 ` , u 2 C i j \Bi+1 ` , u 2 Bi j \Bi+1 ` and u 2 C i j \C i+1 ` . Specially for the first two cases, we assume that ↵ij (xu) < 1 if xu 2 hai↪ bii and ↵i+1 ` (xu) < 1 if xu 2 hai+1↪ bi+1i. This assumption is reasonable. For example, if u 2 Bi j \C i+1 ` and ↵ij (xu) = 1 when xu 2 hai↪ bii, then u can be viewed as a C-class vertex and Bi j can be rewritten as C i j , which makes such a case be that of u 2 C i j \ C i+1 ` .

Lemma 10 For bottleneck decomposition Bi and Bi+1 , it is impossible that u 2 Bi j \ C i+1 ` and u 2 C i j \Bi+1 ` .

Proof: (sketch) For simplicity, we only show the impossibility of u 2 Bi j \ C i+1 ` and discuss the case that the corresponding intervals of Bi and Bi+1 have the forms of hai↪ bi] and (ai+1↪ bi+1i. There are two cases that j < ` and j ≥ `. If j < `, then V i j = V i+1 j by Lemma 9. If xu = bi, then the bottleneck decomposition is Bi and (Bi+1 j ↪C i+1 j ) is a candidate pair of V i j , which induces w(C i+1 j )◁w(Bi+1 j ) ≥ w(C i j )◁(w(Bi j ∩¶u♦)+bi) by Proposition 3-(3). But if xu increases to bi +✏ 2 (ai+1↪ bi+1i for any small ✏ > 0, then the bottleneck decomposition changes to be Bi+1 and (Bi j ↪ C i j ) is a candidate pair of V i+1 j . So we have w(C i j )◁(w(Bi j ∩ ¶u♦) + bi + ✏) ≥ w(C i+1 j )◁w(Bi+1 j ). Combining such two inequalities, w(C i j )◁(w(Bi j ∩¶u♦)+bi+✏) ≥ w(C i j )◁(w(Bi j ∩ ¶u♦) + bi). It's a contradiction. The proof for case j ≥ ` is similar. ⇤

Lemma 10 demonstrates the impossibility of cases u 2 Bi j \ C i+1 ` and u 2 C i j \ Bi+1 ` . So our focus turns to those that u is in the same classes in adjacent Bi and Bi+1 .

Lemma 11 For bottleneck decomposition Bi and Bi+1 cor-

responding to intervals hai↪ bii and hai+1↪ bi+1i, 1. if u 2 Bi j and u 2 Bi+1 ` , then `  j; 2. if u 2 C i j and u 2 C i+1 ` , then ` ≥ j.

Proof:(sketch) For the first claim, we suppose to the contrary that ` > j which guarantees V i j = V i+1 j by Lemma 9. So (Bi j ↪ C i j ) is a candidate pair in V i+1 j if b xu 2 hai+1↪ bi+1i and we can get the first inequality of (3). Similarly, the role of candidate of (Bi+1 j ↪C i+1 j ) in V i j if xu 2 hai↪ bii promises the second inequality of (3)

w(C i j ) b xu + w(Bi j ∩ ¶u♦) ≥ w(C i+1 j ) w(Bi+1 j ) ≥ w(C i j ) xu + w(Bi j ∩ ¶u♦) (3) It's a contradiction since b xu > xu. ⇤ Lemma 11 shows that the relationship between the indexes of pairs which contain u, if u is in the same classes in adjacent Bi and Bi+1 . Furthermore, the following claims will concretely describe the relation between Bi j and Bi+1 ` , C i j and C i+1 ` . The key of proofs is how to analyze the transient changes of bottleneck decompositions at the break point xu = bi = ai+1.

Lemma 12 For bottleneck decomposition Bi and Bi+1 and u 2 Bi j \Bi+1 ` ,

2. if corresponding adjacent intervals have the forms as hai↪ bi) and [ai+1↪ bi+1i, then u 2 Bi`+1 , Bi+1 ` = Bi` [Bi`+1 and C i+1 ` = C i ` [C i `+1 .

1. if corresponding adjacent intervals have the forms as hai↪ bi] and (ai+1↪ bi+1i, then u 2 Bi` , Bi` = Bi+1 ` [ Bi+1 `+1 and C i ` = C i+1 ` [C i+1 `+1 .

Proof: Here we prove the first claim in two steps: 1. u 2 Bi` ; and 2. Bi` = Bi+1 ` [ Bi+1 `+1 . The proof for the second one is similar. Lemma 11 guarantees that index `  j which implies V i ` = V i+1 ` by Lemma 9. Now Suppose to the contrary that u 62 Bi` . Let us focus on the break point that xu = bi. At this point, the bottleneck decomposition of G is Bi and the candidate role of (Bi+1 ` ↪C i+1 ` ) in V i ` keeps that

If the strict inequality in (4) holds, then there must exist a positive number ✏ > 0 such that bi + ✏ = ai+1 + ✏ 2 (ai+1↪ bi+1i and

As we know, once weight xu increases up to bi +✏ = ai+1 + ✏ 2 (ai+1↪ bi+1i, the bottleneck decomposition shall change to be Bi+1 . As a candidate pair in V i+1 ` , the ratio of (Bi` ↪C i ` ) can not be strictly less than ↵i+1 ` (bi + ✏) which induces the impossibility of (5) and the strict inequality of (4). So

Then Bi+1 ` ✓ Bi` by Proposition 3-(3) and u 2 Bi` , because u 2 Bi+1 ` . Furthermore, we confirm that Bi+1 ` ⇢ Bi` . Otherwise the pairs containing u are the same in Bi and Bi+1 which leads to Bi = Bi+1 . It's contradicts the partition of (0↪ wu].

Next, we shall show that Bi` = Bi+1 ` [ Bi+1 `+1 . For this purpose, let us define Bc = Bi` - Bi+1 ` 6= ; and C c = C i ` - C i+1 ` 6= ;. We can see that (Bc ↪C c ) is a candidate pair in V i+1 `+1 . Moreover, we have

where the first equality comes from (6), the second one is from a simple arithmetic calculation and Proposition 3-(3) promises the last inequality. Now let us discuss the inequality

If the strict inequality of (8) is right, then we can also find a positive number ✏ > 0 such that bi + ✏ = ai+1 + ✏ 2 (ai+1↪ bi+1i and

It is easy to see that the bottleneck decomposition of G is Bi+1 when xu = bi + ✏ = ai+1 + ✏ 2 (ai+1↪ bi+1i. So by the increasing monotonicity property of ↵-ratios with indexes, we have ↵i+1 ` (bi + ✏) < ↵i+1 `+1 which illustrates the incorrectness of (9). So the equality of (8) holds and

Therefore Bc ✓ Bi+1 `+1 by Proposition 3-(3). On the other hand, in order to keep the maximality of Bi` 's size, there is only unique possibility that Bc = Bi+1 `+1 and Bi` = Bi+1 ` [ Bi+1 `+1 . ⇤

Note that, with the increasing of xu from hai↪ bii to hai+1↪ bi+1i, we can visualize the operations as split and combine to describe the changes of pairs containing u. Naturally, we can imagine that there are similar results for the case that u 2 C i j \ C i+1 ` .

Lemma 13 For bottleneck decomposition Bi and Bi+1 and u 2 C i j \ C i+1 ` ,

2. if corresponding adjacent intervals have the forms as hai↪ bi) and [ai+1↪ bi+1i, then u 2 C i+1 j , Bi+1 j = Bi j [Bi j+1 and C i+1 j = C i j [C i j+1 .

1. if corresponding adjacent intervals have the forms as hai↪ bi] and (ai+1↪ bi+1i, then u 2 C i+1 j+1 , Bi j = Bi+1 j [Bi+1 j+1 and C i j = C i+1 j [C i+1 j+1 .

3.2 Monotonicity of utility function on (0↪wu]

For the sake of convenience, we use Uu(xu) and ↵u(xu) to denote the utility function and the ↵-ratio function of agent u for any given x-u respectively, where xu 2 (0↪wu]. As before shown in (1), Uu(xu) = xu ·↵u(xu) if u is in B-class; otherwise Uu(xu) = xu◁↵u(xu).

First, we discuss the monotone property of Uu(xu) in any single subinterval hai↪ bii. Then the bottleneck decomposition of G is Bi = ¶(Bi1 ↪C i1 )↪ · · · ↪ (Biki ↪C iki)♦ when xu 2

hai↪ bii. So agent u may be in Bi j or C i j , j = 1↪ 2↪ · · · ↪ ki . To be specific, its ↵-ratio is

It is easy to observe that the ↵-ratio of u is monotonically increasing if it is a C-class vertex; and monotonically decreasing, otherwise. The utility function of agent u is

Lemma 14 For any agent u, any weight profile x-u, and any single interval hai↪ bii ⇢ (0↪wv], utility function Uu(xu) is monotonically nondecreasing on xu 2 hai↪ bii.

which is continuous on hai↪ bii and derivable on (ai↪ bi). Furthermore, the derivative function of Uu(xu) can be computed easily, which is nonnegative on hai↪ bii. Combining the continuity of Uu(xu) on hai↪ bii, we have

Next we shall challenge the monotonicity of Uu(xu) on the whole interval (0↪wu]. One of the biggest difficulties we are facing is that the ↵-ratio function and the utility function of agent u may vary with the bottleneck decompositions. If we can investigate the continuity of ↵-ratio and utility function of agent u at each break point, the monotone property of Uu(xu) can be achieved by Lemma 14.

Lemma 15 For bottleneck decomposition Bi and Bi+1 and u 2 Bi j \Bi+1 ` or u 2 C i j \C i+1 ` , the utility function Uu(xu) is continuous at break point.

Proof: Here we only show the continuity of Uu(xu) at break point xu = bi for the case that u 2 Bi j \Bi+1 ` and the adjacent intervals have the forms as hai↪ bi] and (ai+1↪ bi+1i. Under this case, Lemma 12 promises u 2 Bi` . So ↵u(xu) = ↵i` (xu) if xu 2 hai↪ bi] and ↵u(xu) = ↵i+1 ` (xu) if xu 2 (ai+1↪ bi+1i. Furthermore, equation (6) in the proof of Lemma 12 tells us that if xu = bi

Therefore, the continuity of ↵-ratio function at break point xu = bi holds as

And the utility function is also continuous at xu = bi,

⇤

Combining the monotone property in each subinterval and the continuity at each break point, the monotonicity of Uu(xu) on whole interval (0↪ wu] is derived directly.

Corollary 16 For any agent u and any given weight profile x-u, utility function Uu(xu) is monotonically nondecreasing on (0↪ wu].

Obviously, the monotone property of Uu(xu) in Corollary 16 for any given x-u ensures the correctness of Uu(wu↪ x-u) ≥ Uu(xu↪ x-u), where xu 2 (0↪ wu]. So the main result of this paper is deduced directly.

Theorem 17 BD Mechanism is truthful for the resource sharing game.

Remarks: The strategy of weight misreporting cannot be replaced by the strategy of edge cutting [Cheng et al., 2015]. Let us consider an example of a triangle in which three agents have the same weights. Obviously if one edge is cut, the resources can only be allocated along the remaining edges. But if one agent plays the strategy of weight misreporting, the resources are still be allocated on each edge whatever xu 2 (0↪ wu].

4 Numerical Example

In this section, we analyze a representative numerical example to have an intuitive understanding on the above results. Consider the network of Fig. 1. Each cycle represents a vertex and the number in the cycle is depicted the vertex's weight. As stated before, the bottleneck decomposition of

G shall change with agent u's reporting weight xu for any given x-u. So the interval (0↪wu] is partitioned into different disjoint subintervals, each hai↪ bii corresponding to one decomposition Bi . For the example shown in Fig. 1, Table 1 lists all subintervals and all pairs containing u in different subintervals.

From Table 1, there are some important informations worthy of note. First, u is in the same classes in adjacent Bi and Bi+1 that verifies Lemma 10. The relation between adjacent B-sets or C-sets is that of containing and contained which has been proved in Lemma 12 and 13. Second in nonadjacent decompositions, u may be in different classes. For example, when xu 2 [1↪ 3), u is in C-class with ↵u(xu) = (2 + xu)◁15 < 1. And when xu 2 [16↪ 32], then u is a Bclass vertex in B2 with ↵u(xu) = 20◁(8+xu) < 1. So there must be a crucial decomposition Bi . In such a decomposition, u can be viewed as a B-class and a C-class vertex simultaneously which means that ↵u(xu) = 1 if xu 2 hai↪ bii. Obviously in Table 1, xu = 13 just is the turning point and the corresponding decomposition is the crucial one. Third, if the class containing u changes with xu 2 (0↪wu], then the changing process must be from C-class to B-class with the increasing of xu, not vice versa.

(49↪ 1)

¶v1↪ v3↪ u♦

¶v2↪ v4↪ v7♦

Table 1: All subintervals, each corresponding one decomposition. The second and third column represent the pair (B↪ C) which u is in, where u is written in bold.

The left of Fig. 2 well illustrates the property of continuity and monotonically nondecreasing property of Uu(xu). But for ↵-ratio shown in the right of Fig. 2, ↵u(xu) is monotonically increasing when xu < 13 and it is monotonically decreasing when xu > 13. This result just coincides with the facts that u is in C-class when xu < 13 and in B-class when xu > 13 shown in Table 1. In addition, ↵u(xu) reaches its peak at xu = 13 as ↵u(xu)  1.

5 Conclusion

In this article, we discuss the issue of possible strategic manipulations of agents with respect to BD Mechanism for the application of resource exchange. Our work resolves an open problem on the strategic stability of a resource exchange protocol (i.e., the BD mechanism) from the mechanism design perspective.

We show that, no agent could gain by misreporting its resource amount in a BD Mechanism. Combining the work of Cheng, et al., [Cheng et al., 2015], we establish a strong incentive stability result that an agent could not improve its utility by cutting off any incident edge or by reporting less resource. We note that an agent could not benefit even from the combination of the above two strategies. If an agent does so, it is equivalent to a two-stage strategy. At the first stage, the agent cuts some of the adjacent edges. At the second stage, it decreases its weight in the updated network. The results in [Cheng et al., 2015] and in our paper show that the utility of this agent would be non-increasing. So this completes the research on truthfulness of the popular proportional mechanism on resource exchange.

Acknowledgments

This research was partially supported by the National Nature Science Foundation of China (No. 11301475, 61173011), and by the Research Grant Council of Hong Kong (ECS Project No. 26200314 and GRF Project No. 16213115).