Outline for a course on Game Theory.

 

 

Instructor: Mike O’Neill, CMC Math department.

 

References: 1. Fun and Games by Ken Binmore denoted by [B].

                    2. UCLA course notes by Tom Ferguson denoted by [F].

                                                                                                            

1.    History and background. Applications of game theory to economics, political  

      Science, biology and number theory. ([B] and some additional sources)

 

Definitions and vocabulary. Games in extensive form, plays, game trees, information sets, strategies, chance moves, payoffs. ([B], [F])

 

Example : Game of Pure Strategy (GOPS). The above notions are demonstrated using this simple card game

(1)

           

       2.  Two person zero-sum games of complete information.

Examples: Tic-tac-toe.   NIM.

Backward induction, Zermelo’s Algorithm.  [B]

 

NIM sum theorem. [F]

 

(1)

     

  1. Hex, Chess, Zermelo’s theorem. Corollary: Chess has a value (as does any 0-sum                 

      comp. inf. game.)   Saddle points. Nash equilibria.

      Sub game perfect equilibria [B]

 

      Pure Strategy equilibria: Cournot Competition, Hotelling Competition, Majority

Voting.

 

 

         (2)

 

    4.  Critiques of backward induction and sub-game perfect equilibria.

 

    N-person games, equilibrium n-tuples, Existence theorem for

    equilibrium n- tuples in finite games of complete information. This is

    another inductive proof.   Observe the difference between this theorem and   

    Nash’s theorem.

 

    Non-existence of pure strategy equilibria. Matching Pennies.

     Inspection game.

 

    Team games, multiple equilibria, [B].

 

(2)

 

  1. Chapter 2 from [B].

Probability review. Random variable, conditional probability, expectation.

 

Lotteries, Compound Lotteries.

Game values.

 

Analysis:

An extensive form for “Duel”.

A simplified form of Parcheesi.

 

 

(2)

 

  1. Utility. [O] Chapter 6.

                     Chapter 3 of [B] is required reading before this class.

 

                            Definitions: ordinal utility, preference relations, utility axioms

                       

                            Theorems: equivalent lottery theorem.

                                 Existence of a utility function for a given preference relation.

                                                        

                          Why do we need to be clear about the notion of utility?

 

             From [B], Russian roulette, ineffectiveness of Zermelo’s algorithm in games of 

                 incomplete information. St. Petersburg Paradox.

 

        Risk aversion, Utility scales and temperature scales, Allais’ Paradox, Bayesian

          rationality. [B]

 

       

           (2)

 

 

  1. (Chapter 4 in [B] ])

Payoff functions, Bi-matrix games, Nash equilibria in terms of payoff functions.

 

A strategic form for Duel.

A strategic form for Russian roulette.

 

Successive deletion of dominated strategies.

Common Knowledge and problems with successive deletion.

 

Examples: Prisoner’s dilemma and 2nd Price Auctions

                  Iterated deletion in the Cournot Model.

 

Review of Matrix algebra, closing with a proof of the

Separating hyper plane theorem.

 

            

  

             (2)

 

  1. (Chapter 5 in [B] )

      

          

            Convexity, supporting lines. Concave, convex and affine functions.

 

            Bargaining: binding agreements, cooperative pay off regions, free disposal.

                                Bargaining set, Pareto efficiency (optimality). Nash bargaining

                                solutions.

 

                         Finding Nash bargaining solutions. The Nash axioms.

                          The Nash bargaining theorem.

 

                         

                          Example:“Dividing the dollar”. Risk aversion and love of risk.

 

 

                          Bargaining models: Ultimatum game, with two stages, infinite horizon

                          Game (Rubinstein’s model).

 

                        Theorem: Rubinstein’s solutions approximate the Nash solution.

                        Theorem: (Rubinstein) Infinite horizon has a unique sub game-perfect

                                          equilibrium outcome.

                    

                        Example: Stationary War of Attrition

 

                      (3)

 

  1. (  [B] Chapter 6. [F] Part II.)

            Matrix games (zero-sum or constant sum)

            Mixed strategies

 

            Min-Max theorem:  Proof by separating hyper planes theorem.

                                            Proof by reduction to Linear programming problem. [F]

 

            Solution of matrix games by linear programming. [F]

            Solution by fictitious play.

 

           Battleships, The inspection game. [B]

          

           Rationalizability and Iterated Strict Dominance.

           Theorem: they coincide in 2 player games.

 

                           Proof: by separating hyper plane theorem.

 

 

                (3)

 

 

 

 

  1. ([B] Chapter 7, [F] part III)

 

Reaction curves (with pure and mixed strategies)

Cournot models, monopoly, duopoly…

Equilibrium selection, Pareto dominance, stability.

Nash demand game, pre-play negotiation, threats

Prisoner’s dilemma, Collusion in Cournot Duopoly.

 

Theorems:

 Fixed point theorems of Kakutani and Brouwer.

Nash’s theorem on existence of equilibria.[B] and [O].

 

             The game of Hex and Brouwer’s theorem.[B] (a proof of Brouwer’s theorem)

          

             Existence of equilibrium pairs of threat strategies. [O] (Another fixed point      

                    proof.)

 

           Example: Fictitious play cannot be used to solve bi-matrix games.

 

 

    (3)