New systems can be designed, developed, and managed as societies of agents that interact with each other by o↵ering and providing services. These systems can be viewed as complex networks where nodes are bounded rational agents. In order to deal with complex goals, agents must cooperate with other agents to be able to locate the required services. The aim of this paper is to formally and empirically analyze under what circumstances cooperation emerges in decentralized search for services. We propose a repeated game model that formalizes the interactions among agents in a search process where each agent has the freedom to choose whether or not to cooperate with other agents. Agents make decisions based on the cost of their actions and the expected reward if they participate by 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 the most appropriate for promoting cooperation.