Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Game theory & Linear ProgrammingSteve GuMar 28, 2008Outline•Background•Nash Equilibrium•Zero-Sum Game•How to Find NE using LP?•SummaryBackground: History of Game Theory•John Von Neumann 1903 – 1957.•Book - Theory of Games and Economic Behavior.•John Forbes Nash 1928 – •Popularized Game Theory with his Nash Equilibrium (Nobel prize).Background: Game theoryBackground: Prison’s DilemmaGiven you’re Dave, what’s the best choice?Nash EquilibriumA set of strategies is a Nash equilibrium if no player can do better by changing his or her strategyNash Equilibrium (Cont’)•Nash showed (1950), that Nash equilibria (in mixed strategies) must exist for all finite games with any number of players. •Before Nash's work, this had been proven for two-player zero-sum games (by John von Neumann and Oskar Morgenstern in 1947).•Today, we’re going to find such Nash equilibria using Linear Programming for zero-sum gameZero-Sum Game•A strictly competitive or zero-sum game is a 2-player strategic game such that for each action a  A, we have u1(a) + u2(a) = 0. (u represents for utility)–What is good for me, is bad for my opponent and vice versaZero-Sum Game•Mixed strategy–Making choice randomly obeying some kind of probability distribution•Why mixed strategy? (Nash Equilibrium)•E.g. : P(1) = P(2) = 0.5; P(A) = P(B)=P(C)=1/3Solving Zero-Sum Games•Let A1 = {a11, …, a1n }, A2 = {a21, …, a2m } •Player 1 looks for a mixed strategy p–∑i p(a1i ) = 1–p(a1i ) ≥ 0 –∑i p(a1i ) · u1(a1i, a2j) ≥ r for all j {1, …, m}–Maximize r!•Similarly for player 2.Solve using Linear Programming•What are the unknowns?–Strategy (or probability distribution): p•p(a11 ), p(a12 ),..., p(a1n-1 ), p(a1n )~n numbers •Denoted as p1,p2,...,pn-1,pn–Optimum Utility or Reward: r•Stack all unknowns into a column vector•Goal: maximize: where 121nnrppxpp-� �� �� �� �=� �� �� �� �� �� �MTf x( )1 0 0 0Tf = LSolve Zero-Sum Game using LP•What are the constraints?( )11 0 1 1 1niip x== � =�L121nnrppxpp-� �� �� �� �=� �� �� �� �� �� �M111 1 21 2 112 1 22 2 21 1 2 2, for all {1, 2,..., }, . .... 0... 0...... 0ni ijin nn nn n nb np u r j m i er u p u p u pr u p u p u pr u p u p u p=� �- - - - �- - - - �- - - - ��Solve Zero-Sum Game using LP( )1; 0 0TU x Ax�-ޣ11 1 21 2 112 1 22 2 21 1 2 2... 0... 0...... 0n nn nn n nb nr u p u p u pr u p u p u pr u p u p u p- - - - �- - - - �- - - - �Let: Ae=(0,1,…,1) Aie=(1;-UT) f=(1,0,…,0)TThe LP is: maximize fTxsubject to: Aiex<=0 Aex=1Summary•Zero-Sum Game  Mixed Strategy  NE•Connections with Linear