Coalition Formation with Uncertain Heterogeneous Information

Abstract

Coalition formation methods allow agents to join together and are thus necessary in cases where tasks can only be performed cooperatively by groups. This is the case in the Request For Proposal (RFP) domain, where some requester business agent issues an RFP - a complex task comprised of sub-tasks - and several service provider agents need to join together to address this RFP. In such environments the value of the RFP may be common knowledge, however the costs that an agent incurs for performing a specific sub-task are unknown to other agents. Additionally, time for addressing RFPs is limited. These constraints make it hard to apply traditional coalition formation mechanisms, since those assume complete information, and time constraints are of lesser significance there. To address this problem, we have developed a protocol that enables agents to negotiate and form coalitions, and provide them with simple heuristics for choosing coalition partners. The protocol and the heuristics allow the agents to form coalitions in the face of time constraints and incomplete information. The overall payoff of agents using our heuristics is very close to an experimentally measured optimal value, as our extensive experimental evaluation shows.