The Power Allocation Game on A Network:A Paradox

Yuke Li and A.Stephen Morse,Life Fellow,IEEE

Abstract—The well-known Braess paradox in congestion games states that adding an additional road to a transportation network may increase the total travel time,and consequently decrease the overall efficiency.This paper presents a paradox in a similar spirit and involves a distributed resource allocation game on networks,namely the power allocation game between countries developed in Li and Morse(2017).The paradox is that by having additional friends may actually decrease a country’s total welfare in equilibrium.Conditions for this paradox to occur as well as the price of anarchy results are also derived.

I.INTRODUCTION

I N 1969,a paradoxical example was presented in[2],demonstrating that due to selfish behaviors of agents,a measure aimed to increase the efficiency of a transportation network may produce counter-productive effects.Specifically,it was shown that adding a new route to the transportation network can increase the total travel time therein.The concept of the price of anarchy[3]was adopted to measure the extent of inefficiency caused by agents’behavior of selfish routing in[4]-[9];more recent work includes[10]-[12].For example,[6]obtains lower and upper bounds for the price of anarchy in the congestion game on any transportation network.An optimal network design problem was then formulated and extensively studied in[13]-[21],where the motivation behind this problem was the potential interest of policy makers in designing a transportation network with the goal of minimizing the price of anarchy involved.

This paper proposes a similar paradox that arises in another distributed,resource allocation game on networks,where countries “allocate”their power among their friends and adversaries,namely the power allocation game(PAG).This is a distributed,resource allocation game on a signed graph as suggested in[22],which relates to an emerging line of literature on game theoretic analyses of agent’s interactions in a cooperative and noncooperative networked environment.Some related examples are[23]-[30],and a survey can be found in[31].

This paper focuses on the analysis of the paradox by examining the case of a loss in welfare countries may suffer due to certain changes in the networked environment that were intended to increase its utility.For example,having additional friends in the environment may prevent a country from achieving its optimal welfare.

Obviously,a utility function is needed for the definition of a country’s “welfare”from power allocation and for the introduction of the paradox.A certain family of utility functions that satisfy the two axioms that model countries’preferences for the “power allocation matrices”in[1]and[32]are to be introduced and used throughout the paper.

The paper is structured as the following.In Section II,the set up of the PAG is reviewed,along with a discussion of a family of utility functions to model countries’preferences for“power allocation matrices”,and a paradox is identified.In Section III,conditions for this paradox to occur are derived.The paper concludes with a discussion of the upper and lower bounds for the price of anarchy in the PAG in a general networked environment.

II.THE PAG AND THE PARADOX

A.Basic Idea

By the power allocation game or PAG is meant a distributed resource allocation game between n countries with labels in n={1,2,...,n}[1].The game is formulated on a simple,undirected,signed graph G called “an environment graph”[32]whose n vertices correspond to the countries and whose m edges represent relationships between countries.An edge between distinct vertices i and j,denoted by(i,j),is labeled with a plus sign if countries i and j are friends and with a minus sign if countries i and j are adversaries.For each i ∈ n,Fiand Aidenote the sets of labels of country i’s friends and adversaries respectively;it is assumed that i∈Fiand that Fiand Aiare disjoint sets.Each country i possesses a nonnegative quantity picalled the total power of country i.An allocation of this power or strategy is a nonnegative n×1 row vector uiwhose j component uijis that part of piwhich country i allocates under the strategy to either support country j if j∈Fior to demise country j if j∈Ai;accordingly uij=0 if j/∈ Fi∪Ai.The goal of the game is for each country to choose a strategy which contributes to the demise of all of its adversaries and to the support of all of its friends.

Each set of country strategies{ui,i∈n}determines an n× n matrix U whose i th row is ui.Thus U=[uij]n×nis a nonnegative matrix such that,for each i∈n,ui1+ui2+···+uin=pi.Any such matrix is called a strategy matrix and U is the set of all n×n strategy matrices.

B.Multi-front Pursuit of Survival

In[1]and[32],how countries allocate their power in the support of the survival of its friends and the demise of that of its adversaries is studied,which is in line with fundamental assumptions about countries’behaviors in classic international relations theory.[33]These facts are accounted for by the following additional formulations:

