A random tree search algorithm for Nash equilibrium in capacitated selfish replication games

Seyed Nematollah Ahmadyan, Seyed Rasoul Etesami, H. Vincent Poor

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

In this paper, we consider a resource allocation game with binary preferences and limited capacities over large scale networks and propose a novel randomized algorithm for searching its pure-strategy Nash equilibrium points. It is known that such games always admit a pure-strategy Nash equilibrium and benefit from having a low price of anarchy. However, the best known theoretical results only provide a quasi-polynomial constant approximation algorithm of the equilibrium points over general networks. Here, we search the state space of the resource allocation game for its equilibrium points. We use a random tree based search method to minimize a proper score function and direct the search toward the pure-strategy Nash equilibrium points of the system. We demonstrate efficiency of our algorithm through some empirical results.

Original languageEnglish (US)
Title of host publication2016 IEEE 55th Conference on Decision and Control, CDC 2016
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages4439-4444
Number of pages6
ISBN (Electronic)9781509018376
DOIs
StatePublished - Dec 27 2016
Event55th IEEE Conference on Decision and Control, CDC 2016 - Las Vegas, United States
Duration: Dec 12 2016Dec 14 2016

Publication series

Name2016 IEEE 55th Conference on Decision and Control, CDC 2016

Other

Other55th IEEE Conference on Decision and Control, CDC 2016
CountryUnited States
CityLas Vegas
Period12/12/1612/14/16

All Science Journal Classification (ASJC) codes

  • Artificial Intelligence
  • Decision Sciences (miscellaneous)
  • Control and Optimization

Fingerprint Dive into the research topics of 'A random tree search algorithm for Nash equilibrium in capacitated selfish replication games'. Together they form a unique fingerprint.

  • Cite this

    Ahmadyan, S. N., Etesami, S. R., & Poor, H. V. (2016). A random tree search algorithm for Nash equilibrium in capacitated selfish replication games. In 2016 IEEE 55th Conference on Decision and Control, CDC 2016 (pp. 4439-4444). [7798943] (2016 IEEE 55th Conference on Decision and Control, CDC 2016). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/CDC.2016.7798943