STAT 155, Fall 2009

Shobhana Murali

MAIN POINTS COVERED IN THE LECTURES:

Th 8/27: Overview of the course, and examples of each type of game.

T 9/1: Examples: Odds & Evens, definition of combinatorial games vs partisan games. Subtraction games introduced and discussed. Will be a recurring example. Discussion on whether hex impartial or partisan. Definition of progressively bounded games, an important concept that is crucial to many proofs. Description of using graphs to model games. Backward induction used to analyze subtraction games.

Th 9/3: Recursive characterization of N and P positions. Proved a crucial fact: in a progressively bounded game, all positions are in ,N or in P, Introduced Chomp, and proved that the first player always has a winning strategy (strategy-stealing argument). Introduced Nim, and proved Lemma 2.1.1 which tells us how to analyze nim positions by decomposing it into smaller nim games.

T 9/8: Proved Bouton's theorem, and now we can analyze any nim game. Also looked at his solution to Misère nim. Analyzed Wythoff's nim, and defined mex of a subset of the non-negative integers.

Th 9/10: Defined sums of games. Proved Thm 2.1.9, which generalizes Lemma 2.1.1. Defined the Sprague-Grundy function of a progressively bounded impartial combinatorial game under normal play, which we will use to analyze lots of games. Proved Lemma 2.1.2 which tells us exactly when a position is P. Defined what it means for two games to be equivalent. Encountered the incredible Sprague-Grundy theorem, and stated the Sum theorem, which will be used to prove the SG theorem.

T 9/15: Proved the Sum theorem, and saw that the Sprague-Grundy theorem follows easily. Looked at applications. Looked at SG function on graphs.

Th 9/17: Looked at Wythoff's nim again, this time modeled as a queen moving on an 8 x 8 chessboard, and filled in SG values. Discussed Grundy's game. Discussed Green Hackenbush, Colon Principle and the Fusion principle. Defined some basic concepts related to trees.

T 9/22: Discussed partisan games, and associated definitions. Proved Thm 2.2.1,

Th 9/24: Used strategy stealing argument to show that on a standard, symmetric Hex board, player I always has a winning strategy. Introduced the game of Y, used to analyze Hex. Proved that any colored standard Hex board always contains a monochromatic crossing (and all such crossings have the same color). This proves that the game always ends in a win for one of the players.

T 9/29: Introduced 2-person zero sum games, and the strategic description of a game (as opposed to the extensive description). Defined payoff matrices, mixed,pure, and optimal strategies; and the value of a game. Solved simple games graphically, using minimax and maximin strategies.

Th 10/1: Defined formal notation. Proved supporting hyperplane theorem, and the fundamental theorem of classical game theory - Von Neumann's Minimax theorem.

T 10/6: Clarified and reviewed Minimax theorem. Discussed dominating strategies and saddle points.

Th 10/8: This was mostly about solving games. Battleship example from section 3.4 (variation: #15, page II-31), Two finger Morra, Solving symmetric games (payoff matrix skew-symmetric, value = 0, players interchangeable), Equilibrium theorem (Thm 3.1 on page II-17).

T 10/13: Began non zero-sum games (chap 4 in GTA), and looked at pure strategies. Assumed rational behaviour, and looked at non-cooperative models (players behave independently). Discussed Prisoner's dilemma, and concept of Pareto optimality. Also looked at Chicken, and discussed Cuban missile crisis. Looked at effect of foreknowledge of opponent's choice, and effect on game. Still looking only at pure strategies. Encountered Nash equilibria., and saw that pure Nash equilibrium points need not always exist.

Th 10/15: Midterm Exam

T 10/20: Defined mixed Nash equilibria, looked at several examples. Defined maximin strategies for general sum games. Defined correlated equilibria, of which Nash equilibria is a special case.

Th 10/22: Went over examples of correlated equilibria (battle of the sexes, motorists & traffic light, chicken). Defined notation for k-player games, where k is at least 2. Stated Brouwer's Fixed Point theorem, and gave examples for 1 dimension (the graph has to cross the line x=y, 2 dimensions (crumpled sheet experiment), and 3 dimensions (cup of coffee being stirred).

T 10/27: Proved Nash's theorem. Began discussion of evolutionary game theory with discussion of evolutionarily stable strategies. Started with example of hawks and doves, from Game Theory and Strategy by Philip Straffin.

Th 10/29: Detailed look at some examples from Evolutionary game theory (Hawk-doves, rock paper scissors).

T 11/3: Finished up general-sum games with examples : Used car market, Kuhn trees, fish-seller example. Started describing Potential games.

Th 11/5: Went over potential games, and congestion games in particular. Saw that every finite congestion game has a pure Nash equilibrium.

T 11/10: Introduced characteristic functions of game and the coalitional or characteristic form of games. Defined characteristic functions (followed Ferguson's text for much of this material). Looked at examples of how to find the characteristic function v . Defined the core and imputations.

Th 11/12: Examples: Divide-the-dollar, communications satellites.Found the set of imputations, and the core (empty in both these cases). Defined the Shapley axioms, and Shapley values. Shapley's theorem, and sketch of proof ( read the proof from Ferguson's text). Did an example, (leading into theorem 2 from section IV in Ferguson's text), of another way of computing the Shapley value.

T 11/17: Theorem 2 from Ferguson, giving a formula for computing the Shapley value. Application of Shapley value : The Shapley-Shubik Power index.

Th 11/19: Social choice: Arrow's fairness criteria, voting methods and how they violate (or not) the fairness criteria.

T 11/23: Geanokoplos' proof of Arrow's theorem.

T 12/1: Mechanism design: Discussed various types of auctions and their equivalences.

Th 12/3: Examined auctions in more detail. Defined Bayesian-Nash equilibrium. Statement of Revenue equivalence theorem. Assumptions for the theorem. Examples of how to compute Bayesian Nash equilibrium.


Last modified: Tue Dec 8 07:33:39 PST 2009