Each strategy matrix U determines for each i∈n,the total support σi(U)of country i and the total threat τi(U)against country i.Here σi:U → R and τi:U → R are non-negative valued maps defined by U -→ P j∈Fiuj i+P j∈Aiuij and U -→ Pj∈Aiujirespectively.Thus,country i’s total support is the sum of the amounts of power that each of country i’s friends allocate to its support,plus the sum of the amounts of power country i allocates to the destruction of all of its adversaries.Country i’s total threat,on the other hand,is the sum of the amounts of power country i’s adversaries allocate to its demise.These allocations in turn determine country i’s state xi(U)which may be safe,precarious,or unsafe depending on the relative values of σi(U)and τi(U).In particular,xi(U)=safe if σi(U)＞ τi(U),xi(U)=precarious if σi(U)= τi(U),or xi(U)=unsafe if σi(U) ＜ τi(U).

In playing the PAG,countries select individual strategies in accordance with certain weak and/or strong preferences.A sufficient set of conditions for country i to weakly prefer strategy matrix V∈U over strategy matrix U∈U are as follows

1)For all j∈Fieither xj(V)∈{safe,precarious},or xj(U)=unsafe,or both.

2)For all j∈Aieither xj(V)∈{unsafe,precarious},or xj(U)=safe,or both.

Weak preference by country i of V over U is denoted by U?V.

Meanwhile,a sufficient condition for country i to be indifferent to the choice between V and U is that xi(U)=xj(V)for all j∈Fi∪Ai.This is denoted by V～U.

Finally,a sufficient condition for country i to strongly prefer V over U is that xi(V)be a safe or precarious state and xi(U)be an unsafe state.Strong preference by country i of V over U is denoted by U?V.

C.Preferences:Utility Function Representation

A country i is to derive a certain amount of utility or welfare from a strategy profile of the PAG assuming a certain networked environment;let i’s utility be a function fi:U-→ R.A family of utility functions with the following three properties satisfies the two preference axioms and makes possible a total order of the power allocation matrices in U.For more details about how this is achieved,please refer to[34].

1)Country i receives a two-valued pairwise utility from each of its friends and adversaries,tij(xj(U)).The specific values of the pairwise utilities can be regarded as proxies of the relative importances attached to each friend and adversary relation.

Pairwise utility tij:{safe,precarious,unsafe}→{tij(1),tij(0)}where tij(1)≥tij(0).tij(1),tij(0)∈R is defined as follows.

If j ∈ Fi,tij(1)and tij(0)respectively stands for i’s pairwise utility from j when σj(U)≥ τj(U)and σj(U) ＜ τj(U);

If j ∈ Ai,tij(1)and tij(0)respectively stands for i’s pairwise utility from j when σj(U) ≤ τj(U)and σj(U) ＞ τj(U).

2)Country i’s total utility fi(U)is only equal toif it has not survived itself.

3)Once country i has survived,its total utility fi(U)＞and is a nondecreasing function of tij(xj(U))for any j∈Fi∪Ai.

For simplicity,this paper’s focus is on a subset of utility functions in this family;for any utility function in this subset,its maximum is attained only when all its friends are safe/precarious,and all its adversaries are unsafe/precarious.

After country i’s self-survival threshold is fulfilled,the function fi(U)exhibits a jump discontinuity.Let the set of i’s friends who are safe/precarious under U be(U)and the set of i’s adversaries who are unsafe/precarious be(U).An example is

Some functions in this family may exhibit more jump discontinuities;for instance,countries may additionally prioritize the survival of some friends.An utility function where country i prioritizes the survival of all its friends before preventing the survival of all its adversaries is below:

D.Definition:A Paradox

Let country i’s optimal welfare from power allocation be the maximum utility i can derive from a power allocation matrix U∈U.Denote it as

Since country i’s optimal welfare from power allocation must differ by environments,we define a pairwise utility i receives from having every other country j(other than i)for each of the following four conditions:

Let the two environments be with the same set of countries where one difference between the environments is that for country i,Fi?.A paradox is said to occur if given two PAGs Γ and,country i can obtain a higher optimal welfare from the former even when it has fewer friends.

Example 1:The following illustrates an example of a paradox,which further motivates the main results in Section III.

The parameters of the first environment in Fig.1(a)1is:

1)Set of countries:n={1,2,3}.

2)Their power:p=[8 6 1].

3)Their relations are:r(1,2)=adversary,and r(2,3)=r(1,3)=friend.

The parameters of the second environment in Fig.1(b)is:

1)Set of countries:n={1,2,3}.

2)Their power:p=[8 6 1].

3)Their relations are:r(1,2)=r(2,3)=adversary,and r(1,3)=friend.

