Proceedings of the AAAI Conference on Artificial Intelligence, 21
Providing agents with strategies that will be robust against deviations by coalitions is central to the design of multi-agent agents. However, such strategies, captured by the notion of strong equilibrium, rarely exist. This paper suggests the use of mediators in order to enrich the set of situations where we can obtain stability against deviations by coalitions. A mediator is a reliable entity, which can ask the agents for the right to play on their behalf, and is guaranteed to behave in a pre-specified way based on messages received from the agents. However, a mediator can not enforce behavior; that is, agents can play in the game directly without the mediator's help. We prove some general results about mediators, and concentrate on the notion of strong mediated equilibrium; we show that desired behaviors, which are stable against deviations by coalitions, can be obtained using mediators in a rich class of settings.