Evolutionary Coalitional Games for Random Access Control

Xin Luo, Hamidou Tembine

evolutionary coalitional games, coalitional CODIPAS learning, group-formation, evolutionarily stable coalitional structure

2013

​In this paper we consider a random access system where each user can be in two modes of operation, has a packet
or not and the set of users which have a packet is available to a shared medium. We propose an evolving coalitional game theory
to analyze the system outcomes. Unlike classical coalitional approaches that assume that coalitional structures are fixed
and formed with 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 is, when it is formed it is resilient by small perturbation of
strategies. We show that (i) the formation and the stability of coalitions depend mainly on the cost of making a coalition
compared to the benefit of cooperation, (ii) 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 of the
stable sets. Finally, we discuss the convergence and complexity of the proposed coalitional CODIPAS learning in access control
with different users’ activities.