Fullway handout

Finitely repeated games
We ‘repeat’ a normal form game \(T\) times. Strategies need to be defined to take in to account the entire history of the game.
What did we do?
 We played an iterated prisoner’s dilemma tournament.
What do I need to be able to do?
 Define a repeated game.
 State and prove the theorem of a sequence of stage Nash profiles.
 Draw possibly utility outcomes.
 Obtain subgame perfect Nash equilibria that are not a sequence of state Nash equilibria.

Infinitely repeated games
We now ‘repeat’ a normal form game an infinite amount of times. To deal with this we use discounting.
What did we do?
 We played an infinite iterated prisoner’s dilemma tournament by introducing a probability of the game carrying on.
What do I need to be able to do?
 Calculate expected utilities with discounting.
 Prove particular instances where a given strategy is better than another.
 Prove the Folk theorem.

Population Games and Evolutionary stable strategies
We move on to something different and consider populations and how a particular strategy evolves in a population.
What did we do?
 We played a brief game with cards in class.
What do I need to be able to do?
 Define a population game.
 State and prove the theorem for necessity of stability.
 Define a post entry population \(\chi_{\epsilon}\) and an ESS.
 Obtain ESS in a game against the field.

Nash equilibrium and Evolutionary stable strategies
We consider a particular type of game against the field: member of the population are randomly matched and play a normal form game.
What did we do?
 Nothing really.
What do I need to be able to do?
 Define a pairwise contest game.
 Find ESS in a pairwise contest game from first principles.
 State prove and use the theorem relating an ESS to a Nash equilibrium of a normal form game.

Random events and incomplete information
Here we look at extensive form games with random events.
What did we do?
 3 volunteers played a version of matching pennies with some randomness involved (someone won a melon)
What do I need to be able to do?
 Obtain the normal form representation of a game with incomplete information.
 Describe basic utility theory.
 Solve the principal agent game.

Stochastic games
Games where strategies not only define the utilities but the next game.
What did we do?
 We played a modified version of the Prisoner’s dilemma in the form of a stochastic game (this was a 4 team round robin tournament)
What do I need to be able to do?
 Define a stochastic/Markov game, a Markov strategy.
 State the requirement for Nash equilibrium.
 Obtain Nash equilibrium for stochastic games.

Matching games
We look at the stable marriage problem and the Gale Shapley algorithm.
What did we do?
 We matched 3 volunteers to 3 of my toys (Donatello, Zoe and my Tech Deck).
What do I need to be able to do?
 Define a matching game.
 State and apply the GaleShapley algorithm.
 State and prove the theorem guaranteeing a unique matching as output of the Gale Shapley algorithm.
 State and prove the theorem of reviewer sub optimality.

Cooperative games
Sharing resources when considering contribution of coalitions.
What did we do?
 We played basketball (kind of).
What do I need to be able to do?
 Define a characteristic value game.
 Define monotone and superadditive games.
 Define Efficiency, Null player, Symmetry and Additivity (see exercises  you could be asked to prove that the Shapley value has these properties).
 Define and be able to calculate the Shapley value.

Routing games
Games that can be used to model behaviour in system affected by congestion.
What did we do?
 Nothing fun at all…
What do I need to be able to do?
 Define a routing game, set of paths and feasible paths.
 Define and obtain (from first principles) Optimal flows.
 Define and obtain (from first principles) Nash flows.
 Define the potential function.
 Define marginal costs.
 State and use the theorem connecting the Nash flow to the optimal flow.
 State and use the theorem connecting optimal flows to Nash flows.