6 Coalitions

Question 1

Coalition Formation

Answer 1

Coalitions are (temporary) collections of individuals working together for the purpose of achieving a task. Coalition formation is the process where by an agent decides to cooperate with other agents, because

• the task cannot be performed by a single agent
• the task can be performed more efficiently by several agents working together

Question 2

External coalition formation

Answer 2

• By imposition: an external agency makes decisions
• Agents advertise skills (capabilities)and prices (cost)
• Requestor defines properties of coalition to the external agency
• An entity external to the MAS computes the optimal coalition

Question 3

Internal coalition formation

Answer 3

• By self-organization: coalitions are established by group interactions
• Multi-lateral negotiation of tasks and outcomes
• Identification of tasks to be solved

Question 4

Coalition formation activities

Answer 4

• Coalition value calculation
  Calculate the benefit of each coalition for each task
• Coalition structure generation
  Decide the coalitions to form, maximizing the coalition value
• Payoff distribution
  Deciding how to distribute the payoff between coalition members (equally, outputs, role)

Question 5

Problems

Answer 5

• Decentralised mechanism, but…
- It requiresmany (large) messages between the agents (an agent may need to contact another agent several times)

• The value of the same coalition may be calculated by different agents
• Large space of memory needed to store all possible coalitions of an agent
• No guarantees on the quality of the distribution. Tasks could be left unassigned!