The Power Allocation Game on A Network: A Paradox
  IEEE/CAA Journal of Automatica Sinica  2018, Vol. 5 Issue(4): 771-776   PDF    
The Power Allocation Game on A Network: A Paradox
Yuke Li, A. Stephen Morse     
Department of Political Science, A. S. Morse is with the Department of Electrical Engineering, Yale University, New Haven, CT, USA
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.
Key words: Friends     paradox     price of anarchy     resource allocation game     success     survival     utility    
Ⅰ. INTRODUCTION

In 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 Ⅱ, 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 Ⅲ, 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.

Ⅱ. 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, \ldots, n\}$ [1]. The game is formulated on a simple, undirected, signed graph $\mathbb{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\in {n}$, $\mathcal{F}_i$ and $\mathcal{A}_i$ denote the sets of labels of country $i$'s friends and adversaries respectively; it is assumed that $i\in\mathcal{F}_i$ and that $\mathcal{F}_i$ and $\mathcal{A}_i$ are disjoint sets. Each country $i$ possesses a nonnegative quantity $p_i$ called the $\mathit{ total \ power}$ of country $i$. An allocation of this power or $\mathit{ strategy}$ is a nonnegative $n\times 1$ row vector $u_i$ whose $j$ component $u_{ij}$ is that part of $p_i$ which country $i$ allocates under the strategy to either support country $j$ if $j\in\mathcal{F}_i$ or to demise country $j$ if $j\in\mathcal{A}_i$; accordingly $u_{ij}= 0$ if $j\not\in\mathcal{F}_i\cup\mathcal{A}_i$. 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 $\{u_i, \;i\in {n}\}$ determines an $n\times n$ matrix $U$ whose $i$th row is $u_i$. Thus $U = [u_{ij}]_{n\times n}$ is a nonnegative matrix such that, for each $i\in{n}$, $u_{i1}+u_{i2}+\cdots +u_{in} = p_i$. Any such matrix is called a $\mathit{ strategy \ matrix}$ and $\mathcal{U}$ is the set of all $n\times 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\in{n}$, the total support $\sigma_i(U)$ of country $i$ and the total threat $\tau_i(U)$ against country $i$. Here $\sigma_i:\mathcal{U}\rightarrow \mathbb{R}$ and $\tau_i:\mathcal{U}\rightarrow \mathbb{R}$ are non-negative valued maps defined by $U\longmapsto \sum_{j\in\mathcal{F}_i}u_{ji} +\sum_{j\in\mathcal{A}_i}u_{ij}$ and $U\longmapsto \sum_{j\in\mathcal{A}_i}u_{ji}$ respectively. 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 $\mathit{ state}$ $x_i(U)$ which may be safe, precarious, or unsafe depending on the relative values of $\sigma _i(U)$ and $\tau_i(U)$. In particular, $x_i(U) = $ safe if $\sigma_i(U)>\tau_i(U)$, $x_i(U)=$ precarious if $\sigma_i(U)=\tau_i(U)$, or $x_i(U) = $ unsafe if $\sigma_i(U)<\tau_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\in\mathcal{U}$ over strategy matrix $U\in\mathcal{U}$ are as follows

1) For all $j\in\mathcal{F}_i$ either $x_j(V)\in$ {safe, precarious}, or $x_j(U) = $ unsafe, or both.

2) For all $j\in\mathcal{A}_i$ either $x_j(V) \in $ {unsafe, precarious}, or $x_j(U) = $ safe, or both.

Weak preference by country $i$ of $V$ over $U$ is denoted by $U \preceq V$.

Meanwhile, a sufficient condition for country $i$ to be indifferent to the choice between $V$ and $U$ is that $x_i(U)=x_j(V)$ for all $j\in\mathcal{F}_i\cup\mathcal{A}_i$. This is denoted by $V\sim U$.

