Instability and Efficiency of Non-cooperative Games

It is well known that a non-cooperative game may have multiple equilibria. In this paper we consider the efficiency of games, measured by the ratio between the aggregate payoff over all Nash equilibria and that over all admissible controls. Such efficiency operator is typically unstable with respect to small perturbation of the game. This seemingly bad property can actually be a good news in practice: it is possible that a small change of the game mechanism may improve the efficiency of the game dramatically. We shall introduce a game mediator with limited resources and investigate two mechanism designs aiming to improve the efficiency. Moreover, we compare the mediator's capability of efficiency improvement when she has access to full information or only partial information. When the mechanisms contain only rewards, the mediator has the same power in the two cases. However, when the mediator can use punishments as well, in general she may have a larger power to improve the efficiency in the full information case than in the partial information case.