Portal de Periódicos da CAPES

Network formation games with teams

2016; American Institute of Mathematical Sciences; Volume: 3; Issue: 4 Linguagem: Inglês

10.3934/jdg.2016016

2164-6074

Vikas Vikram Singh, Giovanni Neglia, Konstantin Avrachenkov,

Game Theory and Voting Systems

Network formation games have been proposed as a tool toexplain the topologicalcharacteristics of existing networks. They assume that eachnode is an autonomous decision-maker, ignoring that in manycases different nodes are under the control of the sameauthority (e.g. an Autonomous System) and then they operateas a team.In this paper we introduce the concept of network formationgames for teams of nodes and show howvery different network structures can arise also for somesimple games studied in the literature.Beside extending the usual definition of pairwise stablenetworks to this new setting,we define a more general concept of stability towarddeviations from a specific set $\mathcal{C}$ of teams' coalitions($\mathcal{C}$-stability).We study then a trembling-hand dynamics, where at each timea coalition of teams can create or sever links in order toreduce its cost,but it can also take wrong decisions with some smallprobability. We show that this stochastic dynamics selects $\mathcal{C}$-stable networks or networks from closed cycles in the long runas the error probability vanishes.