Game theoretic reasoning in multi-agent coordination by negotiation with a trusted third party

In multi-agent coordination, one would normally like to find a satisfactory solution that is stable, fair and optimal to all agents. According to traditional game theory, Prisoner's dilemma, no or more than one Nash equilibrium games are situations that are difficult to find such a satisfactory solution. In human society, it often involves a trusted third party in the negotiation process among agents to ensure the cooperation and commitment of agents. In this paper, we describe how the trusted third party can be involved in the negotiation of multi-agent coordination to deal with many difficult game situations. We introduce two communication actions into the traditional game-theoretical reasoning: asking guarantee and offering compensation for agents to use in negotiation. Asking guarantee from agents and depositing it at the trusted third party can ensure the agents to keep their commitments, while offering compensation can allow finding a fair and compromised solution for all agents. We show how the negotiation communication protocols can be proceeded using these two communication actions to reach a compromised and stable agreement in all different game situations.