1Games with Hidden InformationR&N Chapter 6R&N Section 17.6• Assumptions so far:– Two-player game: Player A and B. – Perfect information: Both players see all the states and decisions. Each decision is made sequentially.– Zero-sum: Player’s A gain is exactly equal to player B’s loss.• We are going to eliminate these constraints. We will eliminate first the assumption of “perfect information” leading to far more realistic models.– Some more game-theoretic definitions Matrix games– Minimax results for perfect information games – Minimax results for hidden information games21234-1+4+2 +5+2LLLRRLRPlayer APlayer BPlayer AExtensive form of game: Represent the game by a tree1234-1+4+2 +5+2LLLRRLRA pure strategy for a player defines the move that the player would make for every possible state that the player would see.3Pure strategies for A:Strategy I: (1L,4L)Strategy II: (1L,4R)Strategy III: (1R,4L)Strategy IV: (1R,4R)Pure strategies for B:Strategy I: (2L,3L)Strategy II: (2L,3R)Strategy III: (2R,3L)Strategy IV: (2R,3R)1234-1+4+2 +5+2LLLRRLRRIn general: If N states and B moves, how many pure strategies exist?Matrix form of games1234-1+4+2 +5+1LLLRRLRRPure strategies for A:Strategy I: (1L,4L)Strategy II: (1L,4R)Strategy III: (1R,4L)Strategy IV: (1R,4R)Pure strategies for B:Strategy I: (2L,3L)Strategy II: (2L,3R)Strategy III: (2R,3L)Strategy IV: (2R,3R)+1+5+1+5IV+1+5+1+5III+2+2+4+4II+2+2-1-1IIVIIIIII4+1+5+1+5IV+1+5+1+5III+2+2+4+4II+2+2-1-1IIVIIIIIIPure strategies for Player BPure strategiesfor Player APlayer A’s payoff if game is played with strategy I by Player A and strategy III by Player B• Matrix normal form of games: The table contains the payoffs for all the possible combinations of pure strategies for Player A and Player B• The table characterizes the game completely, there is no need for any additional information about rules, etc.• Although, in many cases, the number of pure strategies may be too large for the table to be represented explicitly, the matrix representation is the basic representation that is used for deriving fundamental properties of games.MinimaxMatrix version+1+5+1+5IV+1+5+1+5III+2+2+4+4II+2+2-1-1IIVIIIIIIMin value across each row),( jiMinMaxjColumnsiRowsM-1+2Max value ofall the rows+1+15Minimax Matrix version• For each strategy (each row of the game matrix), Player A should assume that Player B will use the optimal strategy given Player A’s strategy (the strategy with the minimum value in the row of the matrix). Therefore the best value that Player can achieve is the maximum over all the rows of the minimum values across each of the rows:• The corresponding pure strategy is the optimal solution for this game It is the optimal strategy for A assuming that B plays optimally.+1+5+1+5IV+1+5+1+5III+2+2+4+4II+2+2-1-1IIVIIIIII-1+2+1+1Min value across each rowMax value = game value = +2),( jiMinMaxjColumnsiRowsM+1+5+1+5IV+1+5+1+5III+2+2+4+4II+2+2-1-1IIVIIIIIIMax value acrosseach columnMin of all the columns+5 +4 +5+2),( jiMaxMiniRowsjColumnsM6Minimax or Maximin?• But we could have used the opposite argument:• For each strategy (each column of the game matrix), Player B should assume that Player A will use the optimal strategy given Player B’s strategy (the strategy with the maximum value in the column of the matrix): • Therefore the best value that Player B can achieve is the minimum over all the columns of the maximum values across each of the columns• Problem: Do we get to the same result??• Is there always a solution?+1+5+1+5IV+1+5+1+5III+2+2+4+4II+2+2-1-1IIVIIIIII+5 +4 +5 +2Max value across each columnMin value = game value = +2),( jiMaxMiniRowsjColumnsM-1+2+1+1Min value across each rowMax value = game value = +2),( jiMinMaxjColumnsiRowsM+1+5+1+5IV+1+5+1+5III+2+2+4+4II+2+2-1-1IIVIIIIII+5 +4 +5 +2Max value across each columnMin value = game value = +2),( jiMaxMiniRowsjColumnsM+1+5+1+5IV+1+5+1+5III+2+2+4+4II+2+2-1-1IIVIIIIIINote that we find the same value and same strategies in both cases. Is that always the case?7Minimaxvs. Maximin• Fundamental Theorem I (von Neumann):– For a two-player, zero-sum game with perfect information:• There always exists an optimal pure strategy for each player• Minimax = Maximin• Note: This is a game-theoretic formalization of the minimax search algorithm that we studied earlier.Another (Seemingly Simple) Game• The two Players A and B each have a coin• They show each other their coin, choosing to show either head or tail.• If they both choose head Player B pays Player A $2• If they both choose tail Player B pays Player A $1• If they choose different sides Player A pays Player B $18Side Note about all toy examples• If you find this kind of toy example annoying, it models a large number of real-life situations.• For example: Player A is a business owner (e.g., a restaurant, a plant..) and Player B is an inspector. The inspector picks a day to conduct the inspection; the owner picks a day to hide the bad stuff. Player B wins if the days are different; Player A wins if the days are the same. • This class of problems can be reduced to the “coin game” (with different payoff distributions, perhaps).Extensive FormHTTTHHPlayer APlayer B+2 +1-1-19Extensive FormProblem: Since the moves are simultaneous, Player B does not know which move Player A chose This is no longer a game with prefect information we have to deal with hidden informationHTTTHHPlayer APlayer B+2 +1-1-1+1-1T-1+2HTHPlayer BPlayer A10Matrix Normal Form• It is no longer the case that maximin = minimax(easy to verify: -1 vs. +1)• Therefore: It appears that there is no pure strategy solution• In fact, in general, none of the pure strategiesare solutions to a zero-sum game with hidden information+1-1T-1+2HTHPlayer BPlayer AWhy no Pure Strategy Solutions?• Intuition:• If Player A considers move H, he has to assume that Player B will choose the worst-case move (for A), which is move T– Therefore Player A should try move T instead, but then he has toassume that Player B will choose the worst-case move (for A), which is move H.• Therefore Player A should consider move H, but then he has to assume that Player B will choose the worst-case move (for A), which is move T.– Therefore Player A should try move T instead, but then he has toassume that Player B will choose the
View Full Document
Unlocking...