A journal of IEEE and CAA , publishes high-quality papers in English on original theoretical/experimental research and development in all areas of automation
Volume 5 Issue 4
Jul.  2018

IEEE/CAA Journal of Automatica Sinica

  • JCR Impact Factor: 6.171, Top 11% (SCI Q1)
    CiteScore: 11.2, Top 5% (Q1)
    Google Scholar h5-index: 51, TOP 8
Turn off MathJax
Article Contents
Yuke Li and A. Stephen Morse, "The Power Allocation Game on A Network: A Paradox," IEEE/CAA J. Autom. Sinica, vol. 5, no. 4, pp. 771-776, July 2018. doi: 10.1109/JAS.2018.7511129
Citation: Yuke Li and A. Stephen Morse, "The Power Allocation Game on A Network: A Paradox," IEEE/CAA J. Autom. Sinica, vol. 5, no. 4, pp. 771-776, July 2018. doi: 10.1109/JAS.2018.7511129

The Power Allocation Game on A Network: A Paradox

doi: 10.1109/JAS.2018.7511129

the National Science Foundation 1607101.00

US Air Force FA9550-16-1-0290

More Information
  • 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.


  • loading
  • [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
    D. Braess, "Über ein paradoxon aus der verkehrsplanung, " Unternehmensforschung, vol. 12, no. 1, pp. 258-268, Dec. 1968. doi: 10.1007/BF01918335
    E. Koutsoupias and C. Papadimitriou, "Worst-case equilibria, " Comput. Sci. Rev., vol. 3, no. 2, pp. 65-69, May 2009.
    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
    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.
    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
    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
    T. Roughgarden, Selfish Routing and the Price of Anarchy. Cambridge, MA, USA: MIT Press, 2005.
    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
    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
    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
    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
    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
    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
    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
    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
    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
    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
    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
    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
    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
    Y. K. Li and A. S. Morse, "Game of countriesṕower allocation on networks: balancing equilibrium, " Proc. American Control Conf., Forthcoming, 2018.
    T. Alpcan and T. Başar, Network Security: A Decision and Game-Theoretic Approach. Cambridge, UK: Cambridge University Press, 2010.
    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
    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
    D. Bauso, H. Tembine, and T. Başar, "Robust mean field games, " Dyn. Games Appl., vol. 6, no. 3, pp. 277-303, Sep. 2016. doi: 10.1007/s13235-015-0160-4
    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/
    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
    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
    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
    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
    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
    K. N. Waltz, Theory of International Politics. New York, USA: McGraw-Hill, 1979.
    Y. K. Li and A. S. Morse, "A network game approach to international relations Ⅰ: power allocation, " in Preparation, 2018.


    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索


    Article Metrics

    Article views (1153) PDF downloads(72) Cited by()


    DownLoad:  Full-Size Img  PowerPoint