Agent cooperation

An agent is an intelligent entity, situated in an environment that can be perceived, with goals, and a list of available actions. An agent acts autonomously to satisfy his goals and, more importantly, it’s social. In other words, it does not act independently, but rather collaborate with other agents in the environment. Hence, agent cooperation is crucial to successfully achieve tasks.

Let’s see an example for agent cooperation: the Prisoner’s Dilemma.

This is a very famous problem where 2 people committed a crime, but there is no evidence to convict them for it, only for a minor offence (1 year prison). However, if one person confesses and the other does not, the person who confessed walks free and the other gets 4 years in prison. If both confess, both get 3 years in prison. The agents have no way of communicating or making any binding agreements. We can represent the possible choices of the prisoners as a matrix:

Where the pair $(x, y)$ at the intersection of row $i$ and column $j$ means that the row player gets $x$ and the column player gets $y$ years.

Obviously, the objective of the player is maximizing the number they get. We can get a rational outcome:

As a result, they would both confess and get 3 years in prison.

But they could have walked off with one year. So why do they not cooperate? This is a non-cooperative game, thus no binding agreements can be made between the players. If this were possible and agents can benefit from cooperating, we are looking at a cooperative game. Coalition formation is studied in cooperative game theory.

Organization in Multi-agent Systems

Game Theory studies interactions between agents in situations known as games.

• In Non-Cooperative games, players cannot make binding agreements.
• In Cooperative games, scenarios are modelled such that:
  • binding agreements are possible
  • agents can benefit by cooperating

There are many types of organizations in multi-agent systems, including for example markets and hierarchies:

However, we will focus on coalitions, which are essentially groups of agents cooperating. They have a tendency to be short-lived and goal-directed. There is also no coordination between members of different coalitions, with each coalition having a flat organizational structure.

Coalition Game Theory

Coalition Formation is studied in a field of Game theory, called Cooperative Game Theory.