The rising integration of pocket computing devices in our daily life duties has taken the attention of researchers from different scientific backgrounds. Today's amount of software applications bringing together advanced mobile services and literature of Artificial Intelligence (AI) is quite remarkable and worth investigating. In our research, software agents of BarterCell can operate in wireless networks on behalf of nomadic users, cooperate to resolve complex tasks and negotiate to reach mutually beneficial bartering agreements. In this paper, we introduce BarterCell that is an agent-based service application for users of pocket computing devices. We introduce new negotiation algorithms dedicated to bartering services in specific. We examine our approach in a scenario wherein it is essential for a multi-agent system to establish a chain of mutually attracted agents seeking to fulfill different bartering desires. And, we demonstrate and analyze the obtained results.