Abstract
The optimal decision of an autonomous agent at a given situation depends on the other agents' decisions at the same time. Rational agents, assumed as the utility maximizers, should find a stable equilibrium before acting. Since autonomous agents may have the ability of communication, the agents can use a negotiation mechanism to find or create equilibrium. This thesis addresses how to construct the negotiation mechanism under the assumption of game theory. We propose a negotiation mechanism that allows an agent to convince or persuade other agents for a commitment or an alternation of a strategy. The negotiation mechanism can deal with difficult games and reach optimal payoffs with the underlying assumptions of rationality. We also prove that the negotiation mechanism is fair, and the negotiated result must be stable equilibrium. In the thesis we extend the game theory and define the trusted third party mediated game as a way of multi-agent coordination. 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 thesis, 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: guarantee and compensation for agents to use in negotiation. Depositing guarantee at the trusted third party can ensure the agents to keep their commitments, while exchanging compensation can allow finding a fair and compromised solution for all agents. The mechanism can deal with all the game situations and find an acceptable equilibrium that gives optimal payoffs. We show first 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. Uncertainty is unavoidable in real world problem and may cause risk for the agents. We also extend the mechanism to deal with the uncertain game and find that the risk can be control by agents that have different preferences of risk. We defined three types of preference of risk, i.e., risk-averse, risk-neutral and risk-seeking. The agents negotiate to maximize the expect payoffs while controlling the risk according to its own preference of risk. With this extension, we can conclude that the trusted third party is not limited to deal with traditional game. The trusted third party can also help the agents to coordinate in the uncertain situations.