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\).