<?xml version="1.0" encoding="UTF-8" standalone="yes"?><oembed><version><![CDATA[1.0]]></version><provider_name><![CDATA[Azimuth]]></provider_name><provider_url><![CDATA[https://johncarlosbaez.wordpress.com]]></provider_url><author_name><![CDATA[John Baez]]></author_name><author_url><![CDATA[https://johncarlosbaez.wordpress.com/author/johncarlosbaez/]]></author_url><title><![CDATA[Game Theory (Part&nbsp;2)]]></title><type><![CDATA[link]]></type><html><![CDATA[<p><a href="https://johncarlosbaez.wordpress.com/2013/01/06/game-theory-part-1/">Last time</a> we classified games in a few ways.  This time we&#8217;ll start by looking at a very simple class of games: simultaneous noncooperative two-player games.  </p>
<h3> Simultaneous games </h3>
<p>Remember that in a <b>simultaneous</b> game, each player makes their moves without knowing anything about the other player&#8217;s move.  Thanks to this, we can condense each player&#8217;s move into a single move.  For example, in a card game, if one player lays down a king and then an ace, we can mathematically treat this as a single move, called &#8220;lay down a king and then an ace&#8221;.  So, we&#8217;ll say each player makes just one move&#8212;and they make it without knowing the other player&#8217;s move.  </p>
<p>In class we&#8217;ll play these games like this.  I will decide on my move and write it down on a piece of paper. You&#8217;ll make your move and click either A,B,C,D, or E on your <a href="http://clickers.ucr.edu/clicker/publicStuFAQPage">clicker</a>. </p>
<div align="center">
<img src="https://i1.wp.com/www.reed.edu/cis/mlab/assets/images/clickers1.jpg" />
</div>
<p>Then I&#8217;ll reveal my piece of paper!  At that point, we&#8217;ll each know what both of us did&#8230; but neither of us can change our move.  </p>
<p>So, we each make our move without knowing each other&#8217;s move.</p>
<h3> Two-player games </h3>
<p>Since lots of you will be clicking your clicker at once, you could say there are more than two players in this game.  But your payoff&#8212;the number of points you win or lose&#8212;will depend only on what <i>you</i> did and what <i>I</i> did.  So, we can  treat this game as a bunch of independent two-player games&#8212;and that&#8217;s what we&#8217;ll do.</p>
<h3>  Noncooperative games </h3>
<p>Remember, we use words in funny ways in mathematics!  An &#8216;imaginary&#8217; number is not imaginary in the usual sense; a &#8216;partial&#8217; differential equation isn&#8217;t just part of a differential equation, and so on.  In game theory we use the word &#8216;noncooperative&#8217; in a funny way.  We say a game is <b>noncooperative</b> if the players aren&#8217;t able to form binding commitments.   This means that when we play our games, you and I can&#8217;t talk before the game and promise to do certain things.</p>
<p>There will, however, be games where both of us win if we make the right choice, and both of us lose if we don&#8217;t!   In games like this, if we can figure out how to cooperate without communicating ahead of time and making promises, that&#8217;s allowed! </p>
<h3>  Chicken </h3>
<p>Now let&#8217;s actually look at an example: the game of <a href="http://en.wikipedia.org/wiki/Chicken_%28game%29"><b>chicken</b></a>.  In  this game we drive toward each other at high speed along a one-lane road in the desert.  The one who swerves off the road at the last minute gets called a <i>chicken</i>, and the other driver gets called a <i>hero</i>.  If we both swerve off the road at the last minute, we&#8217;re both called chickens.  But if neither of us does, our cars crash and we both die!</p>
<p>Sounds fun, eh?  </p>
<p>In real life we could each wait as long as possible and see if the other driver starts to swerve.   This makes chicken into a sequential rather than simultaneous game!  You could also promise that you wouldn&#8217;t swerve.  This makes chicken into a cooperative game!</p>
<p>Indeed there are all sorts of variations and complications in real life.  You can see some in the famous movie <i>Rebel Without a Cause</i>, starring James Dean.  Take a look at what happens:</p>
<span class='embed-youtube' style='text-align:center; display: block;'><iframe class='youtube-player' type='text/html' width='420' height='315' src='https://www.youtube.com/embed/u7hZ9jKrwvo?version=3&#038;rel=0&#038;fs=1&#038;showsearch=0&#038;showinfo=1&#038;iv_load_policy=1&#038;wmode=transparent' frameborder='0' allowfullscreen='true'></iframe></span>
<p>This movie version actually involves driving toward a cliff and jumping out at the last possible moment.  </p>
<p>But mathematics, as usual, is about finding problems that are simple enough to state precisely.  So in our simple mathematical version of chicken, we&#8217;ll say each player has just two choices:</p>
<p><b>1</b>: stay on the road.<br />
<b>2</b>: swerve off the road at the last second.</p>
<p>Also, we&#8217;ll express our payoffs in terms of numbers.  A negative payoff is bad, a positive one is good:</p>
<p>&bull;  If either player swerves off the road they get called a chicken, which is bad, so let&#8217;s say they get -1 points.  </p>
<p>&bull; If one player stays on the road and other swerves off the road, the one who stays on the road gets called a hero, so let&#8217;s say they get 1 point.</p>
<p>&bull; If both players stay on the road they both die, so let&#8217;s say they both get -10 points.</p>
<p>We can summarize all this in a little table:</p>
<div align="center">
<table border="0">
<tr>
<td></td>
<td align="center"><font color="red"><b>1</b></font></td>
<td align="center"><font color="red"><b>2</b></font></td>
</tr>
<tr>
<td><b>1 &nbsp;&nbsp;</b></td>
<td align="center">(-10,<font color="red">-10</font>)&nbsp;&nbsp;</td>
<td align="center">(1,<font color="red">-1</font>)</td>
</tr>
<tr>
<td><b>2</b></td>
<td align="center">(-1,<font color="red">1</font>)</td>
<td align="center">(-1,<font color="red">-1</font>)</td>
</tr>
</table>
</div>
<p>Let&#8217;s say the players are you and me.  Your choices 1 and 2 are shown in in black: you get to pick which row of the table we use.  <font color="red">My choices 1 and 2 are in red: I get to pick which column of the table we use.</font></p>
<p>There are four possible ways we can play the game.  For each of the four possibilities we get a pair of numbers.  The first number, in black, is your payoff.   <font color="red">The second, in red, is my payoff.</font></p>
<p>For example, suppose you choose <b>1</b> and I choose <font color="red"><b>2</b></font>.  Then you&#8217;re a hero and I&#8217;m a chicken.   So, your payoff is 1 and mine is -1.   That&#8217;s why we get the pair of numbers (1,<font color="red">-1</font>) in the 1st row and 2nd column of this table.</p>
<p>Now let&#8217;s play this game a bit!  Later we&#8217;ll study it in different ways.</p>
<h3> Rock-paper-scissors </h3>
<p>Here&#8217;s another famous game: <a href="http://en.wikipedia.org/wiki/Rock-paper-scissors"><b>rock-paper-scissors</b></a>.  </p>
<div align="center"><a href="http://en.wikipedia.org/wiki/Rock-paper-scissors"><img width="450" src="https://i2.wp.com/upload.wikimedia.org/wikipedia/commons/e/e6/Rock_paper_scissors.jpg" /></a></div>
<p>Each player can choose either <b>rock</b>, <b>paper</b> or <b>scissors</b>.   Paper beats rock, scissors beats paper, and rock beats scissors.  In these cases let&#8217;s say the winner gets a payoff of 1, while the loser gets a payoff of -1.   If both players make the same choice, it&#8217;s a tie, so let&#8217;s say both players get a payoff of 0.  </p>
<p>Here&#8217;s a table that describes this game:</p>
<div align="center">
<table border="0">
<tr>
<td></td>
<td align="center"><font color="red"><b>rock</b></font></td>
<td align="center"><font color="red"><b>paper</b></font></td>
<td align="center"><font color="red"><b>scissors</b></font></td>
</tr>
<tr>
<td><b>rock &nbsp;&nbsp;</b></td>
<td align="center">(0,<font color="red">0</font>)&nbsp;&nbsp;</td>
<td align="center">(-1,<font color="red">1</font>)&nbsp;&nbsp;</td>
<td align="center">(1,<font color="red">-1</font>)&nbsp;&nbsp;</td>
</tr>
<tr>
<td><b>paper &nbsp; &nbsp;</b></td>
<td align="center">(1,<font color="red">-1</font>)&nbsp;&nbsp;</td>
<td align="center">(0,<font color="red">0</font>)&nbsp;&nbsp;</td>
<td align="center">(-1,<font color="red">1</font>)&nbsp;&nbsp;</td>
</tr>
<tr>
<td><b>scissors &nbsp; &nbsp;</b></td>
<td align="center">(-1,<font color="red">1</font>)&nbsp;&nbsp;</td>
<td align="center">(1,<font color="red">-1</font>)&nbsp;&nbsp;</td>
<td align="center">(0,<font color="red">0</font>)&nbsp;&nbsp;</td>
</tr>
</table>
</div>
<p>Your choices and payoffs are in black, while mine are in red.  </p>
<p>For example, if you choose <b>rock</b> and I choose <b><font color="red">paper</font></b>, we can look up what happens, and it&#8217;s (-1,<font color="red">1</font>).  That means your payoff is -1 while mine is 1.  So I win!  <img src="https://i2.wp.com/math.ucr.edu/home/baez/emoticons/devil.gif" alt="" /></p>
<p>To make this table look more mathematical, we can make up numbers for our choices:</p>
<p><b>1</b>: rock<br />
<b>2</b>: paper<br />
<b>3</b>: scissors</p>
<p>Then the table looks like this:</p>
<div align="center">
<table border="0">
<tr>
<td></td>
<td align="center"><font color="red"><b>1</b></font></td>
<td align="center"><font color="red"><b>2</b></font></td>
<td align="center"><font color="red"><b>3</b></font></td>
</tr>
<tr>
<td><b>1 &nbsp;&nbsp;</b></td>
<td align="center">(0,<font color="red">0</font>)&nbsp;&nbsp;</td>
<td align="center">(-1,<font color="red">1</font>)&nbsp;&nbsp;</td>
<td align="center">(1,<font color="red">-1</font>)&nbsp;&nbsp;</td>
</tr>
<tr>
<td><b>2</b></td>
<td align="center">(1,<font color="red">-1</font>)&nbsp;&nbsp;</td>
<td align="center">(0,<font color="red">0</font>)&nbsp;&nbsp;</td>
<td align="center">(-1,<font color="red">1</font>)&nbsp;&nbsp;</td>
</tr>
<tr>
<td><b>3</b></td>
<td align="center">(-1,<font color="red">1</font>)&nbsp;&nbsp;</td>
<td align="center">(1,<font color="red">-1</font>)&nbsp;&nbsp;</td>
<td align="center">(0,<font color="red">0</font>)&nbsp;&nbsp;</td>
</tr>
</table>
</div>
<p>Let&#8217;s play this game a bit, and then discuss it!</p>
<h3> Normal form </h3>
<p>In the games we&#8217;re studying now, each player can make various choices.  In game theory these choices are often called <b>pure strategies</b>.  We&#8217;ll see why later on in this course.</p>
<p>In our examples so far, each player has the same set of pure strategies.    But this is not required!   You could have some set of pure strategies and I could have some other set.  </p>
<p>For now let&#8217;s only think about games where we both have a <i>finite</i> set of pure strategies.  For example, you could have 4 pure strategies and I could have 2.  Then we could have a game like this:</p>
<div align="center">
<table border="0">
<tr>
<td></td>
<td align="center"><font color="red"><b>1</b></font></td>
<td align="center"><font color="red"><b>2</b></font></td>
</tr>
<tr>
<td><b>1 &nbsp;&nbsp;</b></td>
<td align="center">(0,<font color="red">0</font>)&nbsp;&nbsp;</td>
<td align="center">(-1,<font color="red">1</font>)&nbsp;&nbsp;</td>
</tr>
<tr>
<td><b>2</b></td>
<td align="center">(2,<font color="red">-1</font>)&nbsp;&nbsp;</td>
<td align="center">(0,<font color="red">0</font>)&nbsp;&nbsp;</td>
</tr>
<tr>
<td><b>3</b></td>
<td align="center">(-2,<font color="red">1</font>)&nbsp;&nbsp;</td>
<td align="center">(1,<font color="red">-1</font>)&nbsp;&nbsp;</td>
</tr>
<tr>
<td><b>4</b></td>
<td align="center">(0,<font color="red">1</font>)&nbsp;&nbsp;</td>
<td align="center">(2,<font color="red">0</font>)&nbsp;&nbsp;</td>
</tr>
</table>
</div>
<p>This way of describing a game using a table of pairs of numbers is called <b>normal form</b>, and you can read about it here:</p>
<p>&bull; <a href="http://en.wikipedia.org/wiki/Normal-form_game">Normal-form game</a>, Wikipedia.</p>
<p>There are other ways to describe the same information.  For example, instead of writing </p>
<div align="center">
<table border="0">
<tr>
<td></td>
<td align="center"><font color="red"><b>1</b></font></td>
<td align="center"><font color="red"><b>2</b></font></td>
</tr>
<tr>
<td><b>1 &nbsp;&nbsp;</b></td>
<td align="center">(0,<font color="red">0</font>)&nbsp;&nbsp;</td>
<td align="center">(-1,<font color="red">1</font>)&nbsp;&nbsp;</td>
</tr>
<tr>
<td><b>2</b></td>
<td align="center">(2,<font color="red">-1</font>)&nbsp;&nbsp;</td>
<td align="center">(0,<font color="red">0</font>)&nbsp;&nbsp;</td>
</tr>
<tr>
<td><b>3</b></td>
<td align="center">(-2,<font color="red">1</font>)&nbsp;&nbsp;</td>
<td align="center">(1,<font color="red">-1</font>)&nbsp;&nbsp;</td>
</tr>
<tr>
<td><b>4</b></td>
<td align="center">(0,<font color="red">1</font>)&nbsp;&nbsp;</td>
<td align="center">(2,<font color="red">0</font>)&nbsp;&nbsp;</td>
</tr>
</table>
</div>
<p>we can write everything in black:</p>
<div align="center">
<table border="0">
<tr>
<td></td>
<td align="center"><font color="black"><b>1</b></font></td>
<td align="center"><font color="black"><b>2</b></font></td>
</tr>
<tr>
<td><b>1 &nbsp;&nbsp;</b></td>
<td align="center">(0,<font color="black">0</font>)&nbsp;&nbsp;</td>
<td align="center">(-1,<font color="black">1</font>)&nbsp;&nbsp;</td>
</tr>
<tr>
<td><b>2</b></td>
<td align="center">(2,<font color="black">-1</font>)&nbsp;&nbsp;</td>
<td align="center">(0,<font color="black">0</font>)&nbsp;&nbsp;</td>
</tr>
<tr>
<td><b>3</b></td>
<td align="center">(-2,<font color="black">1</font>)&nbsp;&nbsp;</td>
<td align="center">(1,<font color="black">-1</font>)&nbsp;&nbsp;</td>
</tr>
<tr>
<td><b>4</b></td>
<td align="center">(0,<font color="black">1</font>)&nbsp;&nbsp;</td>
<td align="center">(2,<font color="black">0</font>)&nbsp;&nbsp;</td>
</tr>
</table>
</div>
<p>All the information is still there!  It&#8217;s just a bit harder to see.  The colors are just to make it easier on you.</p>
<p>Mathematicians like <a href="http://en.wikipedia.org/wiki/Matrix_%28mathematics%29">matrices</a>, which are rectangular boxes of numbers.  So, it&#8217;s good to use these to describe normal-form games.   To do this we take our table and chop it into two.  We write one matrix for your payoffs:</p>
<div align="center">
<img src='https://s0.wp.com/latex.php?latex=A+%3D+%5Cleft%28+%5Cbegin%7Barray%7D%7Brr%7D+0+%26+-1+%5C%5C+2+%26+0+%5C%5C+-2+%26+1+%5C%5C+0+%26+2+%5Cend%7Barray%7D+%5Cright%29+&#038;bg=ffffff&#038;fg=000&#038;s=0' alt='A = &#92;left( &#92;begin{array}{rr} 0 &amp; -1 &#92;&#92; 2 &amp; 0 &#92;&#92; -2 &amp; 1 &#92;&#92; 0 &amp; 2 &#92;end{array} &#92;right) ' title='A = &#92;left( &#92;begin{array}{rr} 0 &amp; -1 &#92;&#92; 2 &amp; 0 &#92;&#92; -2 &amp; 1 &#92;&#92; 0 &amp; 2 &#92;end{array} &#92;right) ' class='latex' />
</div>
<p>and one for mine:</p>
<div align="center">
<img src='https://s0.wp.com/latex.php?latex=B+%3D+%5Cleft%28+%5Cbegin%7Barray%7D%7Brr%7D+0+%26+1+%5C%5C+-1+%26+0+%5C%5C+1+%26+-1+%5C%5C+1+%26+0+%5Cend%7Barray%7D+%5Cright%29+&#038;bg=ffffff&#038;fg=000&#038;s=0' alt='B = &#92;left( &#92;begin{array}{rr} 0 &amp; 1 &#92;&#92; -1 &amp; 0 &#92;&#92; 1 &amp; -1 &#92;&#92; 1 &amp; 0 &#92;end{array} &#92;right) ' title='B = &#92;left( &#92;begin{array}{rr} 0 &amp; 1 &#92;&#92; -1 &amp; 0 &#92;&#92; 1 &amp; -1 &#92;&#92; 1 &amp; 0 &#92;end{array} &#92;right) ' class='latex' />
</div>
<p>The number in the ith row and jth column of the matrix <img src='https://s0.wp.com/latex.php?latex=A&#038;bg=ffffff&#038;fg=000&#038;s=0' alt='A' title='A' class='latex' /> is called <img src='https://s0.wp.com/latex.php?latex=A_%7Bi+j%7D&#038;bg=ffffff&#038;fg=000&#038;s=0' alt='A_{i j}' title='A_{i j}' class='latex' />, and similarly for <img src='https://s0.wp.com/latex.php?latex=B&#038;bg=ffffff&#038;fg=000&#038;s=0' alt='B' title='B' class='latex' />.  For example, if you pick choice 3 in this game and I pick choice 2, your payoff is</p>
<div align="center">
<img src='https://s0.wp.com/latex.php?latex=A_%7B32%7D+%3D+1&#038;bg=ffffff&#038;fg=000&#038;s=0' alt='A_{32} = 1' title='A_{32} = 1' class='latex' />
</div>
<p>and my payoff is</p>
<div align="center">
<img src='https://s0.wp.com/latex.php?latex=B_%7B32%7D+%3D+-1&#038;bg=ffffff&#038;fg=000&#038;s=0' alt='B_{32} = -1' title='B_{32} = -1' class='latex' />
</div>
<h3> Definition </h3>
<p>Let&#8217;s summarize everything we&#8217;ve learned today!  Remember, an <img src='https://s0.wp.com/latex.php?latex=m+%5Ctimes+n&#038;bg=ffffff&#038;fg=000&#038;s=0' alt='m &#92;times n' title='m &#92;times n' class='latex' /> matrix has <img src='https://s0.wp.com/latex.php?latex=m&#038;bg=ffffff&#038;fg=000&#038;s=0' alt='m' title='m' class='latex' /> rows and <img src='https://s0.wp.com/latex.php?latex=n&#038;bg=ffffff&#038;fg=000&#038;s=0' alt='n' title='n' class='latex' /> columns.  So, we can say:</p>
<p><b>Definition.</b>  A <b>2-player normal-form game</b> consists of two <img src='https://s0.wp.com/latex.php?latex=m+%5Ctimes+n&#038;bg=ffffff&#038;fg=000&#038;s=0' alt='m &#92;times n' title='m &#92;times n' class='latex' /> matrices of real numbers, <img src='https://s0.wp.com/latex.php?latex=A&#038;bg=ffffff&#038;fg=000&#038;s=0' alt='A' title='A' class='latex' /> and <img src='https://s0.wp.com/latex.php?latex=B.&#038;bg=ffffff&#038;fg=000&#038;s=0' alt='B.' title='B.' class='latex' /> </p>
<p>This definition is very terse and abstract.  That&#8217;s what mathematicians like!  But we have to unfold it a bit to understand it.</p>
<p>Let&#8217;s call you &#8216;player A&#8217; and me &#8216;player B&#8217;.  Then the idea here is that player A can choose among pure strategies <img src='https://s0.wp.com/latex.php?latex=i+%3D+1%2C2%2C%5Cdots+%2C+m&#038;bg=ffffff&#038;fg=000&#038;s=0' alt='i = 1,2,&#92;dots , m' title='i = 1,2,&#92;dots , m' class='latex' /> while player B can choose among pure strategies <img src='https://s0.wp.com/latex.php?latex=j+%3D+1%2C2%2C%5Cdots%2C+n.&#038;bg=ffffff&#038;fg=000&#038;s=0' alt='j = 1,2,&#92;dots, n.' title='j = 1,2,&#92;dots, n.' class='latex' />   Suppose player A makes choice <img src='https://s0.wp.com/latex.php?latex=i&#038;bg=ffffff&#038;fg=000&#038;s=0' alt='i' title='i' class='latex' /> and player B makes choice <img src='https://s0.wp.com/latex.php?latex=j.&#038;bg=ffffff&#038;fg=000&#038;s=0' alt='j.' title='j.' class='latex' />  Then the payoff to player A is <img src='https://s0.wp.com/latex.php?latex=A_%7Bi+j%7D%2C&#038;bg=ffffff&#038;fg=000&#038;s=0' alt='A_{i j},' title='A_{i j},' class='latex' /> and the payoff to player B is <img src='https://s0.wp.com/latex.php?latex=B_%7Bi+j%7D.&#038;bg=ffffff&#038;fg=000&#038;s=0' alt='B_{i j}.' title='B_{i j}.' class='latex' /></p>
]]></html><thumbnail_url><![CDATA[https://i1.wp.com/www.reed.edu/cis/mlab/assets/images/clickers1.jpg?fit=440%2C330]]></thumbnail_url><thumbnail_height><![CDATA[240]]></thumbnail_height><thumbnail_width><![CDATA[360]]></thumbnail_width></oembed>