|M.Sc Student||Rozenfeld Olga|
|Subject||Strong Equilibrium in Congestion Games|
|Department||Department of Computer Science||Supervisor||Professor Moshe Tennenholtz|
|Full Thesis text|
In many multi-agent systems it makes little sense to assume that agents will stick to their parts when provided with suggested protocol, if a deviation can increase their payoffs. While for any multi-agent encounter, represented as a strategic form game, there always exists a strategy profile for which unilateral deviations are not beneficial, requirements regarding joint deviations of multiple players are rarely satisfied. In order to tackle this issue we consider the use of routing mediators, extending upon previous work in game theory and AI. A mediator is a reliable entity that can interact with the players, and potentially act on behalf of the players that give him a permission to do so. However, a mediator can not enforce behavior - any agent is free to participate in the game without the help of the mediator. This notion is highly natural; in many systems there is some form of reliable party that can be used as a mediator. In particular, brokers in financial markets, bidding club organizers in auctions, as well as routers in communication networks, can be viewed as mediators. Notice that we assume that the multi-agent interaction (formalized as a game) is given, and all the mediator can do is to perform actions on behalf of the agents that explicitly allow it to do so. The mediator's behavior on behalf of the agents that give it the right of play is pre-specified, and is conditioned on the information available to the mediator on all agents' actions. Our study concentrates on the use of routing mediators in order to reach correlated strong equilibrium - a multi-agent behavior which is stable against deviations by coalitions. We study the relationships between the power of different routing mediators in establishing correlated strong equilibrium. Our main result shows a natural class of routing mediators that allow implementing fair and efficient outcomes as a correlated super-strong equilibrium in a very wide class of games. We then apply this work to the widely studied setting of congestion games. We study the existence of strong and correlated strong equilibria in congestion games without a mediator, and then explore the extent to which routing mediators can aid in attaining these solutions.