{"id":1078,"date":"2023-06-01T01:55:30","date_gmt":"2023-05-31T16:55:30","guid":{"rendered":"https:\/\/saraheee.com\/?p=1078"},"modified":"2023-06-03T15:55:12","modified_gmt":"2023-06-03T06:55:12","slug":"game-theory-2-chap07-08-nash-equilibrium","status":"publish","type":"post","link":"https:\/\/saraheee.com\/ko\/2023\/06\/game-theory-2-chap07-08-nash-equilibrium\/","title":{"rendered":"Game Theory 2 \u2013 chap07. Nash Equilibrium &#038; Location Game"},"content":{"rendered":"<p>2. Normal-form games<br>2.4 Nash Equilibrium (Chapter 9)<br>Examples: Location, Partnership Games (Chapter 8)<\/p>\n\n\n\n<p>Recall that ISD is driven only by common knowledge of rationality<br>However, ISD makes a weak prediction in many games<\/p>\n\n\n\n<figure class=\"wp-block-image size-large is-resized\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/saraheee.com\/wp-content\/uploads\/2023\/06\/image-8-1024x642.png\" alt=\"\" class=\"wp-image-1242\" width=\"768\" height=\"482\" srcset=\"https:\/\/saraheee.com\/wp-content\/uploads\/2023\/06\/image-8-1024x642.png 1024w, https:\/\/saraheee.com\/wp-content\/uploads\/2023\/06\/image-8-300x188.png 300w, https:\/\/saraheee.com\/wp-content\/uploads\/2023\/06\/image-8-768x481.png 768w, https:\/\/saraheee.com\/wp-content\/uploads\/2023\/06\/image-8-1536x963.png 1536w, https:\/\/saraheee.com\/wp-content\/uploads\/2023\/06\/image-8.png 1682w\" sizes=\"(max-width: 768px) 100vw, 768px\" \/><\/figure>\n\n\n\n<p>In order to obtain a sharp prediction, therefore, we need impose restrictions on players&#8217; <strong><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-global-color-8-color\">beliefs<\/mark><\/strong> about their opponents&#8217; behavior. This will lead to the central solution concept of game theory, <em>Nash equilibrium<\/em>.<\/p>\n\n\n\n<p><\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Definition<\/h3>\n\n\n\n<p><mark style=\"background-color:var(--global-color-10)\" class=\"has-inline-color\">DEFINITION 2.10<\/mark>. A strategy profile s* = \\((s_{1}^{*}, s_{2}^{*})\\) is a <strong><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-global-color-8-color\">Nash equilibrium<\/mark><\/strong> if for each player i, \\(s_{i}^{*}\\) is a best response to \\(s_{j}^{*}\\).<\/p>\n\n\n\n<p>This implies,<\/p>\n\n\n\n<p>\\(u_{1}(s_{1}^{*}, s_{2}^{*})\\) \u2265 \\(u_{1}(s_{1}, s_{2}^{*})\\) for every \\(s_{1} \\in S_{1}\\)<\/p>\n\n\n\n<p>and<\/p>\n\n\n\n<p>\\(u_{2}(s_{1}^{*}, s_{2}^{*})\\) \u2265 \\(u_{2}(s_{1}, s_{2}^{*})\\) for every \\(s_{2} \\in S_{2}\\)<\/p>\n\n\n\n<p>Simply put, a Nash equilibrium is the players&#8217; <em>mutual<\/em> best responses<\/p>\n\n\n\n<p>Two underlying assumptions:<\/p>\n\n\n\n<p>(i) Each player has <em>correct beliefs<\/em> about what opponents will do (equilibrium knowledge)<br>(ii) Each behaves <em>rationally<\/em> given these beliefs<\/p>\n\n\n\n<p><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-global-color-15-color\">The Nash equilibrium first appeared in 1952. If we think about an equilibrium where there is no risk of deviation from economics, the other player must know exactly what they are going to do.<\/mark><br><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-global-color-15-color\">But that&#8217;s too much of an assumption to make, so we start thinking about Rationality alone.<\/mark><br><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-global-color-15-color\">This is where ISD comes in, and then Rationalizability comes in because there&#8217;s not much we can do with ISD after that.<\/mark><\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Justifications of Equilibrium Knowledge<\/h3>\n\n\n\n<h5 class=\"wp-block-heading\">1. Learning or evolution<\/h5>\n\n\n\n<ul class=\"wp-block-list\">\n<li>A game is repeatedly played in society or by a group of agents. The behavior of the players settles down in that the same strategies are used each time the game is played.<\/li>\n<\/ul>\n\n\n\n<h5 class=\"wp-block-heading\">2. Pre-play communication<\/h5>\n\n\n\n<ul class=\"wp-block-list\">\n<li>The players meet before playing a game and reach an agreement on the strategy that each will use. Subsequently, the players individually honor the agreement.<\/li>\n<\/ul>\n\n\n\n<h5 class=\"wp-block-heading\">3. Coordinatiton of play by a mediator (Contractual relationship, See Section 2.8)<\/h5>\n\n\n\n<ul class=\"wp-block-list\">\n<li>An outside mediator recommends to the players that they adopt a specific strategy. Each player, expecting that the others will follow the recommendation, has the right incentive to follow it as well.<\/li>\n<\/ul>\n\n\n\n<h5 class=\"wp-block-heading\">4. Focal points (THOMAS SCHELLING (1960))<\/h5>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Something about the game makes Nash eqbm the obvious choice about how to behave.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\">Computing Nash Equilibria<\/h3>\n\n\n\n<p>The next theorem provides a link between Nash eqbm and ISD<\/p>\n\n\n\n<p>THEOREM 2.11. If a normal-form game is solvable by ISD, the strategy profile surviving the process constitutes a <em>unique<\/em> Nash equilibrium of the game.<\/p>\n\n\n\n<p><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-global-color-15-color\">Nash eqbm is much more assumption-based than ISD.<br>If ISD solves the problem, the remaining profile is the only Nash equilibrium in the game.<\/mark><\/p>\n\n\n\n<p><mark style=\"background-color:var(--global-color-10)\" class=\"has-inline-color\">EXAMPLE 2.13<\/mark> (REVISIT PRISONER&#8217;S DILEMMA).<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td>1 \\ 2<\/td><td>C<\/td><td>D<\/td><\/tr><tr><td>C<\/td><td>2, 2<\/td><td>0, 3<\/td><\/tr><tr><td>D<\/td><td>3, 0<\/td><td>1, 1<\/td><\/tr><\/tbody><\/table><figcaption class=\"wp-element-caption\">Prisoners&#8217; Dilemma<\/figcaption><\/figure>\n\n\n\n<p>ISD leaves only one pure strategy profile, (D, D), which constitutes a unique Nash equilibrium of this game<\/p>\n\n\n\n<p>Theorem 2.11 also provides guidelines to compute Nash eqbm<\/p>\n\n\n\n<p>(1) Eliminate pure strategies that are strictly dominated. If this leaves only one pure strategy profile, then we are done: it becomes the unique Nash eqbm<br>(2) For each profile of supports, find all equilibria.<\/p>\n\n\n\n<p><mark style=\"background-color:var(--global-color-10)\" class=\"has-inline-color\">EXAMPLE 2.14<\/mark>. Find all pure-strategy Nash equilibria of the following game:<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td>1 \\ 2<\/td><td>X<\/td><td>Y<\/td><td>Z<\/td><\/tr><tr><td>J<\/td><td>5, 6<\/td><td>3, 7<\/td><td>0, 4<\/td><\/tr><tr><td>K<\/td><td>8, 3<\/td><td>3, 1<\/td><td>5, 2<\/td><\/tr><tr><td>L<\/td><td>7, 5<\/td><td>4, 4<\/td><td>5, 6<\/td><\/tr><tr><td>M<\/td><td>3, 4<\/td><td>7, 5<\/td><td>3, 3<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-global-color-15-color\">strategy J is strictly dominated by L<\/mark><\/p>\n\n\n\n<p><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-global-color-15-color\">If player 1 chooses K, then player 2&#8217;s best response is X<br>If player 1 chooses L, then player 2&#8217;s best response is Z<br>If player 1 chooses M, then player 2&#8217;s best response is Y<\/mark><\/p>\n\n\n\n<p><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-global-color-15-color\">If player 2 chooses X, then player 1&#8217;s best response is K<br>If player 2 chooses Y, then player 1&#8217;s best response is M<br>If player 2 chooses Z, then player 1&#8217;s best response are K, L<\/mark><\/p>\n\n\n\n<p><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-global-color-15-color\">So the nash equilibrium is (K, X), (M, Y), (L, Z).<\/mark><\/p>\n\n\n\n<p><mark style=\"background-color:var(--global-color-10)\" class=\"has-inline-color\">EXAMPLE 2.15<\/mark> (PARTNERSHIP GAME, CHAPTER 8). Consider a partnership between two players. The joint profit is given by<\/p>\n\n\n\n<p>4(x + y + cxy).<\/p>\n\n\n\n<p>where c \u2208 [0, 1\/4] measures the degree of <strong><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-global-color-8-color\">complementarity<\/mark><\/strong> in the partnership.<br>Suppose the cost of effort is \\(x^{2}\\) for player 1 and \\(y^{2}\\) for player 2.<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large is-resized\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/saraheee.com\/wp-content\/uploads\/2023\/06\/image-9-963x1024.png\" alt=\"\" class=\"wp-image-1251\" width=\"482\" height=\"512\" srcset=\"https:\/\/saraheee.com\/wp-content\/uploads\/2023\/06\/image-9-963x1024.png 963w, https:\/\/saraheee.com\/wp-content\/uploads\/2023\/06\/image-9-282x300.png 282w, https:\/\/saraheee.com\/wp-content\/uploads\/2023\/06\/image-9-768x817.png 768w, https:\/\/saraheee.com\/wp-content\/uploads\/2023\/06\/image-9.png 1076w\" sizes=\"(max-width: 482px) 100vw, 482px\" \/><\/figure><\/div>\n\n\n<p><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-global-color-15-color\">player 1 is x, player 2 is y related to<br>complementarity, meaning how important the collaboration is<\/mark><\/p>\n\n\n\n<p>1) player: N = {1, 2}<br>2) strategy: \\(S_{1}\\) = [0, \u221e), \\(S_{2}\\) = [0, \u221e)<br>3) \\(u_{1}\\)(x, y) = 2(x + y + cxy) &#8211; \\(x^{2}\\)<br>\\(u_{2}\\)(x, y) = 2(x + y + cxy) &#8211; \\(y^{2}\\)<\/p>\n\n\n\n<p><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-global-color-15-color\">Need to divide joint profit in half and subtract cost of effort<\/mark><\/p>\n\n\n\n<p><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-global-color-15-color\">These three elements are the normal-form representation (player, player strategy, payoff function)<\/mark><\/p>\n\n\n\n<p><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-global-color-15-color\">player 1&#8217;s payoff function \\(\\frac{\\partial u_{1}}{\\partial x}\\) = 2 + 2cy &#8211; 2x = 0 \u21d4 x = 1 + cy \u21d4 y = (x &#8211; 1)\/c<\/mark><\/p>\n\n\n\n<p><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-global-color-15-color\">player 2&#8217;s payoff function \\(\\frac{\\partial u_{2}}{\\partial y}\\) = 2 + 2cx &#8211; 2y = 0 \u21d4 y = 1 + cx<\/mark><\/p>\n\n\n\n<p><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-global-color-15-color\">1+cx = (x-1)\/c \u21d4 c + \\(c^{2}\\)x = x-1 \u21d4 (\\(c^{2}\\)-1)x = -c-1 \u21d4 x = \\((1-c)^{-1}\\) = \\(\\frac{1}{1-c}\\)<\/mark><\/p>\n\n\n\n<p><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-global-color-15-color\">y = 1+cx = 1+c\u2219\\(\\frac{1}{1-c}\\) = \\(\\frac{(1-c)+c}{1-c}\\) = \\(\\frac{1}{1-c}\\))<\/mark><\/p>\n\n\n\n<p><\/p>\n\n\n\n<p><mark style=\"background-color:var(--global-color-10)\" class=\"has-inline-color\">EXAMPLE 2.16<\/mark> (LOCATION GAME, EXERCISE 9.4 ON PAGE 109). There are two players who simultaneously select numbers between 0 and 1. Suppose player 1 chooses \\(s_{1}\\) and player 2 chooses \\(s_{2}\\). For each profile \\((s_{i}, s_{j})\\), player i&#8217;s payoff is<\/p>\n\n\n\n<p>\\(u_{i}(s_{i}, s_{j})\\) = \\(\\begin{cases} &amp; \\frac{s_{i}+s_{j}}{2} \\text{ if } s_{i} &lt; s_{j} \\ &amp; 1-\\frac{s_{i}+s_{j}}{2} \\text{ if } s_{i} > s_{j} \\ &amp; \\frac{1}{2} \\text{ if } s_{i} = s_{j} \\end{cases}\\)<\/p>\n\n\n\n<p>Compute the Nash equilibria of this game.<\/p>\n\n\n\n<p>Since the player&#8217;s payoff function is <strong><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-global-color-8-color\">discontinuous<\/mark><\/strong>, and thus standard technique does not work<\/p>\n\n\n\n<p>Key observation: \\(s_{i} &lt; s_{j}\\) cannot arise in any eqbm and thus \\(s_{1} = s_{2}\\) is the case<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>\\(s_{1} = s_{2} &lt; \\frac{1}{2}\\) cannot be an eqbm, because each player has an incentive to deviate<\/li>\n\n\n\n<li>\\(s_{1} = s_{2} > \\frac{1}{2}\\) cannot be an eqbm, because each player has an incentive to deviate<\/li>\n<\/ul>\n\n\n\n<p>Hence the only candidate is<\/p>\n\n\n\n<p>\\(s_{1} = s_{2} = \\frac{1}{2}\\)<\/p>\n\n\n\n<p>In political science, this model is used to explain optimal political positions of candidates (known as the <em>median voter theorem<\/em>)<\/p>\n\n\n\n<p><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Reference1: Chang-Koo Chi, (7\/50) Game Theory and Applications 2 \u2013 Nash Equilibrium, Jul 1, 2020,\u00a0<a href=\"https:\/\/youtu.be\/Z0DL4ss-Emw\" rel=\"noopener\">https:\/\/youtu.be\/Z0DL4ss-Emw<\/a><\/li>\n\n\n\n<li>Reference2: Chang-Koo Chi, (8\/50) Game Theory and Applications 2 \u2013 Location Game, Jul 1, 2020,\u00a0<a href=\"https:\/\/youtu.be\/Sbutb6fvSJ8\" rel=\"noopener\">https:\/\/youtu.be\/Sbutb6fvSJ8<\/a><\/li>\n<\/ul>\n\n\n\n<p><\/p>","protected":false},"excerpt":{"rendered":"<p>Learn about Nash equilibrium, a third way to make predictions in normal-form games. We will also see how to find a Nash equilibrium in a Location game.<\/p>","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[5],"tags":[4,57,73,78,52,56,53],"class_list":["post-1078","post","type-post","status-publish","format-standard","hentry","category-game-theory-and-applications","tag-game-theory","tag-isd","tag-jun-3-2023","tag-location-game","tag-may-29-2023","tag-nash-equilibrium","tag-rationalizability"],"_links":{"self":[{"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/posts\/1078"}],"collection":[{"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/comments?post=1078"}],"version-history":[{"count":18,"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/posts\/1078\/revisions"}],"predecessor-version":[{"id":1261,"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/posts\/1078\/revisions\/1261"}],"wp:attachment":[{"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/media?parent=1078"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/categories?post=1078"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/tags?post=1078"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}