5 - Applications to Games

Summary

BARGAINING GAMES

Bargaining Games with Quadratic Boundaries

In this section we continue the analysis and comparison of the computational complexity of functions. Recall that in some cases, for example, the case of two-person zero-sum games analyzed in Chapter 3, Section 3.1, Leontief's criteria give unambiguous comparisons of solution functions. The comparison of diagonal games and 3 × 3 matrix games of Chapter 3, Section 3.3 cannot be made by a direct application of the Leontief criteria. In that chapter an added restriction, the symmetrical computation restriction, is imposed on the networks that represent the computation. That restriction can be interpreted as a simplicity requirement on the structure of the network. With this restriction we are able to apply Leontief's criteria to obtain unambiguous comparisons of the solution functions for the two classes of games.

However, it remains the case that when the number of variables is small, without imposing additional restrictions, the methods of Chapter 3 can be used to distinguish between the computational complexities of members of only a small class of functions.

In this chapter we extend the applicability of Leontief's criteria by introducing another type of restriction on the networks that represent computations. As in the preceding chapters, we do this in the setting of examples. We seek to compare the complexities of two different solutions in a class of two-agent bargaining problems. Specifically, we compare the Nash solution and the Kalai – Smorodinsky solution. Direct application of Leontief's criteria to the payoff functions for the Nash and Kalai–Smorodinsky solutions is not decisive.