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

Swapnil Dhamal (), Walid Ben-Ameur (), Tijani Chahed (), Eitan Altman (), Albert Sunny () and Sudheer Poojary ()
Additional contact information
Swapnil Dhamal: Institut Polytechnique de Paris
Walid Ben-Ameur: Institut Polytechnique de Paris
Tijani Chahed: Institut Polytechnique de Paris
Eitan Altman: INRIA Sophia Antipolis Méditerranée
Albert Sunny: Indian Institute of Technology, Palakkad
Sudheer Poojary: Qualcomm India Pvt. Ltd.

Annals of Operations Research, 2024, vol. 336, issue 3, No 21, 1904 pages

Abstract: Abstract 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.

Keywords: Game theory; Stochastic game; Markov perfect equilibrium; Stackelberg game; Distributed computing; Volunteer computing (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-023-05231-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:336:y:2024:i:3:d:10.1007_s10479-023-05231-7

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-023-05231-7

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().