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

IEEE/CAA Journal of Automatica Sinica

  • JCR Impact Factor: 15.3, Top 1 (SCI Q1)
    CiteScore: 23.5, Top 2% (Q1)
    Google Scholar h5-index: 77， TOP 5
Turn off MathJax
Article Contents
Article Navigation >  IEEE/CAA Journal of Automatica Sinica  > 2018  >  5(4): 771-776
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
shu

The Power Allocation Game on A Network: A Paradox

doi: 10.1109/JAS.2018.7511129

  • Department of Political Science, A. S. Morse is with the Department of Electrical Engineering, Yale University, New Haven, CT, USA

Funds:

the National Science Foundation 1607101.00

US Air Force FA9550-16-1-0290

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

     

    • FullText(HTML)
  • loading
    • References(34)
  • [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. doi: 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. doi: 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.
    • Related Articles
    • Supplements(0)

Catalog

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

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

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

    Figures(1)

    Get Citation
    PDF
    XML

    Article Metrics

    Article views (1306) PDF downloads(80) Cited by()

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return