A game theoretic framework for distributed computing with dynamic set of agents

被引:0
作者
Swapnil Dhamal
Walid Ben-Ameur
Tijani Chahed
Eitan Altman
Albert Sunny
Sudheer Poojary
机构
[1] Institut Polytechnique de Paris,Télécom SudParis
[2] INRIA Sophia Antipolis Méditerranée,undefined
[3] Indian Institute of Technology,undefined
[4] Palakkad,undefined
[5] Qualcomm India Pvt. Ltd.,undefined
[6] LIA,undefined
[7] Avignon University,undefined
来源
Annals of Operations Research | 2024年 / 336卷
关键词
Game theory; Stochastic game; Markov perfect equilibrium; Stackelberg game; Distributed computing; Volunteer computing;
D O I
暂无
中图分类号
学科分类号
摘要
We consider a distributed computing setting wherein a central entity seeks power from computational providers by offering a certain reward in return. The computational providers are classified into long-term stakeholders that invest a constant amount of power over time and players that can strategize on their computational investment. In this paper, we model and analyze a stochastic game in such a distributed computing setting, wherein players arrive and depart over time. While our model is formulated with a focus on volunteer computing, it equally applies to certain other distributed computing applications such as mining in blockchain. We prove that, in Markov perfect equilibrium, only players with cost parameters in a relatively low range which collectively satisfy a certain constraint in a given state, invest. We infer that players need not have knowledge about the system state and other players’ parameters, if the total power that is being received by the central entity is communicated to the players as part of the system’s protocol. If players are homogeneous and the system consists of a reasonably large number of players, we observe that the total power received by the central entity is proportional to the offered reward and does not vary significantly despite the players’ arrivals and departures, thus resulting in a robust and reliable system. We then study by way of simulations and mean field approximation, how the players’ utilities are influenced by their arrival and departure rates as well as the system parameters such as the reward’s amount and dispensing rate. We observe that the players’ expected utilities are maximized when their arrival and departure rates are such that the average number of players present in the system is typically between 1 and 2, since this leads to the system being in the condition of least competition with high probability. Further, their expected utilities increase almost linearly with the offered reward and converge to a constant value with respect to its dispensing rate. We conclude by studying a Stackelberg game, where the central entity decides the amount of reward to offer, and the computational providers decide how much power to invest based on the offered reward.
引用
收藏
页码:1871 / 1904
页数:33
相关论文
共 50 条
  • [41] A Game Theoretic Framework for DG Optimal Contract Pricing
    Mobarakeh, Ashkan Sadeghi
    Rajabi-Ghahnavieh, Abbas
    Zahedian, Aydin
    [J]. 2013 4TH IEEE/PES INNOVATIVE SMART GRID TECHNOLOGIES EUROPE (ISGT EUROPE), 2013,
  • [42] A Game Theoretic Framework for Multi Domain Cyber Deception
    Hemida, Ahmed
    Asghar, Ahmed Bilal
    Kamhoua, Charles
    Kleinberg, Jon
    [J]. 9TH IEEE EUROPEAN SYMPOSIUM ON SECURITY AND PRIVACY WORKSHOPS, EUROS&PW 2024, 2024, : 443 - 447
  • [43] Game Theoretic Defense Framework Against Sybil Attacks
    Bhupender Kumar
    Bubu Bhuyan
    [J]. SN Computer Science, 5 (7)
  • [44] A Hierarchical Game Theoretic Framework for Cognitive Radio Networks
    Xiao, Yong
    Bi, Guoan
    Niyato, Dusit
    DaSilva, Luiz A.
    [J]. IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, 2012, 30 (10) : 2053 - 2069
  • [45] Community detection in networks: a game-theoretic framework
    Yan Chen
    Xuanyu Cao
    K. J. Ray Liu
    [J]. EURASIP Journal on Advances in Signal Processing, 2019
  • [46] Monetary Consequences of Fiscal Stress in a Game Theoretic Framework
    Dat Thanh Nguyen
    Viet Anh Hoang
    [J]. JOURNAL OF CENTRAL BANKING THEORY AND PRACTICE, 2020, 9 : 125 - 164
  • [47] A Game Theoretic Modeling Framework for Decentralized Transmission Planning
    Fan, Ying
    Papadaskalopoulos, Dimitrios
    Strbac, Goran
    [J]. 2016 POWER SYSTEMS COMPUTATION CONFERENCE (PSCC), 2016,
  • [48] Community detection in networks: a game-theoretic framework
    Chen, Yan
    Cao, Xuanyu
    Liu, K. J. Ray
    [J]. EURASIP JOURNAL ON ADVANCES IN SIGNAL PROCESSING, 2019, 2019 (01)
  • [49] Knowledge Sharing Framework: a Game-Theoretic Approach
    Rami S. Al-Gharaibeh
    Mostafa Z. Ali
    [J]. Journal of the Knowledge Economy, 2022, 13 : 332 - 366
  • [50] Toward integrity assurance of outsourced computing - a game theoretic perspective
    Wang, Yongzhi
    Wei, Jinpeng
    Ren, Shaolei
    Shen, Yulong
    [J]. FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE, 2016, 55 : 87 - 100