Game Theory Concepts and Models in Strategic Decision-Making
Exploring various solution concepts and game models in the realm of game theory, this presentation delves into topics such as Nash equilibrium, dominance, dominant strategy equilibrium, mixed strategies, and iterated dominance. It discusses how players decide on particular equilibria, possible solutions, and issues related to strategic decision-making in games. The slides touch upon concepts like multiplicity of Nash equilibria, dominance by mixed strategies, and path-dependence in iterated dominance.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Other Solution Concepts and Game Models CS598 Ruta Mehta Some slides are borrowed from V. Conitzer s presentations.
So far Normal-form games Multiple rational players, single shot, simultaneous move Nash equilibrium Existence Computation in two-player games.
Today: Issues with NE Multiplicity Selection: How players decide/reach any particular NE Possible Solutions Dominance: Dominant Strategy equilibria Arbitrator/Mediator: Correlated equilibria, Coarse- correlated equilibria Communication/Contract: Stackelberg equilibria, Nash bargaining Other Games Extensive-form Games, Bayesian Games
Dominance if Player i s strategy ?? strictly dominates ?? for all ? ?, ??(?? ,? ?) > ??(?? ?? weakly dominates ?? if for all ? ?, ??(?? ,? ?) ??(?? for some ? ?, ??(?? ,? ?) > ??(?? ,? ?) ,? ?) -i = the player(s) other than i ,? ?); and L M R 0, 0 1, -1 1, -1 -1, 1 0, 0 -1, 1 -1, 1 1, -1 0, 0 U strict dominance G weak dominance B
Dominant Strategy Equilibrium Playing move ? is best for me, no matter what others play. For each player ?, there is a (move) strategy ?? that (weakly) dominates all other strategies. for all i,si ,? ?, ??(??,? ?) ??(?? ,? ?); Example?
Dominance by Mixed strategies Example of dominance by a mixed strategy: 3, 1 0, 0 0, 0 3, 2 1, 0 1, 1 1/2 1/2
Iterated dominance: path (in)dependence Iterated weak dominance is path-dependent: sequence of eliminations may determine which solution we get (if any) (whether or not dominance by mixed strategies allowed) 0, 1 1, 0 0, 0 0, 0 1, 0 0, 1 0, 1 1, 0 0, 0 0, 0 1, 0 0, 1 0, 1 1, 0 0, 0 0, 0 1, 0 0, 1 Iterated strict dominance is path-independent: elimination process will always terminate at the same point (whether or not dominance by mixed strategies allowed)
?1 ?? ?? ?1 ?? ?? ?1 ?? ?? ?1 ?? ?? A B ???? ? ???, ? NE: ???? ???? , ? No one plays dominated strategies. Why? What if they can discuss beforehand?
Players: {Alice, Bob} Two options: {Football, Tennis} 2 3 1 3 F T At Mixed NE both get 2/3 < 1 F 1 2 0 0 1 3 0.5 T 0 0 2 1 2 3 0.5 Instead they agree on (F, T), (T, F) Payoffs are (1.5, 1.5) Fair! Needs a common coin toss!
Correlated Equilibrium (CE) (Aumann 74) Mediator declares a joint distribution ? over S= ??? Tosses a coin, chooses ? = (?1, ,??)~?. Suggests s? to player ?in private ? is at equilibrium if each player wants to follow the suggestion when others do. ,?(??, .), ?? ?1 ????,?(??, .) ???? ? ? ? ?? ??,? ???(??,? ?)Linear in P variables!
CE for 2-Player Case ?11 ??1 ?1? ??? Mediator declares a joint distribution ? = Tosses a coin, chooses ?,? ~?. Suggests ? to Alice, ? to Bob, in private. ? is at equilibrium if each player wants to follow the suggestion, when the other do too. Given Alice is suggested ?, she knows Bob is suggested ? ~?(?,.) ? ? ,. ,? ?,. ? .,? ,? .,? ? ?1 ? ?2 ? ?,. ,? ?,. ? .,? ,? .,?
Players: {Alice, Bob} Two options: {Football, Shopping} F S F 1 2 0 0 0.5 S 0 0 2 1 0.5 Instead they agree on (F, S), (S, F) Payoffs are (1.5, 1.5) CE! Fair!
Rock-Paper-Scissors (Aumann) Prisoner s Dilemma C NC R P S -5, -5 0, -6 C 0, 0 0, 1 1, 0 R 0 1 0 1/6 1/6 -6, 0 -1, -1 NC 1, 0 0, 0 0, 1 P 0 0 0 1/6 1/6 0, 1 1, 0 0, 0 NC is dominated S 0 1/6 1/6 When Alice is suggested R Bob must be following ?(?,.)= (0,1/6,1/6) Following the suggestion gives her 1/6 While P gives 0, and S gives 1/6.
Computation: Linear Feasibility Problem Two-player Game (A, B): play (?,?) w.p. ??? ??????? ??? ???? ?,? ?1 ??????? ???? ??? ?,? ?2 ?????= 1 ? N-player game: Find distribution P over ? = ?=1 s.t. ????,?(??, .) ???? ? ??(?) = 1 ? ? ? ???(??,? ?)? ??,? ?Linear in P variables! ?? ,???, . , ??,?? ??
Computation: Linear Feasibility Problem ? N-player game: Find distribution P over ? = ?=1 s.t. ????,?(?,.) ???? ? ??(?) = 1 ? ? ? ???(??,? ?)? ??,? ?Linear in P variables! ?? ,???,. , ??,?? ?? Can optimize convex function as well!
Coarse- Correlated Equilibrium After mediator declares P, each player opts in or out. Mediator tosses a coin, and chooses s ~ P. If player ? opted in, then suggests her ?? in private, and she has to obey. If she opted out, then she knows nothing about s, and plays a fixed strategy ? ?? At equilibrium, each player wants to opt in, if others are. ??? ???,? ?, ? ?? Where ? ? is joint distribution of all players except i.
Importance of (Coarse) CE Natural dynamics quickly arrive at approximation of such equilibria. No-regret, Multiplicative Weight Update (MWU) Poly-time computable in the size of the game. Can optimize a convex function too.
Show the following CCE CE NE PNE DSE
Extensive-form Game Players move one after another Chess, Poker, etc. Tree representation. Firm 2 Strategy of a player: What to play at each of its node. out in Firm 1 2,0 accommodate fight I O -1, 1 2, 0 -1,1 1,1 F 1, 1 2, 0 A Entry game
A poker-like game Both players put 1 chip in the pot Player 1 gets a card (King is a winning card, Jack a losing card) Player 1 decides to raise (add one to the pot) or check Player 2 decides to call (match) or fold (P1 wins) If player 2 called, player 1 s card determines pot winner nature 1 gets King 1 gets Jack player 1 player 1 raise check raise check player 2 player 2 call fold call fold call fold call fold 2 1 1 1 -2 1 -1 1
Poker-like game in normal form nature 1 gets King 1 gets Jack cc cf fc ff player 1 player 1 0, 0 .5, -.5 -.5, .5 0, 0 0, 0 1, -1 0, 0 1, -1 0, 0 1, -1 1, -1 1, -1 1, -1 rr raise check raise check rc 1.5, -1.5 -.5, .5 1, -1 player 2 player 2 cr call fold call fold call fold call fold cc 2 1 1 1 -2 1 -1 1 Can be exponentially big!
Sub-Game Perfect Equilibrium Every sub-tree is at equilibrium Computation when perfect information (no nature/chance move): Backward induction Firm 2 out in Firm 1 2,0 accommodate fight Firm 2 out in 1,1 -1,1 1,1accommodate 2,0 Entry game
Sub-Game Perfect Equilibrium Every sub-tree is at equilibrium Computation when perfect information (no nature/chance move): Backward induction Firm 2 out in Firm 1 (accommodate, in) 2,0 accommodate fight Firm 2 out in 1,1 -1,1 1,1accommodate 2,0 Entry game
Corr. Eq. in Extensive form Game How to define? CE in its normal-form representation. Is it computable? Recall: exponential blow up in size. Can there be other notions? See Extensive-Form Correlated Equilibrium: Definition and Computational Complexity by von Stengel and Forges, 2008.
Commitment (Stackelberg strategies)
Commitment 1, 1 3, 0 0, 0 2, 1 Unique Nash equilibrium (iterated strict dominance solution) von Stackelberg Suppose the game is played as follows: Player 1 commits to playing one of the rows, Player 2 observes the commitment and then chooses a column Optimal strategy for player 1: commit to Down
Commitment: an extensive-form game For the case of committing to a pure strategy: Player 1 Up Down Player 2 Player 2 Left Right Left Right 1, 1 3, 0 0, 0 2, 1
Commitment to mixed strategies 0 1 1, 1 0, 0 3, 0 2, 1 .49 .51 Also called a Stackelberg (mixed) strategy
Commitment: an extensive-form game for the case of committing to a mixed strategy: Player 1 (1,0) (=Up) (0,1) (=Down) (.5,.5) Player 2 Left Right Left Right Left Right 2, 1 1, 1 3, 0 .5, .5 2.5, .5 0, 0 Economist: Just an extensive-form game, nothing new here Computer scientist: Infinite-size game! Representation matters
Computing the optimal mixed strategy to commit to [Conitzer & Sandholm EC 06] Alice is a leader. Separate LP for every column j* ?2: subject to ?, ???? ???? ? 0, ???= 1 Among soln. of all the LPs, pick the one that gives max utility. maximize ?????? Alice s utility when Bob plays ? Playing ? is best for Bob ? is a probability distribution
On the game we saw before 1, 1 3, 0 0, 0 2, 1 x y maximize 1x + 0y maximize 3x + 2y subject to subject to 1x + 0y 0x + 1y 0x + 1y 1x + 0y x + y = 1 x + y = 1 x 0, y 0 x 0, y 0
Generalizing beyond zero-sum games Minimax, Nash, Stackelberg all agree in zero-sum games 0, 0 -1, 1 -1, 1 0, 0 zero-sum games minimax strategies zero-sum games general-sum games Nash equilibrium zero-sum games general-sum games Stackelberg mixed strategies
Other nice properties of commitment to mixed strategies 0, 0 -1, 1 No equilibrium selection problem 1, -1 -5, -5 Leader s payoff at least as good as any Nash eq. or even correlated eq. (von Stengel & Zamir [GEB 10])
Bayesian Games So far in Games, - Complete information (each player has perfect information regarding the element of the game). Bayesian Game - A game with incomplete information - Each player has initial private information, type. - Bayesian equilibrium: solution of the Bayesian game
Bayesian game Utility of a player depends on her type and the actions taken in the game i is player i s type, ??~ ?. Utilily when ?? type and ? play is ??(??,?) Each player knows/learns its own type, but only distribution of others (before choosing action) Pure strategy ??: ? ??(where Si is i s set of actions) (In general players can also receive signals about other players utilities; we will not go into this) L R L R 4 6 U 4 6 U column player type 1 (prob. 0.5) row player type 1 (prob. 0.5) 4 6 D 2 4 D L R L R 2 2 U 2 4 U column player type 2 (prob. 0.5) row player type 2 (prob. 0.5) 4 2 D 4 2 D
Car Selling Game A seller wants to sell a car A buyer has private value v for the car w.p. P(v) Sellers knows P, but not v Seller sets a price p , and buyer decides to buy or not buy. If sell happens then the seller gets p, and buyer gets (v-p). ?1=All possible prices, 1={1} ?2={buy, not buy}, 2=All possible v ?11,(?,buy) = ?, ?2(?,(?,buy))=? ?, ?2?,(?,not buy) = 0 U11,(?,not buy) = 0
Converting Bayesian games to normal form L R row player type 1 (prob. 0.5) L R 4 6 U 4 6 U column player type 1 (prob. 0.5) 4 6 D 2 4 D L R L R 2 2 U 2 4 U column player type 2 (prob. 0.5) row player type 2 (prob. 0.5) 4 2 D 4 2 D type 1: L type 2: L type 1: L type 2: R type 1: R type 2: L type 1: R type 2: R type 1: U type 2: U 3, 3 4, 3 4, 4 5, 4 exponential blowup in size 4, 3.5 4, 3 4, 4.5 4, 4 type 1: U type 2: D 2, 3.5 3, 3 3, 4.5 4, 4 type 1: D type 2: U 3, 4 3, 3 3, 5 3, 4 type 1: D type 2: D
Bayes-Nash equilibrium A profile of strategies is a Bayes-Nash equilibrium if it is a Nash equilibrium for the normal form of the game Minor caveat: each type should have >0 probability Alternative definition: Mixed strategy of player i, ??: ? ?? for every i, for every type i, for every alternative action si, we must have: -iP( -i) ui( i, i( i), -i( -i)) -iP( -i) ui( i, si, -i( -i)) ? ??(??)
Again what about corr. eq. in Bayesian games? Notion of signaling. Look up the literature.
