Game Theory Lecture Notes - Pennsylvania State University

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. 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.

2 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. 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.

3 Relating Back to Game Theory93 Chapter 8. Zero-Sum Matrix games with Linear Programming951. Linear Programs952. 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. Nash s Bargaining Axioms1334. Nash s Bargaining Theorem134 Chapter 11. A Short Introduction toN-Player Cooperative Games1411. Motivating Cooperative Games1412.

4 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. 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.

5 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. 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.

6 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. 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.)

7 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. 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.

8 The strategy space is constructed from the unique choices determinedby the strategy of the players and the independent random events that aredetermined by the chance probability space constructed from fixed player strategies in a game ofchance. The strategy space is constructed from the unique choices determinedby the strategy of the players and the independent random events that aredetermined by the chance moves. Note in this example that constructing theprobabilities of the various events requiresmultiplyingthe probabilities of thechance moves in each tree paths derived from the Simple Poker Game as a result of the strategy(Fold, Fold). The probability of each of these paths is 1 game tree for the Battle of the Bismark Sea. If the Japanese sail north, thebest move for the Allies is to search north. If the Japanese sail south, then theLIST OF FIGURES viibest move for the Allies is to search south. The Japanese, observing the payoffs,note that given these best strategies for the Allies, there best course of action isto sail Chicken, two cars drive toward one another.

9 The player who swerves firstloses 1 point, the other player wins 1 point. If both players swerve, then eachreceives 0 points. If neither player swerves, a very bad crash occurs and bothplayers lose 10 three dimensional array is like a matrix with an extra dimension. They aredifficult to capture on a page. The elements of the array for Playeristore thevarious payoffs for Playeriunder different strategy combinations of the differentplayers. If there are three players, then there will be three different minimax analysis of the game of competing networks. The row player knowsthat Player 2 (the column player) is trying to maximize her [Player 2 s] , Player 1 asks: What is the worst possible outcome I could see if I playeda strategy corresponding to this row? Having obtained theseworst possiblescenarioshe chooses the row with the highest value. Player 2 does somethingsimilar in August 1944, the allies broke out of their beachhead at Avranches and startedheading in toward the mainland of France.

10 At this time, General Bradley was incommand of the Allied forces. He faced General von Kluge of the German nintharmy. Each commander faced several troop movement choices. These choicescan be modeled as a the battle of Avranches General Bradley and General von Kluge faced offover the advancing Allied Army. Each had decisions to make. This game matrixshows that this game hasnosaddle point solution. There is no position in thematrix where an element is simultaneously the maximum value in its columnand the minimum value in its von Kluge chooses to retreat, Bradley can benefit by playing a strategydifferent from his maximin strategy and he moves east. When Bradley does this,von Kluge realizes he could benefit by attacking and not playing his maximinstrategy. Bradley realizes this and realizes he should play his maximin strategyand wait. This causes von Kluge to realize that he should retreat, causing thiscycle to payoff matrix for PlayerP1in Rock-Paper-Scissors.