Finally, a sufficient condition for country $i$ to strongly prefer $V$ over $U$ is that $x_i(V)$ be a safe or precarious state and $x_i(U)$ be an unsafe state. Strong preference by country $i$ of $V$ over $U$ is denoted by $U \prec 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 $f_i: \mathcal{U} \longrightarrow \mathbb{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 $\mathcal{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, $t_{ij}(x_{j}(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 $t_{ij}\!\!:\!\!\{\!\text{safe}, \text{precarious}, \text{unsafe}\!\}\!\! \rightarrow\!\! \{\!t_{ij}(1), t_{ij}(0)\!\}$ where $t_{ij}(1) \geq t_{ij}(0)$. $t_{ij}(1), t_{ij}(0) \in \mathbb{R}$ is defined as follows.

If $j \in \mathcal{F}_{i}$, $t_{ij}(1)$ and $t_{ij}(0)$ respectively stands for $i$'s pairwise utility from $j$ when $\sigma_{j}(U) \geq \tau_{j}(U)$ and $\sigma_{j}(U) < \tau_{j}(U)$;

If $j \in \mathcal{A}_{i}$, $t_{ij}(1)$ and $t_{ij}(0)$ respectively stands for $i$'s pairwise utility from $j$ when $\sigma_{j}(U) \leq \tau_{j}(U)$ and $\sigma_{j}(U) > \tau_{j}(U)$.

2) Country $i$'s total utility $f_{i}(U)$ is only equal to $t_{ii}^0$ if it has not survived itself.

3) Once country $i$ has survived, its total utility $f_{i}(U) > t_{ii}^0$, and is a nondecreasing function of $t_{ij}(x_{j}(U))$ for any $j \in \mathcal{F}_{i} \cup \mathcal{A}_{i}$.

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 $f_{i}(U)$ exhibits a jump discontinuity. Let the set of $i$'s friends who are safe/precarious under $U$ be $\mathcal{F}^{1}_{i}(U)$ and the set of $i$'s adversaries who are unsafe/precarious be $\mathcal{A}^{1}_{i}(U)$. An example is

$ f_{i}(U) = \begin{cases} t_{ii}(0),&x_{i}(U)\! =\! \text{unsafe} \\ \sum\nolimits_{i \in \mathcal{F}^{1}_{i}(U) \cup \mathcal{A}^{1}_{i}(U)}t_{ij}(1),&x_{i}(U)\! \in\! \{\text{safe, precarious}\}.\\ %0&j \not\in \{i\} \cup \mathcal{F}_{i} \cup \mathcal{A}_{i} \end{cases} $

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:

$ f_{i}(U) = \begin{cases} t_{ii}(0),&x_{i}(U)\! =\! \text{unsafe}\\ \sum\nolimits_{j \in \mathcal{F}^{1}_{i}(U)} t_{ij}(1),&x_{i}(U)\! \in\! \{\text{safe, precarious}\}\\ \sum\nolimits_{i \in \mathcal{F}^{1}_{i}(U) \cup \mathcal{A}^{1}_{i}(U)}t_{ij}(1),&x_{i}(U)\! \in\! \{\text{safe, precarious}\}, \\&\forall j\! \in\! \mathcal{F}_i. \end{cases} $
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 \in \mathcal{U}$. Denote it as

$ f^{*}_{i}(U) $

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

1) $t_{ij}^{\mathcal{F}}(1)$: $j \in \mathcal{F}_{i}$ and $x_{j}(U) \in \{\text{safe}, \text{precarious}\}$.

2) $t_{ij}^{\mathcal{F}}(0)$: $j \in \mathcal{F}_{i}$ and $x_{j}(U) = \text{unsafe}$.

3) $t_{ij}^{\mathcal{A}}(1)$: $j \in \mathcal{A}_{i}$ and $x_{j}(U) \in \{\text{unsafe}, \text{precarious}\}$.

4) $t_{ij}^{\mathcal{A}}(0)$: $j \in \mathcal{A}_{i}$ and $x_{j}(U) = \text{safe}$.

Let the two environments be with the same set of countries where one difference between the environments is that for country $i$, $\mathcal{F}_{i} \subset \mathcal{\overline{F}}_{i}$. A paradox is said to occur if given two PAGs $\Gamma$ and $\overline{\Gamma}$, country $i$ can obtain a higher optimal welfare from the former even when it has fewer friends.

$\mathit{Example\ 1:}$ The following illustrates an example of a paradox, which further motivates the main results in Section Ⅲ.

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

Download:
Fig. 1 A Paradox for country 3.

