A formal model based on Game Theory for the analysis of cooperation in distributed service discovery

New systems can be designed, developed, and managed as societies of agents that interact with each other by offering and providing services. These systems can be viewed as complex networks where nodes are bounded rational agents. In order to deal with complex goals, they require cooperation of the other agents to be able to locate the required services. The aim of this paper is formally and empirically analyze under which circumstances cooperation emerges in decentralized search of services. We propose a repeated game model that formalizes the interactions among agents in a search process where agents are free to choose between cooperate or not in the process. Agents make decisions based on the cost of their actions and the expected reward if they participate forwarding queries in a search process that ends successfully. We propose a strategy that is based on random-walks, and we study under what conditions the strategy is a Nash equilibrium. We performed several experiments in order to evaluate the model and the strategy and to analyze which network structures are more appropriate to promote cooperation.