Evolutionary coalitional games for random access control

Xin Luo, Hamidou Tembine

Research output: Contribution to journalArticlepeer-review


This paper considers a random access system with several users and one shared medium. Each user has its own queue (of packets) which can be empty or not. We propose an evolving coalitional game between the users and analyze the system outcomes. Unlike classical coalitional approaches that assume that coalitional structures are fixed and formed cost-free, we explain how coalitions can be formed in a fully distributed manner using evolutionary dynamics and coalitional combined fully distributed payoff and strategy (CODIPAS) learning. We introduce the concept of evolutionarily stable coalitional structure (ESCS), which, when it is formed, is resilient to small perturbation of strategies. We show that (1) the formation and the stability of coalitions depend mainly on the cost of making a coalition compared to the benefit of cooperation, (2) the grand coalition can be unstable and a localized coalitional structure is formed as an evolutionarily stable coalitional structure. When the core is empty, the coalitional CODIPAS scheme selects one element of the stable set. Finally, we discuss the convergence and complexity of the proposed coalitional learning in access control with different users’ activities. Some extensions to cognitive medium access control with queue management are provided.

Original languageEnglish (US)
Pages (from-to)1-34
Number of pages34
JournalAnnals of Operations Research
StateAccepted/In press - Apr 23 2016


  • Coalitional structure
  • Distributed learning
  • Evolutionary games

ASJC Scopus subject areas

  • General Decision Sciences
  • Management Science and Operations Research


Dive into the research topics of 'Evolutionary coalitional games for random access control'. Together they form a unique fingerprint.

Cite this