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 counterproductive 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]
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]
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 IdeaBy the power allocation game or PAG is meant a distributed resource allocation game between
Each set of country strategies
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
In playing the PAG, countries select individual strategies in accordance with certain weak and/or strong preferences. A sufficient set of conditions for country
1) For all
2) For all
Weak preference by country
Meanwhile, a sufficient condition for country
Finally, a sufficient condition for country
A country
1) Country
Pairwise utility
If
If
2) Country
3) Once country
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
$ 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
$ 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} $ 
Let country
$ f^{*}_{i}(U) $ 
Since country
1)
2)
3)
4)
Let the two environments be with the same set of countries where one difference between the environments is that for country
The parameters of the first environment in Fig. 1(a)^{1} is:
Download:


Fig. 1 A Paradox for country 3. 
^{1}Red edges in Fig. 1 denote adversary relations and green edges denote friend relations.
1) Set of countries:
2) Their power:
3) Their relations are:
The parameters of the second environment in Fig. 1(b) is:
1) Set of countries:
2) Their power:
3) Their relations are:
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 RESULTSThis 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 selfsurvival is fulfilled, in its attainment of its optimal welfare.
Let two PAGs be
$ \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
$ \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
Therefore, in any equilibrium
$ \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,
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.
Given two games
Given a random environment, let the optimal welfare country
Let an alternative environment be
Then,
$ f^{*}_{i}(U) > \overline{f}^{*}_{i}(\overline{U}) $ 
must hold because for any of
Then having more friends does not decrease
Therefore, in order for the stated paradox to occur, there must exist another country
For country
Since
$ p_i + p_j \leq \displaystyle\sum\limits_{k \in {n}  \{i, j\}}p_i, $ 
there must hold that in any equilibrium
$ 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
To country
Since
Therefore, having more friends than before decreases country
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.
For country
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
$ \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
To country
Since
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^*)} $ 
In
$ \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
$ \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
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.
$ 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 = (n1)\text{inf}\{t_{ii}^{\mathcal{F}}(0): i \in {n}\} + \text{inf}\{t_{ii}^{\mathcal{F}}(1): i \in{n}\}. $ 
Obviously, there exists no lower value for
Now rank all countries' pairwise utilities from not having survived itself,
$ \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,
$ \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}}(0): i \in {n}\}. $ 
This then gives the upper bound
$ 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\} . $ 
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."
[1]  Y. K. Li and A. S. Morse, "Game of power allocation on networks, " Proc. American Control Conf., Seattle, WA, USA, 2017, pp. 52315236. http://arxiv.org/abs/1610.00787 
[2]  D. Braess, "Über ein paradoxon aus der verkehrsplanung, " Unternehmensforschung, vol. 12, no. 1, pp. 258268, Dec. 1968. https://link.springer.com/article/10.1007/BF01918335 
[3]  E. Koutsoupias and C. Papadimitriou, "Worstcase equilibria, " Comput. Sci. Rev., vol. 3, no. 2, pp. 6569, May 2009. 
[4]  H. Lin, T. Roughgarden, and É. Tardos, "A stronger bound on braessś paradox, " in Proc. 15th Annu. ACMSIAM Symp. Discrete Algorithms, New Orleans, Louisiana, USA, 2004, pp. 340341. 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. 977991, May 2006. 
[6]  T. Roughgarden and É. Tardos, "How bad is selfish routing?, " J. ACM (JACM), vol. 49, no. 2, pp. 236259, 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. 16671686, 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. 571584, 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. 215224, 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. 1826, 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. 183199, 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. 472481. http://www.ams.org/mathscinetgetitem?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. 257278, 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. 155, 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. 98115, 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. 4555, 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. 254263, 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 GameTheoretic 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. 536585, 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. 277303, Sep. 2016. http://link.springer.com/article/10.1007/s1323501501604 
[27]  H. Tembine, Q. Y. Zhu, and T. Başar, "Risksensitive meanfield games, " IEEE Trans. Autom. Control, vol. 59, no. 4, pp. 835850, Apr. 2014. http://ieeexplore.ieee.org/document/6656891/ 
[28]  K. C. Cao, Y. Q. Chen, and D. Stuart, "A fractional micromacro model for crowds of pedestrians based on fractional mean field games, " IEEE/CAA J. of Autom. Sinica, vol. 3, no. 3, pp. 261270, Jul. 2016. http://www.en.cnki.com.cn/Article_en/CJFDTotalZDHB201603006.htm 
[29]  S. Li, M. C. Zhou, X. Luo, and Z. H. You, "Distributed winnertakeall in dynamic networks, " IEEE Trans. Autom. Control, vol. 62, no. 2, pp. 577589, Feb. 2017. http://www.researchgate.net/publication/303872576_Distributed_Winnertakeall_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. 301310, 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. 861899. 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. 29122917. http://arxiv.org/abs/1710.02934 
[33]  K. N. Waltz, Theory of International Politics. New York, USA: McGrawHill, 1979. 
[34]  Y. K. Li and A. S. Morse, "A network game approach to international relations Ⅰ: power allocation, " in Preparation, 2018. 