One focus of multi-agent systems research is the notion that complex outcomes or behaviours may be arrived at through the interaction of agents. However, it is still an open question as to how agents in a complex system form coalitions or modules, and how these coalitions self-organize into hierarchies. In this paper, we begin to address this question by investigating agent collaboration in the context of a high-level pattern recognition task. We propose a novel market-based communication protocol, which governs the aggregate behaviour of individual agents and subsequent emergent properties of the system. Based on the Contract Net Protocol, individual agents bid to join coalitions (or solutions to a given problem). An important contribution of this study is the analysis of the role heterogeneous agents play in the formation of coalitions. Using a simple model, we show that by promoting diversity within the agent population it is possible to avoid deadlock or "tie" conditions, which otherwise have to be solved arbitrarily by the deadlocked agents.