Game Theory Lecture Notes

1 Game Theory : Penn State Math 486 LectureNotesVersion Griffin 2010-2012 Licensed under a Creative Commons Attribution-Noncommercial-Share Alike United States LicenseWith Major Contributions By:James FanGeorge Kesidisand Other Contributions By:Arlan StutlerContentsList of FiguresvChapter 1. Preface and an Introduction to Game Theoryxi1. Using These Notesxi2. An Overview of Game TheoryxiChapter 2. Probability Theory and games Against the House11. Probability12. Random Variables and Expected Values63. Conditional Probability74. Bayes Rule12 Chapter 3. Utility Theory151. Decision Making Under Certainty152. Advanced Decision Making under Uncertainty22 Chapter 4.

2 Game Trees, Extensive Form, Normal Form and Strategic Form251. Graphs and Trees252. Game Trees with Complete Information and No Chance283. Game Trees with Incomplete Information324. games of Chance345. Pay-off Functions and Equilibria36 Chapter 5. Normal and Strategic Form games and Matrices471. Normal and Strategic Form472. Strategic Form Games483. Review of Basic Matrix Properties504. Special Matrices and Vectors525. Strategy Vectors and Matrix Games53 Chapter 6. Saddle Points, Mixed Strategies and the Minimax Theorem551. Saddle Points552. Zero-Sum games without Saddle Points583. Mixed Strategies604.

3 Mixed Strategies in Matrix Games635. Dominated Strategies and Nash Equilibria646. The Minimax Theorem697. Finding Nash Equilibria in Simple Games748. A Note on Nash Equilibria in General76 Chapter 7. An Introduction to Optimization and the Karush-Kuhn-Tucker Conditions 79iiiivCONTENTS1. A General Maximization Formulation802. Some Geometry for Optimization823. Gradients, Constraints and Optimization864. Convex Sets and Combinations885. Convex and Concave Functions896. Karush-Kuhn-Tucker Conditions907. Relating Back to Game Theory93 Chapter 8. Zero-Sum Matrix games with Linear Programming951. Linear Programs952.

4 Intuition on the Solution of Linear Programs963. A Linear Program for Zero-Sum Game Players1004. Matrix Notation, Slack and Surplus Variables for Linear Programming1035. Solving Linear Programs by Computer1056. Duality and Optimality Conditions for Zero-Sum Game Linear Programs108 Chapter 9. Quadratic Programs and General Sum Games1151. Introduction to Quadratic Programming1152. Solving QP s by Computer1163. General Sum games and Quadratic Programming116 Chapter 10. Nash s Bargaining Problem and Cooperative Games1271. Payoff Regions in Two Player Games1272. Collaboration and Multi-criteria Optimization1313.

5 Nash s Bargaining Axioms1334. Nash s Bargaining Theorem134 Chapter 11. A Short Introduction toN-Player Cooperative Games1411. Motivating Cooperative Games1412. Basic Results on Coalition Games1423. Division of Payoff to the Coalition1434. The Core1445. Shapley Values146 Bibliography149 List of are several sub-disciplines within Game Theory . Each one has its ownunique sets of problems and applications. We will study Classical Game Theory ,which focuses on questions like, What is my best decision in a given economicscenario, where a reward function provides a way for me to understand how mydecision will impact my result.

6 We may also investigate Combinatorial GameTheory, which is interested in games like Chess or Go. If there s time, we llstudy Evolutionary Game Theory , which is interesting in its own Monty Hall Problem is a multi-stage decision problem whose solutionrelies on conditional probability. The stages of decision making are shown inthe diagram. We assume that the prizes are randomly assigned to the can t see this step so we ve adorned this decision with a square box. We lldiscuss these boxes more when we talk aboutgame trees. You the player mustfirst choose a door. Lastly, you must decide whether or not to switch doorshaving been shown a door that is on 3 Vertices: There are 64 = 26distinct graphs on three vertices.

7 Theincreased number of edges graphs is caused by the fact that the edges are Paths: We illustrate two paths in a digraph on three Tree: We illustrate a directed tree. Every directed tree has a uniquevertex called theroot. The root is connected by a directed path to every othervertex in the directed Tree: We illustrate a sub-tree. This tree is the collection of all nodes thatare descended from a with Perfect Information: Player 1 moves first and holds upa symbol for either rock, paper or scissors. This is illustrated by the three edgesleaving the root node, which is assigned to Player 1. Player 2 then holds up asymbol for either rock, paper or scissors.

8 Payoffs are assigned to Player 1 and 2at terminal nodes. The index of the payoff vector corresponds to the Guinea is located in the south pacific and was a major region of contentionduring World War II. The northern half was controlled by Japan through 1943,while the southern half was controlled by the Allies. (Image created fromWikipedia ( ),originally sourced OF game tree for the Battle of the Bismark Sea. The Japanese could choose tosail either north or south of New Britain. The Americans (Allies) could chooseto concentrate their search efforts on either the northern or southern this game tree, the Americans would always choose to search the Northif theyknewthe Japanese had chosen to sail on the north side of New Britain;alternatively, they would search the south route, if they knew the Japanese hadtaken that.)

9 Assuming the Americans have perfect intelligence, the Japanesewould always choose to sail the northern route as in this instance they wouldexpose themselves to only 2 days of bombing as opposed to 3 with the tic-tac-toe: Players in this case try to get two in a game tree for the Battle of the Bismark Sea with incomplete Kenney could not have knowna prioriwhich path the Japanesewould choose to sail. He could have reasoned (as they might) that there bestplan was to sail north, but he wouldn t reallyknow. We can capture this fact byshowing that when Kenney chooses his move, he cannot distinguish between thetwo intermediate nodes that belong to the : The root node of the game tree is controlled by Nature.

10 At this node, asingle random card is dealt to Player 1. Player 1 can then decide whether to endthe game by folding (and thus receiving a payoff or not) or continuing the gameby raising. At this point, Player 2 can then decide whether to call or fold, thuspotentially receiving a Red Black Poker: We are told that Player 1 receives a red card. Theresulting game tree is substantially simpler. Because the information set onPlayer 2 controlled nodes indicated a lack of knowledge of Player 1 s card, wecan see that this sub-game is now a complete information unique path through the game tree of the Battle of the Bismark each player determines a priori the unique edge he/she will select whenconfronted with a specific information set, a path through the tree can bedetermined from these probability space constructed from fixed player strategies in a game ofchance.