1Red edges in Fig. 1 denote adversary relations and green edges denote friend relations.

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

2) Their power: $p = [8\quad 6 \quad1]$.

3) Their relations are: $r(1, 2) = \text{adversary}$, and $r(2, 3) = r(1, 3) = \text{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 \quad 6 \quad 1]$.

3) Their relations are: $r(1, 2) = r(2, 3) = \text{adversary}$, and $r(1, 3) = \text{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

$ t_{32}^{\mathcal{F}}(1) < t_{32}^{\mathcal{A}}(1), $

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.

Ⅲ. 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.

$\mathit{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 an environment with more friends than before, but not vice versa.

Let two PAGs be $\Gamma$ and $\overline{\Gamma}$, where the only difference between the two environments is that for a country $i$ $\mathcal{F}_i \subset \mathcal{\overline{F}}_{i}$. If $\forall U^* \in \mathcal{U}^*$, $x_i(U^*) \in \{\text{safe}, \text{precarious}\}$, then it must be that $\forall \overline{U}^* \in \mathcal{\overline{U}}^*$, $x_i(\overline{U}^*) \in \{\text{safe}, \text{precarious}\}$.

$\mathit{Proof:}$ In $\Gamma$, if for a country $i$, $\forall U^* \in \mathcal{U}^*$, $x_i(U^*) \in \{\text{safe}, \text{precarious}\}$, by definition

$ \sum\limits_{j \in \mathcal{F}_i}u^*_{ji} + \sum\limits_{j \in \mathcal{A}_i}u^*_{ij} \geq \sum\limits_{j \in \mathcal{A}_i}u^*_{ji}. $

Given that $\mathcal{F}_i \subset \mathcal{\overline{F}}_{i}$, any equilibrium allocations in the two games satisfy the following:

$ \sum\limits_{j \in \mathcal{F}_i} \overline{u}^*_{ji} + \sum\limits_{j \in \mathcal{A}_i}\overline{u}^*_{ij} \geq \sum\limits_{j \in \mathcal{F}_i} u^*_{ji} + \sum\limits_{j \in \mathcal{A}_i}u^*_{ij} $

and

$ \sum\limits_{j \in \mathcal{F}_i} u^*_{ji} + \sum\limits_{j \in \mathcal{A}_i}u^*_{ij} \geq \text{sup} \{\tau_{i}(U^*): U^* \in \mathcal{U}^*\}. $

Note that

$ \text{sup} \{\tau_{i}(U^*): U^* \in \mathcal{U}^*\} = \text{sup} \{\tau_{i}(\overline{U}^*): \overline{U}^* \in \mathcal{\overline{U}}^*\}, $

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

Therefore, in any equilibrium $\overline{U}^* \in \mathcal{\overline{U}^*}$ of $\overline{\Gamma}$, it must also be that

$ \sum\limits_{j \in \mathcal{F}_i}\overline{u}^*_{ji} + \sum\limits_{j \in \mathcal{A}_i}\overline{u}^*_{ij} \geq \sum\limits_{j \in \mathcal{A}_i}\overline{u}^*_{ji}. $

In other words, $i$ must also survive in any equilibrium in the game $\overline{\Gamma}$ with more friends in the new environment.

$\mathit{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 $\mathcal{F}_i \subset \mathcal{\overline{F}}_{i}$ and $\mathcal{\overline{A}}_i \subset \mathcal{A}_{i}$ hold.

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.

$\mathit{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 $\Gamma$ and $\overline{\Gamma}$, the only difference between the two underlying environments is $\mathcal{F}_i \subset \mathcal{\overline{F}}_{i}$. If there exists country $i \in {n}$, $f^{*}_{i}(U) > \overline{f}^{*}_{i}(\overline{U})$, then there must exist country $j \neq i$ such that $t_{ij}^{\mathcal{F}}(0) < t_{ij}^{\mathcal{A}}(1)$.

$\mathit{Proof:}$ Suppose to the contrary. That is to say, for any country $i$, $t_{ij}^{\mathcal{F}}(0) \geq t_{ij}^{\mathcal{A}}(1)$, $j \neq 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 $\Gamma$ assuming this environment be $f^*_{i}(U)$.

Let an alternative environment be $\overline{\Gamma}$ such that the only difference from $\Gamma$ is that $\mathcal{F}_i \subset \mathcal{\overline{F}}_{i}$. Let the optimal welfare country $i$ can obtain from the PAG $\Gamma$ assuming this environment be $\overline{f}^*_{i}(U)$

Then,

$ f^{*}_{i}(U) > \overline{f}^{*}_{i}(\overline{U}) $

must hold because for any of $i$'s new friends $j$, even when $x_{j}(\overline{U}) \in \{\text{unsafe}, \text{precarious}\}$, $t_{ij}^{\mathcal{F}}(0) \geq t_{ij}^{\mathcal{A}}(1)$.

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 \neq i$ such that $t_{ij}^{\mathcal{F}}(0) < t_{ij}^{\mathcal{A}}(1)$.

$\mathit{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 \in n$, suppose that there exists another country $j \neq i$ such that $t_{ij}^{\mathcal{A}}(1) > t_{ij}^{\mathcal{F}}(1)$, and that $p_i + p_j \leq \displaystyle\sum_{k \in {n} - \{i, j\}}p_i$. Then there can be constructed two different environments in which the PAG takes place $\Gamma$ and $\overline{\Gamma}$ where the only difference between the two environments is that for a country $i$ $\mathcal{F}_i \subset \mathcal{\overline{F}}_{i}$. The stated paradox then occurs for country $i$ as it switches from $\Gamma$ to $\overline{\Gamma}$, which means that $f^*_i(U^*) < \overline{f}^*_i(\overline{U}^{*})$.

$\mathit{Proof:}$ Let the environment of the PAG $\Gamma$ 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 $\overline{\Gamma}$ be such that all countries are adversaries with $j$, and $i$ is a friend with all of the other countries excluding $j$.

Since

$ p_i + p_j \leq \displaystyle\sum\limits_{k \in {n} - \{i, j\}}p_i, $

there must hold that in any equilibrium $U^* \in \mathcal{U}^*$ of $\Gamma$,

$ x_{j}(U^*) \in \{\text{unsafe, precarious}\}, $

and

$ \forall k \neq j, x_{k}(U^*) \in \{\text{safe}, \text{precarious}\}. $

The same must hold for in any equilibrium $\overline{U}^* \in \mathcal{\overline{U}}^*$ of $\overline{\Gamma}$.

To country $i$, country $j$ is an unsafe/precarious friend in $\Gamma$ and an unsafe/precarious adversary in $\overline{\Gamma}$.

Since $t_{ij}^{\mathcal{A}}(1) > t_{ij}^{\mathcal{F}}(1) \geq t_{ij}^{\mathcal{F}}(0)$, it must be that $f^*_i(U^*) < \overline{f}^*_i(\overline{U}^*)$, with all other pairwise utilities from other neighbors being equal.

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.

$\mathit{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 \in {n}$, suppose that there exists a subset of countries $\mathcal{S}$ such that $i \not\in \mathcal{S}$ and for any $j \in \mathcal{S}$, $t_{ij}^{\mathcal{A}}(1) > t_{ij}^{\mathcal{F}}(1)$, and that $p_{i} + \displaystyle\sum_{j \in \mathcal{S}} p_j \leq \displaystyle\sum_{k \in {n} -\{i\} - \mathcal{S}}p_k$. Then there exists two games assuming different environments $\Gamma$ and $\overline{\Gamma}$ where the only difference between the environments is that for a country $i$ $\mathcal{F}_i \subset \mathcal{\overline{F}}_{i}$, and a $U^{*} \in \mathcal{U}^{*}$ and a $\overline{U}^{*} \in \mathcal{\overline{U}}^{*}$ exist such that $f^*_i(U^*) < \overline{f}^*_i(\overline{U}^{*})$.

$\mathit{Proof:}$ Let the environment of the PAG $\Gamma$ be such that all countries other than $i$ are adversaries with any country $j$ in $\mathcal{S}$. $i$ is a friend with all other countries including countries in $\mathcal{S}$. Let the environment of the PAG $\overline{\Gamma}$ be such that all countries are adversaries with countries in $\mathcal{S}$, and $i$ is a friend with all of the other countries excluding those in $\mathcal{S}$.

Since

$ p_{i} + \displaystyle\sum\limits_{j \in \mathcal{S}} p_j \leq \displaystyle\sum\limits_{k \in {n} -\{i, \mathcal{S}\}}p_k, $

it must hold that in any equilibrium $U^* \in \mathcal{U}^*$ of $\Gamma$,

$ \forall j \in \mathcal{S}, x_{j} = \{\text{unsafe, precarious}\} $

and

$ \forall k \not\in \mathcal{S}, x_{k} \in \{\text{safe}, \text{precarious}\}. $

The same must also hold in any equilibrium $\overline{U}^* \in \mathcal{\overline{U}}^*$ of $\overline{\Gamma}$.

To country $i$, any country $j \in \mathcal{S}$ is an unsafe/precarious friend in $\Gamma$ and an unsafe/precarious adversary in $\overline{\Gamma}$.

Since $\forall j \in \mathcal{S}$, $t_{ij}^{\mathcal{A}}(1) > t_{ij}^{\mathcal{F}}(1) \geq t_{ij}^{\mathcal{F}}(0)$, there holds that $f^*_i(U^*) < \overline{f}^*_i(\overline{U}^*)$. Therefore, having more friends than before decreases country $i$'s optimal welfare from power allocation.

Ⅳ. 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]):

$ \frac{\displaystyle\max\limits_{U\in \mathcal{U}} \displaystyle\sum\limits_{i \in {n}}f_{i}(U)}{\displaystyle\min\limits_{U \in \mathcal{U^*}}\displaystyle\sum\limits_{i \in {n}}f_{i}(U^*)} $

$\mathit{Lemma\ 1:}$ In any PAG $\Gamma$, at least a country survives in any $U \in \mathcal{U}$. Note that this holds regardless of whether $\mathcal{U}$ is an equilibrium.

In $\Gamma$, $\forall U \in \mathcal{U}$, $\exists i \in {n}$ such that $x_i(U) \in \{\text{safe}, \text{precarious}\}$.

$\mathit{Proof:}$ The proof is by contradiction. Given an $U \in \mathcal{U}$, suppose that $\forall i \in {n}$, $x_i(U) = \text{unsafe}$. That is to say that,

$ \forall i \in {n}, \sum\limits_{j \in \mathcal{F}_{i}}u_{ji} + \sum\limits_{j \in \mathcal{A}_{i}}u_{ij} < \sum\limits_{j \in \mathcal{A}_{i}}u_{ji}. $

Equivalently,

$ \forall i \in {n}, p_{i} - \sum\limits_{j \in \mathcal{F}_{i}}u_{ji} + \sum\limits_{j \in \mathcal{F}_{i}}u_{ji} < \sum\limits_{j \in \mathcal{A}_{i}}u_{ji}. $

Summing from 1 to $n$ in ${n}$ gives the following,

$ \sum\limits_{i \in {n}}p_i - \sum\limits_{i \in {n}}(\sum\limits_{j \in \mathcal{F}_{i}}u_{ji} - \sum\limits_{j \in \mathcal{F}_{i}}u_{ij}) < \sum\limits_{i \in {n}}\sum\limits_{j \in \mathcal{A}_{i}}u_{ji}. $

Note that,

$ \sum\limits_{i \in {n}}(\sum\limits_{j \in \mathcal{F}_{i}}u_{ji} - \sum\limits_{j \in \mathcal{F}_{i}}u_{ij}) = \sum\limits_{\{i, j\} \in \mathcal{R}_{\mathcal{F}}}(u_{ji} - u_{ij}) + (u_{ij} - u_{ji}) = 0. $

Then there holds that

$\sum\limits_{i \in {n}}p_i < \sum\limits_{i \in {n}}\sum\limits_{j \in \mathcal{A}_{i}}u_{ji}. $

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

$ \sum\limits_{i \in {n}}p_i \geq \sum\limits_{i \in {n}}\sum\limits_{j \in \mathcal{A}_{i}}u_{ji}. $

Hence there is a contradiction. Therefore, given an $U \in \mathcal{U}$, there must exist $i \in {n}$, $x_i(U) = \{\text{safe}, \text{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.

$\mathit{Theorem\ 4:}$ In the power allocation game $\Gamma$,

$ 1 \leq \text{PoA} \leq \frac{A}{B} $

where

$ A = n \text{sup}\{\sum\limits_{j \in \mathcal{F}_i}t_{ij}^{\mathcal{F}}(1) + \sum\limits_{j \in \mathcal{A}_i}t_{ij}^{\mathcal{A}}(1): i \in {n}\} $

and

$ B = (n-1)\text{inf}\{t_{ii}^{\mathcal{F}}(0): i \in {n}\} + \text{inf}\{t_{ii}^{\mathcal{F}}(1): i \in{n}\}. $

$\mathit{Proof:}$ In an environment without any antagonism among countries, $\displaystyle\max_{U \in \mathcal{U}} \sum_{i \in {n}}f^*_{i}(U)$ is achieved with all countries allocating zero to one other. At the same time, $\displaystyle\max_{U^* \in \mathcal{U^*}}\sum_{i \in {n}}f^*_{i}(U^*)$ is also achieved because this is obviously an equilibrium. Therefore, in this case $\text{PoA} = 1$.

Obviously, there exists no lower value for $\text{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, $t_{ii}(0)$, $i \in {n}$, nondecreasingly, and denote the maximum as

$ \text{sup}\{t_{ii}^{\mathcal{F}}(0): i \in {n}\} $

and the minimum as

$ \text{inf}\{t_{ii}^{\mathcal{F}}(0): i \in {n}\}. $

Rank all countries' pairwise utilities from not having survived itself, $t_{ii}^{\mathcal{F}}(1), i \in {n}$, nondecreasingly, and denote the maximum as

$ \text{sup}\{t_{ii}^{\mathcal{F}}(1): i \in {n}\} $

and the minimum as

$ \text{inf}\{t_{ii}^{\mathcal{F}}(1): i \in {n}\}. $

Rank the optimal welfare of all countries

$ \sum\limits_{j \in \mathcal{F}_{i}}t_{ij}^{\mathcal{F}}(1) + \sum\limits_{j \in \mathcal{A}_i}t_{ij}^{\mathcal{A}}(1), i \in {n} $

nondecreasingly, and denote the highest as

$ \text{sup}\{\sum\limits_{j \in \mathcal{F}_i}t_{ij}^{\mathcal{F}}(1) + \sum\limits_{j \in \mathcal{A}_i}t_{ij}^{\mathcal{A}}(1), i \in {n}\}. $

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 $\text{inf}\{t_{ii}^{\mathcal{F}}(1): i \in {n}\}$. Since the other countries have not survived, their utilities are at least

$ \text{inf}\{t_{ii}^{\mathcal{F}}(0): i \in {n}\}. $

This then gives the upper bound $\text{PoA} \leq \frac{A}{B}$ where

$ A = n \text{sup}\{\sum\limits_{j \in \mathcal{F}_i}t_{ij}^{\mathcal{F}}(1) + \sum\limits_{j \in \mathcal{A}_i}t_{ij}^{\mathcal{A}}(1): i \in {n}\} $

and

$ B = (n - 1){\rm{inf}}\{ t_{ii}^{\cal F}(0):i \in n\} + {\rm{inf}}\{ t_{ii}^{\cal F}(1):i \in n\} . $
Ⅴ. 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."

REFERENCES
[1] Y. K. Li and A. S. Morse, "Game of power allocation on networks, " Proc. American Control Conf., Seattle, WA, USA, 2017, pp. 5231-5236. http://arxiv.org/abs/1610.00787
[2] D. Braess, "Über ein paradoxon aus der verkehrsplanung, " Unternehmensforschung, vol. 12, no. 1, pp. 258-268, Dec. 1968. https://link.springer.com/article/10.1007/BF01918335
[3] E. Koutsoupias and C. Papadimitriou, "Worst-case equilibria, " Comput. Sci. Rev., vol. 3, no. 2, pp. 65-69, May 2009.
[4] H. Lin, T. Roughgarden, and É. Tardos, "A stronger bound on braessś paradox, " in Proc. 15th Annu. ACM-SIAM Symp. Discrete Algorithms, New Orleans, Louisiana, USA, 2004, pp. 340-341. http://dl.acm.org/citation.cfm?id=982840
[5] X. Huang, A. E Ozdaglar, and D. Acemoglu, "Efficiency and braessṕaradox under pricing in general networks, " IEEE J. Sel. Areas Commun., vol. 24, no. 5, pp. 977-991, May 2006.
[6] T. Roughgarden and É. Tardos, "How bad is selfish routing?, " J. ACM (JACM), vol. 49, no. 2, pp. 236-259, Mar. 2002. http://dl.acm.org/citation.cfm?id=506153
[7] H. Youn, M. T Gastner, and H. Jeong, "Price of anarchy in transportation networks: Efficiency and optimality control, " Phys. Rev. Lett., vol. 101, no. 12, pp. 128701, Sep. 2008. http://www.ncbi.nlm.nih.gov/pubmed/18851419
[8] T. Roughgarden, Selfish Routing and the Price of Anarchy. Cambridge, MA, USA: MIT Press, 2005.
[9] H. Lin, T. Roughgarden, É. Tardos, and A. Walkover, "Stronger bounds on braessś paradox and the maximum latency of selfish routing, " SIAM J. Discrete Math., vol. 25, no. 4, pp. 1667-1686, Jan. 2011. http://dl.acm.org/citation.cfm?id=2340567
[10] J. R. Marden and T. Roughgarden, "Generalized efficiency bounds in distributed resource allocation, " IEEE Trans. Autom. Control, vol. 59, no. 3, pp. 571-584, Mar. 2014. http://ieeexplore.ieee.org/xpls/icp.jsp?arnumber=5717472
[11] G. Piliouras, E. Nikolova, and J. S. Shamma, "Risk sensitivity of price of anarchy under uncertainty, " ACM Trans. Econ. Comput., (TEAC), vol. 5, no. 1, pp. Article No. 5, Nov. 2016. http://dl.acm.org/citation.cfm?id=2482578
[12] D. Acemoglu, A. Makhdoumi, A. Malekian, and A. Ozdaglar, "Informational braessṕaradox: the effect of information on traffic congestion, " arXiv preprint arXiv: 1601. 02039, 2016. http://arxiv.org/abs/1601.02039
[13] M. Y. Chen and A. S. Alfa, "A network design algorithm using a stochastic incremental traffic assignment approach, " Transp. Sci., vol. 25, no. 3, pp. 215-224, Aug. 1991. http://dl.acm.org/citation.cfm?id=2749152
[14] T. L Friesz, H. J. Cho, N. J. Mehta, R. L. Tobin, and G. Anandalingam, "A simulated annealing approach to the network design problem with variational inequality constraints, " Transp. Sci., vol. 26, no. 1, pp. 18-26, Feb. 1992. http://dl.acm.org/citation.cfm?id=2726930
[15] L. J. Leblanc, "An algorithm for the discrete network design problem, " Transp. Sci., vol. 9, no. 3, pp. 183-199, Aug. 1975. http://www.jstor.org/stable/25767791
[16] T. Roughgarden, "Designing networks for selfish users is hard, " Proc. 42nd IEEE Symp. Foundations of Computer Science, Las Vegas, Nevada, USA, 2001, pp. 472-481. http://www.ams.org/mathscinet-getitem?mr=1948736
[17] H. Yang and M. G. H. Bell, "Models and algorithms for road network design: a review and some new developments, " Transp. Rev., vol. 18, no. 3, pp. 257-278, Jul. 1998. http://www.researchgate.net/publication/248987340_Models_and_algorithms_for_road_network_design_a_review_and_some_new_developments
[18] T. L. Magnanti and R. T. Wong, "Network design and transportation planning: models and algorithms, " Transp. Sci., vol. 18, no. 1, pp. 1-55, Feb. 1984. http://dl.acm.org/citation.cfm?id=2735942
[19] P. N. Brown and J. R. Marden, "Studies on robust social influence mechanisms: incentives for efficient network routing in uncertain settings, " IEEE Control Syst., vol. 37, no. 1, pp. 98-115, Feb. 2017. http://www.researchgate.net/publication/313147141_Studies_on_Robust_Social_Influence_Mechanisms_Incentives_for_Efficient_Network_Routing_in_Uncertain_Settings
[20] H. Poorzahedy and M. A. Turnquist, "Approximate algorithms for the discrete network design problem, " Transp. Res. Part B: Meth., vol. 16, no. 1, pp. 45-55, Feb. 1982. http://www.sciencedirect.com/science/article/pii/0191261582900406
[21] C. Suwansirikul, T. L. Friesz, and R. L. Tobin, "Equilibrium decomposed optimization: a heuristic for the continuous equilibrium network design problem, " Transp. Sci., vol. 21, no. 4, pp. 254-263, Nov. 1987. http://www.jstor.org/stable/25768284
[22] Y. K. Li and A. S. Morse, "Game of countriesṕower allocation on networks: balancing equilibrium, " Proc. American Control Conf., Forthcoming, 2018.
[23] T. Alpcan and T. Başar, Network Security: A Decision and Game-Theoretic Approach. Cambridge, UK: Cambridge University Press, 2010.
[24] E. Feron, E. Abed, N. Balcan, J. Baras, P. Young, L. Kaebling, N. Martins, A. Ozdaglar, J. Shamma, and E. Frazzoli, "Distributed learning and information dynamics in networked autonomous systems, " Georgia Tech Research Corp Atlanta Atlanta, Tech. Rep., 2015. http://www.dtic.mil/docs/citations/AD1000659
[25] D. Acemoglu, A. Malekian, and A. Ozdaglar, "Network security and contagion, " J. Econ. Theory, vol. 166, pp. 536-585, Nov. 2016. http://www.sciencedirect.com/science/article/pii/S0022053116300837
[26] D. Bauso, H. Tembine, and T. Başar, "Robust mean field games, " Dyn. Games Appl., vol. 6, no. 3, pp. 277-303, Sep. 2016. http://link.springer.com/article/10.1007/s13235-015-0160-4
[27] H. Tembine, Q. Y. Zhu, and T. Başar, "Risk-sensitive mean-field games, " IEEE Trans. Autom. Control, vol. 59, no. 4, pp. 835-850, Apr. 2014. http://ieeexplore.ieee.org/document/6656891/
[28] K. C. Cao, Y. Q. Chen, and D. Stuart, "A fractional micro-macro model for crowds of pedestrians based on fractional mean field games, " IEEE/CAA J. of Autom. Sinica, vol. 3, no. 3, pp. 261-270, Jul. 2016. http://www.en.cnki.com.cn/Article_en/CJFDTotal-ZDHB201603006.htm
[29] S. Li, M. C. Zhou, X. Luo, and Z. H. You, "Distributed winner-take-all in dynamic networks, " IEEE Trans. Autom. Control, vol. 62, no. 2, pp. 577-589, Feb. 2017. http://www.researchgate.net/publication/303872576_Distributed_Winner-take-all_in_Dynamic_Networks
[30] L. Xue, C. Y. Sun, D. Wunsch, Y. J. Zhou, and F. Yu, "An adaptive strategy via reinforcement learning for the prisoner's dilemma game, " IEEE/CAA J. of Autom. Sinica, vol. 5, no. 1, pp. 301-310, Jan. 2018. http://kns.cnki.net/KCMS/detail/detail.aspx?filename=zdhb201801030&dbname=CJFD&dbcode=CJFQ
[31] J. R. Marden and J. S. Shamma, "Game theory and distributed control, " in Handbook of Game Theory with Economic Applications, H. P. Young and S. Zamir, Eds. New York, USA: Elsevier, 2015, pp. 861-899. http://citeseerx.ist.psu.edu/viewdoc/summary?cid=26432885
[32] Y. K. Li, A. S. Morse, J. Liu, and T. Başar, "Countries' Survival in networked international environments, " Proc. IEEE Conf. Decision and Control, San Diego, CA, USA, 2017, pp. 2912-2917. http://arxiv.org/abs/1710.02934
[33] K. N. Waltz, Theory of International Politics. New York, USA: McGraw-Hill, 1979.
[34] Y. K. Li and A. S. Morse, "A network game approach to international relations Ⅰ: power allocation, " in Preparation, 2018.