Introduction to Game Theory

1. Games in Extensive Form.- 1.1. Trees.- 1.2. Game Trees.- 1.2.1. Information Sets.- 1.3. Choice Functions and Strategies.- 1.3.1. Choice Subtrees.- 1.4. Games with Chance Moves.- 1.4.1. A Theorem on Payoffs.- 1.5. Equilibrium N-tuples of Strategies.- 1.6. Normal Forms.- 2. Two-Person Zero-Sum Games.- 2.1. Saddle Points.- 2.2. Mixed Strategies.- 2.2.1. Row Values and Column Values.- 2.2.2. Dominated Rows and Columns.- 2.3. Small Games.- 2.3.1. 2 × n and m × 2 Games.- 2.4. Symmetric Games.- 2.4.1. Solving Symmetric Games.- 3. Linear Programming.- 3.1. Primal and Dual Problems.- 3.1.1. Primal Problems and Their Duals.- 3.2. Basic Forms and Pivots.- 3.2.1. Pivots.- 3.2.2. Dual Basic Forms.- 3.3. The Simplex Algorithm.- 3.3.1. Tableaus.- 3.3.2. The Simplex Algorithm.- 3.4. Avoiding Cycles and Achieving Feasibility.- 3.4.1. Degeneracy and Cycles.- 3.4.2. The Initial Feasible Tableau.- 3.5. Duality.- 3.5.1. The Dual Simplex Algorithm.- 3.5.2. The Duality Theorem.- 4. Solving Matrix Games.- 4.1. The Minimax Theorem.- 4.2. Some Examples.- 4.2.1. Scissors-Paper-Stone.- 4.2.2. Three-Finger Morra.- 4.2.3. Colonel Blotto's Game.- 4.2.4. Simple Poker.- 5. Non-Zero-Sum Games.- 5.1. Noncooperative Games.- 5.1.1. Mixed Strategies.- 5.1.2. Maximin Values.- 5.1.3. Equilibrium N-tuples of Mixed Strategies.- 5.1.4. A Graphical Method for Computing Equilibrium Pairs.- 5.2. Solution Concepts for Noncooperative Games.- 5.2.1. Battle of the Buddies.- 5.2.2. Prisoner's Dilemma.- 5.2.3. Another Game.- 5.2.4. Supergames.- 5.3. Cooperative Games.- 5.3.1. Nash Bargaining Axioms.- 5.3.2. Convex Sets.- 5.3.3. Nash's Theorem.- 5.3.4. Computing Arbitration Pairs.- 5.3.5. Remarks.- 6. N-Person Cooperative Games.- 6.1. Coalitions.- 6.1.1. The Characteristic Function.- 6.1.2. Essential and Inessential Games.- 6.2. Imputations.- 6.2.1. Dominance of Imputations.- 6.2.2. The Core.- 6.2.3. Constant-Sum Games.- 6.2.4. A Voting Game.- 6.3. Strategic Equivalence.- 6.3.1. Equivalence and Imputations.- 6.3.2. (0,1)-Reduced Form.- 6.3.3. Classification of Small Games.- 6.4. Two Solution Concepts.- 6.4.1. Stable Sets of Imputations.- 6.4.2. Shapley Values.- 7. Game-Playing Programs.- 7.1. Three Algorithms.- 7.1.1. The Naive Algorithm.- 7.1.2. The Branch and Bound Algorithm.- 7.1.3. The Alpha-Beta Pruning Algorithm.- 7.2. Evaluation Functions.- 7.2.1. Depth-Limited Subgames.- 7.2.2. Mancala.- 7.2.3. Nine-Men's Morris.- Appendix. Solutions.