In the first environment,country 3 has a friend relation with both country 1 and country 2,which are adversaries.Any pure strategy Nash equilibrium from the PAG in this environment predicts country 1 to be safe,country 2 to be unsafe/precarious,and country 3 to be safe.This is because even with all of country 3’s total power as support,country 2 may not even be able to survive if country 1 invests more than 7 to attack it,while country 1 and country 2 can always remain safe.If country 3’s utility from having country 2 as a safe/precarious friend is lower than having it as an unsafe/precarious adversary

then it will prefer the second environment where it turns against country 2 with country 1 and gains a higher optimal welfare(with country 2 being unsafe/precarious and countries 1 and 3 being safe in any equilibrium).Therefore,country 3’s optimal welfare in the first environment is always lower than its welfare in the second environment,which constitutes the paradox.

Fig.1.A Paradox for country 3.

III.MAIN RESULTS

This section presents results on the conditions for the stated paradox to occur.In particular,the conditions involve a comparison of the roles of friends in a country’s survival and,after the self-survival is fulfilled,in its attainment of its optimal welfare.

Theorem 1:If a country can survive in the equilibria of the PAG assuming a certain networked international environment,then it can survive in the equilibria of another PAG assuming

1Red edges in Fig.1 denote adversary relations and green edges denote friend relations.an environment with more friends than before,but not vice versa.

Let two PAGs be Γ and Γ,where the only difference between the two environments is that for a country i Fi?Fi.If?U?∈ U?,xi(U?)∈ {safe,precarious},then it must be that∈ {safe,precarious}.

Proof:In Γ,if for a country i,?U?∈ U?,xi(U?) ∈{safe,precarious},by definition

Given that Fi?,any equilibrium allocations in the two games satisfy t

and

Note that

because the only difference between the two environments lies in the number of i’s friends.

Therefore,in any equilibrium∈of,it must also be that

In other words,i must also survive in any equilibrium in the gamewith more friends in the new environment.

Remark 1:The existence of multiple equilibria in the PAG is the reason in Theorem 1 for the comparison between two games,in all of whose equilibria country i survives.Intuitively,the reverse of Theorem 1 may not be true,with the logic being that country i may not gather the level of support in the previous environment to survive in a new environment with some of its former friends becoming nonexistent.Theorem 1 also holds in the case where country i has some of the former adversaries turn nonexistent or new friends,which means when Fi?and?Aihold.

Next a necessary condition and a sufficient condition is respectively to be provided such that a country may achieve a lower optimal welfare in the equilibria of the power allocation game in a new networked environment with more friends than in the previous environment.

Theorem 2(Necessary Condition):A necessary condition for the above stated paradox to occur is that there exists at least a country which derives a higher utility from having another country as an unsafe/precarious adversary than as a unsafe friend.

Given two games Γ and Γ,the only difference between the two underlying environments is Fi?If there exists country i∈ n,then there must exist country j/=i such that

Proof:Suppose to the contrary.That is to say,for any country i,which means that for any country i the utility of having any other country as an unsafe friend exceeds that of having it as an unsafe/precarious adversary.

Given a random environment,let the optimal welfare country i can obtain from the PAG Γ assuming this environment be(U).

Let an alternative environment besuch that the only difference from Γ is that Fi?.Let the optimal welfare country iobtain from the PAG Γ assuming this environment be(U)

Then,

must hold because for any of i’s new friends j,even when xj()∈{unsafe,precarious},

Then having more friends does not decrease i’s optimal welfare from power allocation.

Therefore,in order for the stated paradox to occur,there must exist another country j /= i such that

Theorem 3(Sufficient Condition):A sufficient condition for the stated paradox to occur is that there exists at least one country which derives a higher utility from having another as an unsafe/precarious adversary than as a safe/precarious friend and that the total power of these two countries is smaller than that of all other countries in the environment.

For country i∈n,suppose that there exists another country j/=i such thatand that

Then there can be constructed two different environments in which the PAG takes place Γ and Γ where the only difference between the two environments is that for a country i Fi?Fi.The stated paradox then occurs for country i_as it switches from Γ to Γ,which means that

Proof:Let the environment of the PAG Γ be such that all countries other than i are adversaries with j.i is a friend with all of the other countries including j.Let the environment of the PAG Γ be such that all countries are adversaries with j,and i is a friend with all of the other countries excluding j.

Since

there must hold that in any equilibrium U?∈ U?of Γ,

and

The same must hold for in any equilibrium

To country i,country j is an unsafe/precarious friend in Γ and an unsafe/precarious adversary in

