Homework 5  Matching games, cooperative games and routing games

Obtain stable suitor optimal and reviewer optimal matchings for the matching games shown.

Game 1:

Game 2:

Game 3:

Game 4:


Consider a matching game where all reviewers have the same preference list. Prove that there is a single stable matching.

For the following cooperative games:
 Verify if the game is monotonic.
 Verify if the game is super additive.
 Obtain the Shapley value.

Prove that the Shapley value has the following properties:
 Efficiency
 Null player
 Symmetry
 Additivity
Note that this does not prove that the Shapley value is the only vector that has those properties (it in fact is though).

Calculate the Nash flow and the optimal flow for the following routing game:

For a routing game the ‘Price of Anarchy’ is defined as:
For the game shown (a generalisation of “Pigou’s example”) obtain the PoA as a function of \(\alpha\).