{"id":813,"date":"2023-05-27T00:49:44","date_gmt":"2023-05-26T15:49:44","guid":{"rendered":"https:\/\/saraheee.com\/?p=813"},"modified":"2023-06-06T15:20:47","modified_gmt":"2023-06-06T06:20:47","slug":"game-theory-1-chap03-normal-form-games-basic-concepts","status":"publish","type":"post","link":"https:\/\/saraheee.com\/ko\/2023\/05\/game-theory-1-chap03-normal-form-games-basic-concepts\/","title":{"rendered":"Game Theory 1 \u2013 chap03. Normal-form games, basic concepts"},"content":{"rendered":"<h4 class=\"wp-block-heading\">Review<\/h4>\n\n\n\n<p><strong>1. Preliminaries<\/strong><br>1.1 Choice under Uncertainty: Expected Utility Theory<br>1.2 Common Knowledge<\/p>\n\n\n\n<p><strong>2. Normal Form Games<\/strong><br>2.1 Basic Concepts (Chapter 3 &amp; 4)<br>2.2 Dominance and Interated Dominance (Chapter 6 &amp; 7)<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Part 1: Analysis of Normal-form Games<\/h2>\n\n\n\n<p>In Part I, we consider games in which players <strong><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-global-color-8-color\">simultaneously<\/mark><\/strong> choose actions and receive payoffs that depend on the profile of their actions.<br>Moreover, for each player, there is <strong><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-global-color-8-color\">no<\/mark><\/strong> other source of <strong><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-global-color-8-color\">uncertainty<\/mark><\/strong> on the payoff than her rivals&#8217; choices.<\/p>\n\n\n\n<p><mark style=\"background-color:var(--base)\" class=\"has-inline-color\">Static games with complete information, or normal-form games<\/mark><\/p>\n\n\n\n<p>We study how to describe and how to solve a normal-form game (about 3 lectures)<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Normal-Form Games<\/h3>\n\n\n\n<p>A game in general has the following 4 basic elements:<\/p>\n\n\n\n<p>(i) a list of players,<br>(ii) a complete description of what each player can do,<br>(iii) a description of what each player knows when he\/she acts, and<br>(iv) a specification of the players&#8217; preferences over outcomes<\/p>\n\n\n\n<p><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-global-color-15-color\">About the information set of interactive knowledge (iii)<\/mark><\/p>\n\n\n\n<p>Two ways of describing these 4 elements,<\/p>\n\n\n\n<p><mark style=\"background-color:var(--base)\" class=\"has-inline-color\">the normal-form and extensive-form representation<\/mark><\/p>\n\n\n\n<p>A two-player normal-form game consists of<\/p>\n\n\n\n<p>(i) a set of <strong><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-global-color-8-color\">players<\/mark><\/strong>, {l,2}<br>(ii) a set of <strong><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-global-color-8-color\">strategies<\/mark><\/strong> available to each player, \\(S_{1}\\) and \\(S_{2}\\)<br>(iii) a vNM <strong><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-global-color-8-color\">payoff function<\/mark><\/strong> for each player, \\(u_{1}(s_{1}, s_{2})\\) and \\(u_{2}(s_{1}, s_{2})\\).<\/p>\n\n\n\n<p><mark style=\"background-color:var(--global-color-10)\" class=\"has-inline-color\">EXAMPLE 2.1 (PRISONER&#8217;S DILEMMA)<\/mark>.<\/p>\n\n\n\n<p>Two prisoners are each asked to either<br>(i) betray the other by testifying that the other committed the crime, or<br>(ii) cooperate with the other by remaining silent.<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>If both betray the other, each of them serves 2 years in prison.<\/li>\n\n\n\n<li>If only one betrays, he is set free and the other serves 3 years in prison.<\/li>\n\n\n\n<li>If both cooperate and remain silent, each serves 1 year in prison.<\/li>\n<\/ul>\n\n\n\n<figure class=\"wp-block-table aligncenter\"><table><tbody><tr><td><\/td><td><\/td><td>player 2&#8217;s choice<\/td><td>player 2&#8217;s choice<\/td><\/tr><tr><td><\/td><td><\/td><td>B<\/td><td>C<\/td><\/tr><tr><td>player 1&#8217;s choice<\/td><td>B<\/td><td>-2, -2<\/td><td>0, -3<\/td><\/tr><tr><td>player 1&#8217;s choice<\/td><td>C<\/td><td>-3, 0<\/td><td>-1, -1<\/td><\/tr><\/tbody><\/table><figcaption class=\"wp-element-caption\">Table: Normal Form Representation of Prisoner&#8217;s Dilemma<\/figcaption><\/figure>\n\n\n\n<p><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-global-color-15-color\">This example is irrelevant to (iii) of the 4 basic elements, since the information each player has is the same<\/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 there are a finite number of strategies that each player can choose from, you can represent them as a matrix like this.<br>What if there are infinite?<\/mark><\/p>\n\n\n\n<p><mark style=\"background-color:var(--global-color-10)\" class=\"has-inline-color\">EXAMPLE 2.2 (FIRST-PRICE AUCTIONS)<\/mark>.<\/p>\n\n\n\n<p>One object (indivisible) is to be auctioned off to n bidders. Each bidder i&#8217;s valuation of the object is \\(v_{i}\\). The bidders simultaneously submit their bids, and the object is awarded to the highest bidder in exchange for a payment.<\/p>\n\n\n\n<p><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-global-color-15-color\">Each bidder makes a bid, the highest bidder gets the object<\/mark><\/p>\n\n\n\n<p>\\(V_{1}, V_{2}, V_{3}, &#8230;, V_{n}\\)<\/p>\n\n\n\n<p>1) N = {1, 2, 3, &#8230;, n}<br>2) \\(S_{i}\\) = [0 , \u221e)<br>3) \\(u_{i}(s)\\) = \\(v_{i} &#8211; s_{i}\\) (if \\(s_{i} &gt; max(s_{j}) and s_{i} != s_{j}\\))<br>                    0 in O.W(otherwise)<br>(s = \\(s_{1}, s_{2}, &#8230;, s_{n}\\))<\/p>\n\n\n\n<p><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-global-color-15-color\">N: participants, S: strategies available in the auction<\/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\">Types of strategies: Pure(execute any one strategy unconditionally), Mixed(stochastically organize the strategies you can choose from)<\/mark><\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Mixed Strategies<\/h3>\n\n\n\n<p>Let \\(\\Delta S_{i}\\) denote the set of probability distributions over the strategy space \\(S_{i}\\), i.e.,<\/p>\n\n\n\n<p><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-global-color-15-color\">\\(\\Delta s_{i}\\) = { p : \\(S_{i}\\) \u2192 [0, 1] | \\(\\sum_{s_{i} \\in S_{i}} p(s_{i})\\) = 1 }<br>\\(S_{1}\\) = {L, C, R}<br>\\(\\Delta S_{1}\\) = { p \u2208 [0, 1], q \u2208 [0, 1] | 0 \u2264 p +q \u2264 1 }<\/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\">\\(S_{i}\\) is a probability, so it is positive and cannot be greater than 1.<br>The sum of all possible counts must equal 1.<br>So the probability of choosing \\(s_{i}\\) is 1 for all i when added together.<\/mark><\/p>\n\n\n\n<p>Each element \\(\\sigma_{i}\\) of \\(\\Delta S_{i}\\) represents a mixed strategy for player i,<\/p>\n\n\n\n<p><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-global-color-15-color\">In general, S denotes a pure strategy and O denotes a mixed strategy.<br>The probability that player i chooses strategy s is given by<\/mark><\/p>\n\n\n\n<p>\\(\\sigma_{i}\\)(s) = Pr(i chooses strategy s \u2208 \\(S_{i}\\)<\/p>\n\n\n\n<p>One underlying assumption of mixed strategies is, players randomize <strong><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-global-color-8-color\">independently<\/mark><\/strong>, put differently, learning what P1 played conveys no information about what P2 did<\/p>\n\n\n\n<p>Given \\((\\sigma_{1}, \\sigma_{2})\\), a strategy profile \\(s_{1}, s_{2}\\) is chosen with probability<\/p>\n\n\n\n<p>\\(\\sigma_{1}(s_{1}) \\cdot \\sigma_{2}(s_{2})\\)<\/p>\n\n\n\n<p><mark style=\"background-color:var(--global-color-10)\" class=\"has-inline-color\">EXAMPLES 2.3. Battle of the Sexes<\/mark><\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td><\/td><td>Opera<\/td><td>Movie<\/td><\/tr><tr><td>Opera<\/td><td>2, 1<\/td><td>0, 0<\/td><\/tr><tr><td>Movie<\/td><td>0, 0<\/td><td>1, 2<\/td><\/tr><\/tbody><\/table><figcaption class=\"wp-element-caption\">Battle of the Sexes<\/figcaption><\/figure>\n\n\n\n<p>Suppose that P1 plays \\(\\sigma_{1}\\) = (3\/4, 1\/4) and P2 plays \\(\\sigma_{2}\\) = (1\/4, 3\/4)<\/p>\n\n\n\n<p>Given this profile (\\(\\sigma_{1}, \\sigma_{2})\\), (Opera, Movie) is played with probability<\/p>\n\n\n\n<p>\\(\\sigma_{1}\\)(Opera) x \\(\\sigma_{2}\\)(Movie) = \\(\\frac{9}{16}\\)<\/p>\n\n\n\n<p>The complete distribution over strategy profiles (= possible outcomes) is<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td><\/td><td>Opera<\/td><td>Movie<\/td><\/tr><tr><td>Opera<\/td><td>3\/4 * 1\/4 = 3\/16<\/td><td>3\/4 * 3\/4 = 9\/16<\/td><\/tr><tr><td>Movie<\/td><td>1\/4 * 1\/4 = 1\/16<\/td><td>1\/4 * 3\/4 = 3\/16<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>When player i has two strategies, e.g., \\(S_{i}\\) = {L,R}, the set of his possible mixed strategies \\(\\Delta S_{i}\\) is the simplex in \\(\\Re^{2}\\), that is an interval<\/p>\n\n\n\n<p><mark style=\"background-color:var(--base)\" class=\"has-inline-color\">Triangle with O L R as each vertex<\/mark><\/p>\n\n\n\n<p>When player i has three strategies, the set of mixed strategies becomes the simplex of \\(\\Re^{3}\\), that is an equilateral triangle<\/p>\n\n\n\n<p><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-global-color-15-color\">All mixed and pure strategies can be represented by an equilateral triangle if there are three possible strategies, or by an inteval if there are two.<\/mark><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Reference1: Chang-Koo Chi, (3\/50) Game Theory and Applications 1 &#8211; Normal-form games, basic concepts, Jul 1, 2020,&nbsp;<a href=\"https:\/\/youtu.be\/XDSyRmXMXUg\" rel=\"noopener\">https:\/\/youtu.be\/XDSyRmXMXUg<\/a><\/li>\n\n\n\n<li>Reference2: Chang-Koo Chi, (4\/50) Game Theory and Applications 2 &#8211; Normal-form games, basic concepts, Jul 1, 2020, 00:00-05:36,&nbsp;<a href=\"https:\/\/youtu.be\/YzD3DoYagYg\" rel=\"noopener\">https:\/\/youtu.be\/YzD3DoYagYg<\/a><\/li>\n<\/ul>\n\n\n\n<p><\/p>","protected":false},"excerpt":{"rendered":"<p>Analyze the four elements of a normal form game, consider the payoff function, and work through an example. We will also learn about mixed strategies, which represent probability distributions over the strategy space.<\/p>","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[5],"tags":[21,4,26,24,10],"class_list":["post-813","post","type-post","status-publish","format-standard","hentry","category-game-theory-and-applications","tag-basic-concepts","tag-game-theory","tag-may-25-2023","tag-mixed-strategies","tag-normal-form-games"],"_links":{"self":[{"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/posts\/813"}],"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=813"}],"version-history":[{"count":40,"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/posts\/813\/revisions"}],"predecessor-version":[{"id":1515,"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/posts\/813\/revisions\/1515"}],"wp:attachment":[{"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/media?parent=813"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/categories?post=813"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/saraheee.com\/ko\/wp-json\/wp\/v2\/tags?post=813"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}