Therefore,having more friends than before decreases country i’s optimal welfare from power allocation.

Theorem 3 extends to the case where a country may have a subset of countries in the environment,each of which satisfies the stated condition.Thus Corollary 1 immediately follows.Then when the conditions in Corollary 1 holds,having more friends from this subset only decreases its optimal welfare from power allocation for a country.

Corollary 1:If there exists at least a country which derives a higher utility from having any other in a subset of countries(which it is not a member of)as an unsafe/precarious foe than as a safe/precarious friend and the total power of this country and those in the subset is smaller than that of all other countries in the environment,then the stated paradox is to occur.

For country i∈n,suppose that there exists a subset of countries S such that i/∈ S and for any j ∈ S,and thatThen there exists two games assuming different environments Γ and Γ where the only difference between the environments is that for a countryexist such that

Proof:Let the environment of the PAG Γ be such that all countries other than i are adversaries with any country j in S.i is a friend with all other countries including countries in S.Let the environment of the PAG Γ be such that all countries are adversaries with countries in S,and i is a friend with all of the other countries excluding those in S.

Since

it must hold that in any equilibrium U?∈ U?of Γ,

and

The same must also hold in any equilibrium∈of

To country i,any country j∈S is an unsafe/precarious friend in Γ and an unsafe/precarious adversary in

IV.THE PRICE OF ANARCHY RESULTS

In this section we compare the implications of different networked international environments for the total welfare of countries in the power allocation game,by assessing the“price of anarchy”in different environments.Price of anarchy(POA)is commonly used as a measure of how far from optimality the system downgrades due to the selfish behaviors of agents.

Definition 1(Price of Anarchy Concept[3]):

Lemma 1:In any PAG Γ,at least a country survives in any U∈U.Note that this holds regardless of whether U is an equilibrium.

In Γ,?U ∈ U,?i∈ n such that xi(U)∈ {safe,precarious}.

Proof:The proof is by contradiction.Given an U∈U,suppose that?i∈ n,xi(U)=unsafe.That is to say that,

Equivalently,

Summing from 1 to n in n gives the following,

Note that,

Then there holds that

However,by each country’s total power constraint,it must be the case that

Hence there is a contradiction.Therefore,given an U∈U,there must exist i∈n,xi(U)={safe,precarious}.In other words,in any power allocation matrix assuming any environment,it can never be the case that there is no survivor.

Based on Lemma 1,in the worst case equilibria of the power allocation game,it has to hold that at least a country survives.Given this,an upper bound for the price of anarchy in the PAG is immediate because in the worst case equilibria there is only one survivor and the utilities of all countries are the smallest possible.In addition,environments which give a lower bound for the price of anarchy can be constructed,which can be achieved in environments without any antagonism.

Theorem 4:In the power allocation game Γ,

where

and

Proof:In an environment without any antagonism among countries,is achieved with all countries allocating zero to one other.At the same time,is also achieved because this is obviously an equilibrium.Therefore,in this case PoA=1.

Obviously,there exists no lower value for PoA;otherwise,it means that even better total welfare can be achieved in equilibrium.However,this creates a contradiction because U?already achieves the optimal total welfare.1 is tight as a lower bound for the PAG in environments without any adversary relations.

Now rank all countries’pairwise utilities from not having survived itself,tii(0),i∈n,nondecreasingly,and denote the maximum as

and the minimum as

Rank all countries’pairwise utilities from not having survived itself,(1),i∈n,nondecreasingly,and denote the maximum as

and the minimum as

Rank the optimal welfare of all countries

nondecreasingly,and denote the highest as

By Lemma 1,in any PAG,at least one country survives.Suppose there exists a PAG where exactly one country survives and the utility of this country is inf{(1):i∈n}.Since the other countries have not survived,their utilities are at least

This then gives the upper bound PoA≤where

and

V.DISCUSSION AND CONCLUSION

This paper analytically studies a paradox emerging from the PAG.Specifically,the paper shows that friends may play different roles in a country’s survival and its attainment of optimal welfare.Much like what Example 1 has shown,a country’s having many friends may impede its attainment of optimal welfare from power allocation,especially when potential friends have conflicts among themselves.

However,paradoxes of this kind are unsurprising in a political context.To win over as many allies as possible always requires a country to straddle middle grounds between parties with perhaps irreconcilable differences or even conflicts.Just as the former British PM,Margaret Thatcher,accurately stated,“standing in the middle of the road is very dangerous;you get knocked down by the traffic from both sides.”