Forming Coalitions in the Face of Uncertain Rewards

Abstract

When agents are in an environment where they can interact with each other, groups of agents may agree to work together for the benefit of all the members of the group. Finding these coalitions of agents and determining how the joint reward should be divided among them is a difficult problem. This problem is aggravated when the agents have different estimates of the value that the coalition will obtain. A "two agent auction" mechanism is suggested to complement an existing coalition formation algorithm for solving this problem. 1. The Problem Given a set of agents with different abilities and different information, there may be many opportunities for cooperation among the agents that will benefit all. Even more likely is the chance that a coalition can form, a subset of the agents working together, benefiting each agent in the group perhaps at the expense of the community as a whole. An agent following the economic principle of rationality will attempt to form a coalition which will max...