×

### Let's log you in.

or

Don't have a StudySoup account? Create one here!

×

### Create a StudySoup account

#### Be part of our community, it's free to join!

or

##### By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here

by: Floy Kub

31

0

49

# Game Theory STAT 155

Floy Kub

GPA 3.64

Staff

### Almost Ready

These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

### Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

×
Unlock Preview

### Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

COURSE
PROF.
Staff
TYPE
Class Notes
PAGES
49
WORDS
KARMA
25 ?

## Popular in Statistics

This 49 page Class Notes was uploaded by Floy Kub on Thursday October 22, 2015. The Class Notes belongs to STAT 155 at University of California - Berkeley taught by Staff in Fall. Since its upload, it has received 31 views. For similar materials see /class/226734/stat-155-university-of-california-berkeley in Statistics at University of California - Berkeley.

×

## Reviews for Game Theory

×

×

### What is Karma?

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/22/15
Stat 155 Game theory Yuval Peres Lectures 232425 Fall 2004 General sum games We now turn to discuss the theory of general sum games in which some degree of cooperation between the players may be optimal A general sum game is given in strategic form by two matrices A and B whose entries give the payoffs of given joint pure strategies to each of the two players Here are two examples Example the prisoner s dilemma Two suspects are held and questioned by police who ask each of them to confess or to remain silent If both confess they will each spend a year in prison If both remain silent ve years to each is the sentence If one confesses and the other is silent then the rst is sentenced to ten years and the other goes free Writing the payoff as the number of years that remain in the following decade apart from those spent in prison we obtain the following payoff matrix H s c I s 55 010 0 100 11 The pay off matrices for players I and H are the 2 X 2 matrices given by the collection of rst or second entries in each of the vectors in the above matrix If the players only play one round then there is an argument involving domination that each should confess in the sense that the outcome she secures is preferable to the alternative of remaining silent whatever the behaviour of the other player However this outcome is much worse than that secured for each player by both remaining silent In a onceonly game the globally preferable outcome of each remaining silent could only occur were each player to suppress the desire to achieve the best outcome in sel sh terms In games with repeated play ending at a known time the same applies by an argument of backward induction In games with repeated play ending at a random time however the globally preferable solution may arise even with sel sh play Example the battle of the sexes The wife wants to head to the opera but the husband yearns instead to spend an evening watching baseball Neither is satis ed by an evening without the other In numbers here s the scenario Lectures 23 24 25 2 I 0 471 B 0 0 so that player I is the wife and II the husband Player I can guarantee a safety value of maxpeAn minqun pTBq where B denotes the matrix of payoffs received by player I However a minimax approach is unsuitable in this context We now introduce a central notion for the study of general sum games De nition 1 Nash equilbrium A pair of vecotrs wy with ac 6 Am and y E An de ne a Nash equilibrium if no players gains by deviating unilaterally from it That is waAyx 2 wTAy4lt for all x 6 Am and waBy 2 wTBy4lt for all y E An There can be many Nash equilibria in a game If x and y are unit vectors with a 1 in some coordiante and O in the others then the equilbrium is called pure ln battle of the sexes there are two pure equilibria these are BB and 00 There is also a mixed equilibrium 4515 and 1545 having the low value of 45 In this example it is quite arti cial to suppose that the two players cannot discuss and that there are not repeated plays Example a case of hideandseek Consider the hide and seek game with payoff matrix B given by 1 12 1 3 1 5 This means that the matrix D is equal to 1 2 3 5 To determine a minimal cover of the matrix D consider rst a cover that has all of its mass on the rows u 2 5 and 1 00 Note that rows 1 and 2 know only column 2 according to the de nition of knowing introduced in the analysis of this game Modifying the vectors u and 1 according to the rule given in this analysis we obtain updated vectors u 14 and 1 01 whose sum is 6 equal to the expression max7r D7r obtained by choosing the permutation 7r id Lectures 23 24 25 3 An optimal strategy for the hider is to play p1 1 16 and p22 56 An optimal strategy for the seeker consists of playing qrow1 16 qrow2 23 and qcol2 16 The value of the game is 16 Another example lions and antelopes Antelopes have been observed to jump energetically when a lion nearby seems liable to hunt them Why do they expend energy in this way One theory was that the antelope were signalling danger to others at some dis tance in a community spirited gesture However the antelope have been observed doing this all alone The currently accepted theory is that the signal is intended for the lion to indicate that the antelope is in good health and is unlikely to be caught in a chase We now consider a simple model where two cheetahs are giving chase to two antelope The cheetahs will catch any antelope they choose If they choose the same one they must share the spoils If they catch one without the other cheetah doing likewise the catch is unshared There is a large antelope and a small one that are worth I and s to the cheetahs Here is the matrix of payoffs H L S l L l2l2 ls S sl s2s2 lfl 2 25 the rst row dominates the second and likewise the columns Each cheetah chases the larger antelope If s lt l lt 25 and the rst cheetach chases the large antelope with probability x then the expected payoff to the second cheetah of chasing the larger antelope is equal to 1 ix 17 wl and that arising from chasing the smaller antelope is S 1 7 65 w 2 A symmetric mixed Nash equilibrium arises at that value of w for which these last two quantities are equal because at any other value of w player I would have cause to deviate from the mixed strategy 531 7 w to the better of the pure strategies available We nd that 2175 w 5 Symmetric mixed Nash equilibria are of particular interest It has been experimentally veri ed that in some biological situations systems approach such an equilibria presumably by mechanisms of natural selection Lectures 23 24 25 4 General sum games with k 2 2 players It doesn t make sense to talk about zero sum games when there are more than two players The notion of a Nash equilibrium however can be used in this context We now describe formally the set up of a game with k 2 2 players Each player i has a set Si of pure strategies If for each i E 1 k player i uses strategy li 6 Si then player 9 has a payoff of Fjl1 lk where we are given functions F7231 X32 gtlt gtltSkall forj 1k Example an ecology game Three rms will either pollute a lake in the following year or purify it They pay 1 unit to purify but it is free to pollute If two or more pollute then the water in the lake is useless and each rm must pay 3 units to obtain the water that they need from elsewhere If at most one rm pollutes than the water is usable and the rms incur no further costs Assuming that rm I puri es the cost matrix is ll Po Pu l Pu 101 111 Po 3331 011 lf rm I pollutes then it is ll Po Pu l Pu 3133 110 Po 333 3313 To discuss the game we rstly introduce the notion of Nash equilibrium in the context of games with several players De nition 2 A pure Nash equilibrium in a kperson game is a set of pure strategies for each of the players Ifl631gtltgtltSk such that for eachj E 1k and lj F703z1zjz1mzgt sMixz1zz1zzgtr More generally a mixed Nash equilibrium is a collection of k probability vectors Xi each of length ISZ39I such that 3021XHX2271XI gF21XHXjXj1Xk for each probability vector X of length ISjI We have written FjX1X2Xk Z X1l1XklkFl1lk l1631lk63k Lectures 23 24 25 5 De nition 3 A game is symmetric if for every i0j0 E 1 d there is a permutation 7r of the set 1 d such that 7ri0 jg and F7ril7r1739 r r 717419 Fi117 r r r 71k For this de nition to make sense we are in fact requiring that the strategy sets of the players coincide We will prove the following result Theorem 1 Nash s theorem Every game has a Nash equilibrium Note that the equilbrium may be mixed Corollary 1 In a symmetric game there is a symmetric Nash equilibrium Returning to the ecology game note that the pure equilibria consist of each rm polluting or one of the three rms polluting and the remaining two purifying We now seek a symmetric mixed equilibrium There is just one parameter p 6 01 which is the probability that a given rm will purify the lake For rm 1 the expected cost from purifying is equal to 1317p2 and from polluting is 31 7 p2 Equating these two expressions we obtain that p is either one of the two values 12 xgG or 12 7 xgES each of which lies in the interval 01 These values correspond to the symmetric mixed equilibria for the game Stat 155 Game theory Yuval Peres Lectures 111213 Fall 2004 A betting game Suppose that there are two players a hider and a chooser The hider has two coins At the beginning of any given turn he decides either to place one coin in his left hand or two coins in his right He does so unseen by the chooser The chooser then selects one of his hands and wins the coins hidden there That means he may get nothing if the hand is empty or one or two coins How should each of the agents play if he wants to maximise his gain or minimize his loss Calling the chooser player I and the hider player II we record the outcomes in a normal or strategic form H L R l L 2 O R O 1 If the players choose non random strategies and each seeks to minimise his worst loss or to assure his gain what are these amounts In general consider a pay off matrix ammm so that player I may play one ofm possible plays and player II one of 71 possibilities The meaning of the entries is that 127 is the amount that II pays I in the event that I plays 2 and II plays 9 Let s calculate the assured payment for player I if pure strategies are used If he announces to player II that he will play 2 then II will play that j for which minj 17 is attained If he were announcing his choice beforehand player I would therefore play that 2 attaining maxi minj aij On the other hand if player II has to annonce his intention for the coming round to player I then a similar argument shows that he plays 9 where j attains mini max aij In the example the assured value for II is 1 and the assured value for I is zero In plain words the hider can assure only losing one unit by placing one coin in his left hand whereas the chooser knows that he will never lose anything by playing It s always true that the assured values satisfy the inequality minj 17 2 maximinj aij lntuitively this is because player II cannot be assured of winning an amount greater than that amount more than which player I can be assured of not paying Mathematically let 9 denote the value ofj that attains the minimum of mawiaij and let denote the value of 2 that attains the maximum of mini aij Then min max 127 max aw 2 a3 2 min 1 max min aij j 2 2 7 j 7 2 j Lectures 111213 2 The fact that the assured values are not equal means that it makes sense to consider random strategies for the players Suppose then that in the example I player L with probability w and R the rest of the time whereas II plays L with probability t and R with probability 1 7 t Suppose that I announces to II his choice for 3 How would II react If he plays L his expected payment is 253 if R then 1 7 3 He minimizes the payout and achieves min2w1 7 Knowing that II will react in this way to hearing the value of w I will seek to maximize his payoff by choosing an to maximize min2w 1 7 He is choosing the value of x at which the two lines in this graph cross y2x So his choice is w 13 Looking at things the other way round suppose that player II has to announce t rst The payoff for player I becomes 2t if he picks left and 1 7 t if he picks right Player should choose t 13 to minimize his expected payment This assures him of not paying more than 23 on the average Let s look at another example Suppose we are dealing with a game that has the following payoff matrix llLR l T O 2 B 5 1 Suppose that player I plays T with probability w and B with probability 1 7 w and that player II plays L with probability t and R with probability 1 7 t If player II has declared the value of y then Player I has expected payoff of 21 7 y if he plays T and 43 1 if he plays B The maximum of these quantities is the expected payoff for player I under his optimal strategy given that he knows 3 Player II minimizes and so chooses t 16 to obtain an expected payoff of 53 Lectures 111213 3 4y1 2 5 3 1 22y If player I has declared the value of x then player I has expected payment of 51 7 x if he plays L and 1 x if he plays R He minimizes this and then player I chooses an to maximize the resulting quantity He therefore picks w 23 with expected outcome of 53 2 3 In general player I can choose a probability vector m 1wm 1 where an is the probability that he plays 2 Player I similarly chooses a strategy 31 ynT The resulting expected payoff is given by Z mamy wTAy We will prove Von Neumann s minimax theorem which states that miny maxz wTAy maxz miny wTAy Example Two players choose numbers in 12 n The player whose number is higher than that of her opponent by one wins a dollar but if it exceeds the other number by two or more she loses 2 dollars In the event of a tie no money changes hands We write the payoff matrix for the game ll 1 2 3 4 n l 1 0 1 2 2 2 2 1 0 1 2 2 3 2 1 0 1 2 2 n 1 2 2 1 0 1 2 2 1 0 This apparently daunting example can be reduced by a new technique Lectures 111213 4 Domination if row 2 has each of its elements at least the corresponding element in row 2 that is is 127 2 1 for each 9 then for the purpose of determining the value of the game we may erase row 2 The value of the game is de ned as the value arising from Von Neumann s minimax theorem Similarly there is a notion of domination for player II If aij g aw for each 2 then we can eliminate column 9 without affecting the value of the game More precisely assuming that 127 3 air if player II changes a mixed strategy 3 to another 2 by letting 239 yj 317 23w O and 2 y for all I 74 j 9 then 200211231311 wTAy 2 2 0021123121 wTA27 27 23239 because Zi j xi amy ai jyj 2 Zi j mam 33 yr In the example in question we may eliminate each row and column indexed by four or greater We obtain the reduced game H 1 2 3 1 1 0 1 2 2 1 0 1 3 2 1 0 Consider 531532533 as a strategy for player I The expected payments made by player II under his pure strategies 12 and 3 are 2 7 2w371 321 7 3 Player II seeks to minimize his expected payment Player I is choosing 531532533 for the time being suppose that he zes 33 and optimises his choice for 31 Eliminating 32 1 becomes 17 1 7 35637531 33w1 3 71 Computing the choice of an for which the maximum of the minimum of these quantities is attained and then maximises this over 33 yields an optimal strategy for each player of 141214 and a value for the game of zero Solution of chomp The game of chomp is progressively bounded so that each position is N or P We will show that each rectangular position is in N Otherwise it is in P Consider the move by Player I of chomping the upper right hand corner The resulting position is in N This means that player II has a move to P However player I can play this move to start with because each move after the upper right square of chocolate is gone is available when it was still there So player I can move to P a contradiction Note that it may not be that chomping the upper right hand Lectures 111213 5 corner is a winning move This argument called strategy stealing proves that player I has a winning strategy without identifying it We can be precise about what is meant by a winning strategy a strategy is a function assigning to each possible position a legal move It is winning if the player who has the rst move will win by using it whatever strategy his opponent uses Example Wytho Mm A position consists of a pair of nm of natural numbers nm 2 O A legal move is one of the following to reduce n to some value between 0 and n 7 1 without changing m to reduce m to some value between 0 and m 7 1 without changing n or to reduce each of n and m by the same amount so that the outcome is a pair of natural numbers Consider the following recursive de nition of a sequence of pairs of natural numbers 10170 00a1b1 12 and for each k 2 1 ak mewa1 ak1b0 17194 and bk ak k Each natural number greater than zero is equal to precisely one of the a or the 17 To see this note that aj cannot be equal to any of a1 aj1 or b1 lay1 We have that ak gt aj because otherwise a would have taken the slot that ak did so that bk ak k gt aj j bj Set 04196 LivOJ and k ls17 Firstly we will suppose that there exists 6 E O 1 for which 04196 1k and bk 2 and nd that there is only one number in O 1 for which this might be true Since bk ak k 2 implies that ls6 k ls1 7 Dividing by k and noting that 0 g ke 7Lk6j lt1 so that 0 316 71klk6jlt1k we nd that 1611176 3 Thus 62 6 71 0 so that 6 or 16 equal 21 Thus if there is a solution in O 1 it must be this value We now de ne 6 21 Note that 3 implies that 1911179 so that W0 7 9l 7 W61 k This means that k 04k k We need to verify that 0 mewiaowgtgt704k71n807ww k7llr Lectures 111213 6 We Checked earlier that 0 is not one of these values Why is it equal to their mex De ne z to be this mex If 2 7 0 then Z lt 0 S a 3 for all I 2 k Since 2 is de ned as a niex7 z 7 042 782 for 2 E 07 k 71 Stat 155 Game theory Yuval Peres Lectures 262728 Fall 2004 Example the game of chicken We solve the game of chicken The pure equilibria are C I and IC To determine the symmetric mixed equilibria suppose that player I plays C with probability w and I with probability 1 7 w This presents player II with expected payoffs of 2x 7 1 if she plays C and a 2w 7 a if she plays I We seek an equilibrium where player II has positive weight on each of C and I and thus one for which 2w71a2w7a That is w 171a The payoff for player to is 2w71 which equals 172a There is an abstract paradox here We have a symmetric game with payoff matrices A and B that has a unique symmetric equilibrium with payoff 4 By replacing A and B by smaller matrices A and B we obtain a payoff 5 in a unique symmetric equilibrium that exceeds 4 The proof of Nash s theorem Recall Nash s theorem Theorem 1 For any general sum game with two players there exists at least one Nash equilibrium To prove this theorem we will use Theorem 2 Brouwer s xed point theorem IfK Q Rd is closed con vex and bounded and T K 7 K is continuous then there exists at E K such that Tw w Remark The xed point theorem is easy in dimension d 1 when K is a closed interval a 1 De ning fw Tw 7 at note that Ta 2 a implies that fa 2 0 while Tb S 1 implies that fb S O The intermediate value theorem assures the existence of w 6 ab for which fw 0 and thus so that Tw w Note also that each of the hypotheses on T in the theorem are required Consider T R 7 R given by Tw at 1 as well as T 01 7 01 given by Tw sic2 and also T z E C 6 12 7 z E C 6 12 given by Tw wexpi7r2 Proof of Nash s theorem using Brouwer s theorem Suppose that the game is speci ed by payoff matrices Aan and Ban for players I and II We will de ne a map T K 7 K with K Am gtlt An from a pair of strategies for the two players to another such pair Note rstly that K is convex closed and bounded De ne for w 6 Am and y E An 0200731 02 maX Zaijyj 14317 0 j 1 Lectures 2627 28 2 Or c max Am 7 wTAy 0 where A denotes the i th row of the matrix A That is c is equal to the gain for player I obtained by switching from strategy w to pure strategy 2 if theis gain is positive otherwise it is zero Similarly we de ne 61706731 dj max 0337 7 0933170 where BO denotes the j th column of B The quantities dj have the same interpretation for player II as the c do for player I We now de ne the map T it is given by Twy 524 where ii 502 C2 1 221 Ck for 2 E 1 m and 3 yj ndj 1 2191 dk for j E 1 n Note that T is continuous because c and 27 are Ap plying Brouwer s theorem we nd that ther exists 5331 6 K for which 5331 We now claim that for this choice of w and 3 each c O forz E 1m and dj O forj E 1n To see this suppose for example that cl gt 0 Note that the current payoff of player I is a weighted average There must exists 2 E 1 m for which wTAy 2 Am and an gt O For this 2 we have that Ci O This implies that Z 1Z1Ck because cl gt 0 That is the assumption that cl gt O has brought a contra diction We may repeat this argument for each 2 E 1 m thereby proving that each Ci 0 Similarly each dj 0 We deduce that wTAy 2 Am for all 2 E 1 m This implies that lt xi wTAy 2 KTAy for all w nAm Similarly wTAy 2 wTAgf for all 31 E An Thus wy is a Nash equilibrium D Example the shselling game Fish being sold at the market is fresh with probability 23 and old otherwise and the customer knows this The seller knows whether the particular sh on sale now is fresh or old The customer asks the sh seller whether the sh is fresh the seller answers Lectures 2627 28 3 63 03 94 33 93 30 10 6 0 Figure 1 The Kuhn tree for the sh selling game and then the customer decides to buy the sh or to leave Without buying it The payoff to the seller is 6 is the customer buys the sh 0 if he leaves Without buying it Being truthful has a value of3 to the seller The customer has a payoff of 3 from buying the sh if it is fresh or from leaving if it is old The Kuhn tree for the game is depicted in the gure Here are the payoffs for the two players 11 BB BL LB LL I FF 82 82 21 21 Fo 92 73 50 31 0F 6 2 20 43 01 00 72 11 72 11 We reduce the matrix by domination arguments Note that telling the truth dominate lying as a strategy for the seller In the reduced matricx LL is dominated for the customer as is LB We have the matrix 11 BB BL I FF 82 82 Fo 92 73 00 7 11 In this matrix 00 is dominated for the seller at which point BB is domi nated for the customer We obtain that a pure strategy of FF for the buyer and BL for the seller is optimal Note that in this case the incenitve for truth telling has not been strong enough to de ect the seller from his aim of selling sh he will always claim that the sh is fresh Some xed point theorems We will discuss some xed point theorems beginning with Lectures 2627 28 4 Theorem 3 Banach s xed point theorem LetK be a complete met ric space Suppose that T K gt K satis es dTwTy S Adwy for all 563 6 K with 0 lt A lt 1 xed Then T has a unique xed point in K Note recall that a metric space is complete if each Cauchy sequence therein converges to a point in the space Consider the metric space being a subset of Rd and the metric at being Euclidean distance if you are not familiar with these de nitions Proof Uniqueness of the xed point if Tw w and Ty y then dwy dTwTy S Adwy Thus dwy 0 and w 3 As for existence given any x E K we de ne wn TwnA for each n 2 1 setting am w Set a dw0w1 and note that dwnwn1 S Ana If h gt n then H 1971 aAn dwkwn S dwnwn1 dwk1wk S a A S This implies that am n E N is a Cauchy sequence The metric space K is complete whence mm a 2 as n a 00 Note that dz T2 S dz at dwnwn1 dwn1Tz S 1 Adz at Ana gt 0 as n a 00 Hence dTzz 0 and T2 z D Stat 155 Game theory Yuval Peres Lectures 202122 Fall 2004 The game of Green Hackenbush In the game of Green Hackenbush we are given a nite graph that consists of vertices and some undirected edges between some pairs of the vertices One of the vertices is called the root and might be thought of as the ground on which the rest of the structure is standing We talk of green Hackenbush because there is an partisan variant of the game in which edges may be coloured red or blue instead The aim of the players I and H is to remove the last edge from the graph At any given turn a player may remove some edge from the graph This causes not only that edge to disappear but also all those edges for which every path to the root travels through the edge the player removes Note rstly that if the original graph consists of a nite number of paths each of which ends at the root then in this case Green Hackenbush is equivalent to the game of nim where the number of piles is equal to the number of paths and the number of chips in a pile is equal to the length of the corresponding path We need a lemma to handle the case where the graph is a tree Lemma 1 Colon Principle The Srague Grundy function of Green Hack enbush on a tree is una ected by the following operation for any example of two branches of the tree meeting at a vertex we may replace these two branches by a path emanating from the vertex whose length is the nimsum of the Sprague Gruncly functions of the two branches Proof See Ferguson I 7 42 The proof in outline if the two branches consist simply of paths or stalks emanating from a given vertex then the result is true by noting that the two branches form a two pile game of nim and using the direct sum Theorem for the Sprague Grundy functions of two games More generally we show that we may perform the replacement operation on any two branches meeting at a vertex by iterating replacing pairs of stalks meeting inside a given branch until each of the two branches itself has become a stalk As a simple illustration see the gure The two branches in this case are stalks of length 2 and 3 The Sprague Grundy values of these stalks equal 2 and 3 and their nim sim is equal to 1 Hence the replacement operation takes the form shown For further discussion of Hackenbush and references about the game see Ferguson part I section 6 Lectures 20 21 22 2 General hideandseek games We now analyse a more general version of the game of hide and seek A matrix of values 1717an is given Player I chooses a location ij at which to hide Player I chooses a row or a column of the matrix He wins a payment of 1727 if the line he has chosen contains the hiding place of his opponent Firstly we propose a strategy for player I later checking that it is optimal The player may choose a xed permutation 7r of the set 1 n and then hide at location i m with a probability pi that he chooses Given a choice 7r the optimal choice for pi is pi dimD where dij b2 and D7r 221 dim because it is this choice that equalizes the expected payments The expected payoff for the game is then lD Thus if Player I is going to use a strategy that consists of picking a permutation 7r and then doing as described the right permutation to pick is one that maximizes D We will in fact show that doing this is an optimal strategy not just in the restricted class of those involving permutations in this way but over all possible strategies To nd an optimal strategy for Player I we need an analogue of Konig s lemma In this context a covering of the matrix D 012an will be a pair of vectors u u1un and w 101 wn such that m 10 2 dij for each pair ij We assume that u and 1 have non negative components The analogue of the Konig lemma Lemma 2 Consider a minimal covering uv This means one for which 221 102 is minimal Then TL mw m7axD7r 1 s H Lectures 20 21 22 3 Proof Note rstly that a minimal covering exists because the map uv gt I 112 n 1 H and attains its in mum if at all on the closed and bounded set uw uhw 3 71M where M manJ Dk l Note also that we may assume that mini gt 0 That the lefthand side of 1 is at least the right hand side is straight forward lndeed for any 7r we have that 10 2 dim Summing over 2 we obtain this inequality Showing the other inequality is harder and requires Hall s marriage lemma or something similar We need a de nition of knowing to use the Hall lemma We say that row 2 knows column 9 is 4lt 7 u wj 7d Let s check Hall s condition Suppose that k rows 11 2 know between them only I lt k columns 91 9 De ne 71 from M by reducing these rows by a small amount 5 Leave the other rows unchanged The condition that 5 must satisfy is in fact that e lt minuf Z and also 5 lt minm 10 7 01239 ijsuch that m 10 gt 0127 Similarly de ne 12 from 10 by adding 5 to the 1 columns known by the k rows Leave the other columns unchanged That is for the columns that are changing 133 10 5 forz E 1l We claim that 2113 is a covering of the matrix At places where the equality dij 10 holds we have that dij 21 133 by construction In places where dij lt 10 then 7741372ufiewggtd h the latter inequality by the assumption on the value of e The covering 2113 has a strictly smaller sum of components than does uw contradicting the fact that this latter covering was chosen to be minimal We have checked that Halls condition holds Hall s lemma provides a mathcing of columns and rows This is a permutation 7r such that for each 2 we have that u ME dim Lectures 20 21 22 4 from which it follows that n n 4lt 4lt E uZ E 102 D7 i1 i1 We have found a permutation 7r that gives the other inequality required to prove the lemma D We have therefore found a pair of optimal strategies for the players To summarise player I chooses row 2 with probability itfDj r7 and column 9 with probability lugD3 Against this strategy if player I chooses 14 then the payoff will be 71 bi 2 dijbij D11 D7 D7 7 We deduce that the permutation strategy for player I described earlier is indeed optimal Stat 155 Game theory Yuval Peres Lectures 262728 Fall 2004 Example the game of chicken We solve the game of chicken The pure equilibria are C I and IC To determine the symmetric mixed equilibria suppose that player I plays C with probability w and I with probability 1 7 w This presents player II with expected payoffs of 2x 7 1 if she plays C and a 2w 7 a if she plays I We seek an equilibrium where player II has positive weight on each of C and I and thus one for which 2w71a2w7a That is w 171a The payoff for player to is 2w71 which equals 172a There is an abstract paradox here We have a symmetric game with payoff matrices A and B that has a unique symmetric equilibrium with payoff 4 By replacing A and B by smaller matrices A and B we obtain a payoff 5 in a unique symmetric equilibrium that exceeds 4 The proof of Nash s theorem Recall Nash s theorem Theorem 1 For any general sum game with two players there exists at least one Nash equilibrium To prove this theorem we will use Theorem 2 Brouwer s xed point theorem IfK Q Rd is closed con vex and bounded and T K 7 K is continuous then there exists at E K such that Tw w Remark The xed point theorem is easy in dimension d 1 when K is a closed interval a 1 De ning fw Tw 7 at note that Ta 2 a implies that fa 2 0 while Tb S 1 implies that fb S O The intermediate value theorem assures the existence of w 6 ab for which fw 0 and thus so that Tw w Note also that each of the hypotheses on T in the theorem are required Consider T R 7 R given by Tw at 1 as well as T 01 7 01 given by Tw sic2 and also T z E C 6 12 7 z E C 6 12 given by Tw wexpi7r2 Proof of Nash s theorem using Brouwer s theorem Suppose that the game is speci ed by payoff matrices Aan and Ban for players I and II We will de ne a map T K 7 K with K Am gtlt An from a pair of strategies for the two players to another such pair Note rstly that K is convex closed and bounded De ne for w 6 Am and y E An 0200731 02 maX Zaijyj 14317 0 j 1 Lectures 2627 28 2 Or c max Am 7 wTAy 0 where A denotes the i th row of the matrix A That is c is equal to the gain for player I obtained by switching from strategy w to pure strategy 2 if theis gain is positive otherwise it is zero Similarly we de ne 61706731 dj max 0337 7 0933170 where BO denotes the j th column of B The quantities dj have the same interpretation for player II as the c do for player I We now de ne the map T it is given by Twy 524 where ii 502 C2 1 221 Ck for 2 E 1 m and 3 yj ndj 1 2191 dk for j E 1 n Note that T is continuous because c and 27 are Ap plying Brouwer s theorem we nd that ther exists 5331 6 K for which 5331 We now claim that for this choice of w and 3 each c O forz E 1m and dj O forj E 1n To see this suppose for example that cl gt 0 Note that the current payoff of player I is a weighted average There must exists 2 E 1 m for which wTAy 2 Am and an gt O For this 2 we have that Ci O This implies that Z 1Z1Ck because cl gt 0 That is the assumption that cl gt O has brought a contra diction We may repeat this argument for each 2 E 1 m thereby proving that each Ci 0 Similarly each dj 0 We deduce that wTAy 2 Am for all 2 E 1 m This implies that lt xi wTAy 2 KTAy for all w nAm Similarly wTAy 2 wTAgf for all 31 E An Thus wy is a Nash equilibrium D Example the shselling game Fish being sold at the market is fresh with probability 23 and old otherwise and the customer knows this The seller knows whether the particular sh on sale now is fresh or old The customer asks the sh seller whether the sh is fresh the seller answers Lectures 2627 28 3 63 03 94 33 93 30 10 6 0 Figure 1 The Kuhn tree for the sh selling game and then the customer decides to buy the sh or to leave Without buying it The payoff to the seller is 6 is the customer buys the sh 0 if he leaves Without buying it Being truthful has a value of3 to the seller The customer has a payoff of 3 from buying the sh if it is fresh or from leaving if it is old The Kuhn tree for the game is depicted in the gure Here are the payoffs for the two players 11 BB BL LB LL I FF 82 82 21 21 Fo 92 73 50 31 0F 6 2 20 43 01 00 72 11 72 11 We reduce the matrix by domination arguments Note that telling the truth dominate lying as a strategy for the seller In the reduced matricx LL is dominated for the customer as is LB We have the matrix 11 BB BL I FF 82 82 Fo 92 73 00 7 11 In this matrix 00 is dominated for the seller at which point BB is domi nated for the customer We obtain that a pure strategy of FF for the buyer and BL for the seller is optimal Note that in this case the incenitve for truth telling has not been strong enough to de ect the seller from his aim of selling sh he will always claim that the sh is fresh Some xed point theorems We will discuss some xed point theorems beginning with Lectures 2627 28 4 Theorem 3 Banach s xed point theorem LetK be a complete met ric space Suppose that T K gt K satis es dTwTy S Adwy for all 563 6 K with 0 lt A lt 1 xed Then T has a unique xed point in K Note recall that a metric space is complete if each Cauchy sequence therein converges to a point in the space Consider the metric space being a subset of Rd and the metric at being Euclidean distance if you are not familiar with these de nitions Proof Uniqueness of the xed point if Tw w and Ty y then dwy dTwTy S Adwy Thus dwy 0 and w 3 As for existence given any x E K we de ne wn TwnA for each n 2 1 setting am w Set a dw0w1 and note that dwnwn1 S Ana If h gt n then H 1971 aAn dwkwn S dwnwn1 dwk1wk S a A S This implies that am n E N is a Cauchy sequence The metric space K is complete whence mm a 2 as n a 00 Note that dz T2 S dz at dwnwn1 dwn1Tz S 1 Adz at Ana gt 0 as n a 00 Hence dTzz 0 and T2 z D Stat 155 Game theory Yuval Peres Lecture 2 Fall 2004 We continue the overview of topics Another example of a mathematical tool that we will encounter is Theorem 1 Brouwer s xed point theorem If K Q Rd is closed bounded and convex and T K gt K is continuous then T has a xed point That is there exists at E K for which Tw w The assumption of convexity can be weakened but not discarded entirely To see this consider the example of the annulus C w E R2 1 S S 2 and the mapping T C a C that sends each point to its rotation by 90 degrees anticlockise about the origin Then T is isometric that is Tw 7 Inc 7 yl for each pair of points wy E C Certainly then T is continuous but it has no xed point Although from its statement it is not evident what the connection of Brouwer s theorem to game theory might be we will see that the theorem is of central importance in proving the existence of Nash equilibria Example Pie cutting As another example consider the problem of a pie different parts of whose interior are composed of different ingredients The game has two or more players who each have their own preferences regarding which parts of the pie they would most like to have If there are just two players there is a well known method for dividing the pie one splits it into two halves and the other chooses which he would like Each obtains at least onehalf of the pie as measured according to each own preferences But what if there are three or more players We will study this question and that where we ask that the pie be cut in such a way that each player judges that he gets at least as much as anyone else according to his own criterion Example Secret sharing Suppose that we plan to give a secret to two people We do not trust either of them entirely but want the secret to be known to each of them provided that they co operate If we look for a physical solution to this problem we might just put the secret in a room put two locks on the door and give each of the players the key to one of the doors In a computing context we might take a password and split it in two giving the each half to one of the players However this would force the length of the password to be high if one or other half is not to be guessed by repeated tries A more ambitious goal is to split the secret in two in such a way that neither person has any useful information on his own And here Lecture 2 2 is how to do it suppose that the secret s is an integer that lies between 0 and some large value M for example M 106 We who hold the secret at the start produce a random integer 3 whose distribution is uniform on the interval 0 M 7 1 uniform means that each of the M possible outcomes is equally likely having probability We tell the number x to the rst person and the number 3 s 7 wm0dM to the second person mod M means adding the right multiple of M so that the value lies on the interval 0 M 7 The rst person has no useful information What about the second Note that Pyj P57wm0dMj lM the last equality because 5 7 wmodM equals 3 if and only if the uniform random variable x happens to hit one particular value on 0 M1 So the second person himself only has a uniform random variable and thus no useful information Together however the players can add the values they have been given reduce the answer mod M and get the secret 5 back A variant of this scheme can work with any number of players We might have ten of them in such a way that any nine of them have no useful information if they pool their resources and with the ten together being able to unlock the secret Example Cooperative games These games deal with the formation of coalitions and their mathematical solution involves the notion of Shapley value As an example suppose that three people 1 and I sit in a store the rst two bearing a left handed glove while the third has a right handed one A wealthy tourist ignorant of the bitter local climactic conditions enters the store in dire need of a pair of gloves She refuses to deal with the glove bearers individually so that it becomes their job to form coalitions to make a sale of a left and right handed glove to her The third player has an advantage because his commodity is in scarcer supply This means that he should be able to obtain a higher fraction of the payment that the tourist makes than either of the other players However if he holds out for too high a fraction of the earnings the other players may agree between them to refuse to deal with him at all blocking any sale and thereby risking his earnings We will prove results in terms of the concept of the Shapley value that provide a solution to this type of problem Example Keeping the metereologist honest The employer of a weatherman is determined that he should provide a good prediction of the weather for the following day The weatherman s instruments are good and he can with su icient effort tune them to obtain the correct value for the probability of rain on the next day There are many days and on the i th of them this correct probability is called pi On the evening of the 2 7 1 th day the weatherman submits his estimate 13 for the probability of rain on the following day the i th one Which scheme should we adopt to reward Lecture 2 3 or penalize the weatherman for his predictions so that he is motivated to correctly determine 13 that is to declare 13 13 The employer does not know what 13 is because he has no access to technical equipment but he does know the 13 values that the waetherman provides and he knows whether or not it is raining on each day One suggestion is to pay the weatherman on the i th day the amount 13 or some dollar multiple of that amount if it rains and 1713 if it shines If 13 13 06 then the payoff is 13 lPit rains 1 7 13 lPit shines 132 1 7 13 1 7 13 06 X 06 04 X 04 052 But in this case even if the weatherman does correctly compute that 13 06 he is tempted to report the 13 value of 1 because by the same formula in this case his earnings are 06 Another idea is to wait for a long time one year say and reward the weatherman according to how accurate his predictions have been on the average More concretely suppose for the sake of simplicity that both the weatherman is only able to report 13 values on a scale of 01 so that he has eleven choices namely kIO k E 0 10 When a year has gone by the days of that year may be divided into eleven types according to the 13 value that the weatherman declared We would compare the fraction of days it rained in the class of days on which 13 was declared to the value 13 and reward the weatherman if this value is low for each of the eleven values of 2 A scheme like this is quite reasonable and would certainly ensure that the weatherman tuned his instruments at the beginning of the year How ever it is not perfect For example ordinary random uctuation mean that the weatherman will be probably be slightly wrong as the end of the year approaches It might be that it rained on 95 percent of the days on which the weatherman declared 13 09 while on those on which he declared at 06 the average in reality has been 55 percent Suppose that on the evening of one of the later days he sees that his instruments accurately predict 09 He knows that it very likely to rain on the next day He is tempted to declare the next day at 06 that is to set 13 06 for the 2 in question because doing so will boost his 06 category and allow his 09 category to catch up with the downpour lnfact it is possible to design a scheme whereby we decide day by day how to reward the weatherman only on the basis of his declaration from the previous evening without encountering the kind of problem that the last scheme had Suppose that we pay f to the weatherman if it rains and f1 7 132 if it shines on day 2 lf13 13 and 13 x then the expected payment made on day 2 is equal to pfwgt17pgtf1 06 9W Lecture 2 4 We are de ning gpw to be this left hand side7 because we are interested in how the payout is expected to depend on the prediction w of the weatherman on a given day where the probability of rain is 13 Our aim is to reward the weatherman if his 13 equals pi in other words7 to ensure that the expected payout is maximised when w p This means that the function gp 01 a R should satisfy gpp gt gpw for all x 6 01 7 Homework Using this approach7 determine a good choice of f Or nd another good scheme for rewarding the weatherman Stat 155 Game theory Yuval Peres Lecture 3 Fall 2004 Topic Combinatorial games Example We begin with K chips in one pile Players I and II make their moves alternately with player I going rst Each players takes between one and four chips on his turn The player who removes the last chip wins the game We write N n E N player I wins if there n chips at the start where we are assuming that each player plays optimally We set P N 7 N Clearly 1 23 4 Q N because player I can win with his rst move That 5 E P because the number of chips after the rst move must lie in the set 12 34 That 6 7 89 6 N follows from the fact that player I can force his opponent into a losing position by ensuring that there are ve chips at the end of his rst turn Continuing this line of argument we nd that P n E N nis divisible by ve De nition 1 A combinatorial game has two players and a set which is usually nite of possible positions There are rules for each of the players that specify the available legal moves for the player whose turn it is If the moves are the same for each of the players the game is called impartial Otherwise it is called partisan The players alternate moves Under normal play the player who cannot move loses Under mis ere play the player who makes the nal move loses De nition 2 Generalising the earlier example we write N for the collec tion of starting positions from which the rst player to move will win pro vided that each of the players adopts an optimal straegy and P for the remaining starting positions Example nim In this game there are several piles each containing nitely many chips A legal move is to remove any positive number of chips from a given pile The game has normal play so the player who takes the nal chip wins We will write the state of play in the game in the form 711712 nk meaning that there are k piles of chips still in the game and that the rst has n1 chips in it the second ng and so on Lecture 3 2 Note that 1 1 E P because the game must end after the second turn from this beginning We see that 12 6 N because the rst player can bring 12 to 11 6 P Similarly 7171 6 P for n E N and nm E N if nm E N are not equal We see that 123 6 P because whichever move the rst player makes the second can force there to be two piles of equal size The following theorem characterises the sets N and P for this game Theorem 1 Given a starting position 711712 nk write each of the it in binary and sum each of the columns mod 2 The position is in P if and only if all of the answers are zero To illustrate the theorem consider the starting position 123 We nd that number of chips decimal number of chips binary 1 01 2 10 3 11 Summing modulo two the zeros and ones in the two columns of binary we obtain 00 The theorem con rms that 123 6 P Homework i the weatherman problem ii Consider a game where there are two piles of chips Players may with draw chips from exactly one of the piles on their turns with the legal moves being to remove between one and four chips from the rst pile and from be tween one and ve chips from the second pile Determine for which nm E N it is the case that nm E P iii Nimble in this game a nite number of coins are placed on a row of slots of nite length Several coins can occupy any given slot In any given turn a player may move one of the coins to the left by any number of places The game ends when all the coins are at the leftmost slot Stat 155 Game theory Yuval Peres Lecture 2 Fall 2004 We continue the overview of topics Another example of a mathematical tool that we will encounter is Theorem 1 Brouwer s xed point theorem If K Q Rd is closed bounded and convex and T K gt K is continuous then T has a xed point That is there exists at E K for which Tw w The assumption of convexity can be weakened but not discarded entirely To see this consider the example of the annulus C w E R2 1 S S 2 and the mapping T C a C that sends each point to its rotation by 90 degrees anticlockise about the origin Then T is isometric that is Tw 7 Inc 7 yl for each pair of points wy E C Certainly then T is continuous but it has no xed point Although from its statement it is not evident what the connection of Brouwer s theorem to game theory might be we will see that the theorem is of central importance in proving the existence of Nash equilibria Example Pie cutting As another example consider the problem of a pie different parts of whose interior are composed of different ingredients The game has two or more players who each have their own preferences regarding which parts of the pie they would most like to have If there are just two players there is a well known method for dividing the pie one splits it into two halves and the other chooses which he would like Each obtains at least onehalf of the pie as measured according to each own preferences But what if there are three or more players We will study this question and that where we ask that the pie be cut in such a way that each player judges that he gets at least as much as anyone else according to his own criterion Example Secret sharing Suppose that we plan to give a secret to two people We do not trust either of them entirely but want the secret to be known to each of them provided that they co operate If we look for a physical solution to this problem we might just put the secret in a room put two locks on the door and give each of the players the key to one of the doors In a computing context we might take a password and split it in two giving the each half to one of the players However this would force the length of the password to be high if one or other half is not to be guessed by repeated tries A more ambitious goal is to split the secret in two in such a way that neither person has any useful information on his own And here Lecture 2 2 is how to do it suppose that the secret s is an integer that lies between 0 and some large value M for example M 106 We who hold the secret at the start produce a random integer 3 whose distribution is uniform on the interval 0 M 7 1 uniform means that each of the M possible outcomes is equally likely having probability We tell the number x to the rst person and the number 3 s 7 wm0dM to the second person mod M means adding the right multiple of M so that the value lies on the interval 0 M 7 The rst person has no useful information What about the second Note that Pyj P57wm0dMj lM the last equality because 5 7 wmodM equals 3 if and only if the uniform random variable x happens to hit one particular value on 0 M1 So the second person himself only has a uniform random variable and thus no useful information Together however the players can add the values they have been given reduce the answer mod M and get the secret 5 back A variant of this scheme can work with any number of players We might have ten of them in such a way that any nine of them have no useful information if they pool their resources and with the ten together being able to unlock the secret Example Cooperative games These games deal with the formation of coalitions and their mathematical solution involves the notion of Shapley value As an example suppose that three people 1 and I sit in a store the rst two bearing a left handed glove while the third has a right handed one A wealthy tourist ignorant of the bitter local climactic conditions enters the store in dire need of a pair of gloves She refuses to deal with the glove bearers individually so that it becomes their job to form coalitions to make a sale of a left and right handed glove to her The third player has an advantage because his commodity is in scarcer supply This means that he should be able to obtain a higher fraction of the payment that the tourist makes than either of the other players However if he holds out for too high a fraction of the earnings the other players may agree between them to refuse to deal with him at all blocking any sale and thereby risking his earnings We will prove results in terms of the concept of the Shapley value that provide a solution to this type of problem Example Keeping the metereologist honest The employer of a weatherman is determined that he should provide a good prediction of the weather for the following day The weatherman s instruments are good and he can with su icient effort tune them to obtain the correct value for the probability of rain on the next day There are many days and on the i th of them this correct probability is called pi On the evening of the 2 7 1 th day the weatherman submits his estimate 13 for the probability of rain on the following day the i th one Which scheme should we adopt to reward Lecture 2 3 or penalize the weatherman for his predictions so that he is motivated to correctly determine 13 that is to declare 13 13 The employer does not know what 13 is because he has no access to technical equipment but he does know the 13 values that the waetherman provides and he knows whether or not it is raining on each day One suggestion is to pay the weatherman on the i th day the amount 13 or some dollar multiple of that amount if it rains and 1713 if it shines If 13 13 06 then the payoff is 13 lPit rains 1 7 13 lPit shines 132 1 7 13 1 7 13 06 X 06 04 X 04 052 But in this case even if the weatherman does correctly compute that 13 06 he is tempted to report the 13 value of 1 because by the same formula in this case his earnings are 06 Another idea is to wait for a long time one year say and reward the weatherman according to how accurate his predictions have been on the average More concretely suppose for the sake of simplicity that both the weatherman is only able to report 13 values on a scale of 01 so that he has eleven choices namely kIO k E 0 10 When a year has gone by the days of that year may be divided into eleven types according to the 13 value that the weatherman declared We would compare the fraction of days it rained in the class of days on which 13 was declared to the value 13 and reward the weatherman if this value is low for each of the eleven values of 2 A scheme like this is quite reasonable and would certainly ensure that the weatherman tuned his instruments at the beginning of the year How ever it is not perfect For example ordinary random uctuation mean that the weatherman will be probably be slightly wrong as the end of the year approaches It might be that it rained on 95 percent of the days on which the weatherman declared 13 09 while on those on which he declared at 06 the average in reality has been 55 percent Suppose that on the evening of one of the later days he sees that his instruments accurately predict 09 He knows that it very likely to rain on the next day He is tempted to declare the next day at 06 that is to set 13 06 for the 2 in question because doing so will boost his 06 category and allow his 09 category to catch up with the downpour lnfact it is possible to design a scheme whereby we decide day by day how to reward the weatherman only on the basis of his declaration from the previous evening without encountering the kind of problem that the last scheme had Suppose that we pay f to the weatherman if it rains and f1 7 132 if it shines on day 2 lf13 13 and 13 x then the expected payment made on day 2 is equal to pfwgt17pgtf1 06 9W Lecture 2 4 We are de ning gpw to be this left hand side7 because we are interested in how the payout is expected to depend on the prediction w of the weatherman on a given day where the probability of rain is 13 Our aim is to reward the weatherman if his 13 equals pi in other words7 to ensure that the expected payout is maximised when w p This means that the function gp 01 a R should satisfy gpp gt gpw for all x 6 01 7 Homework Using this approach7 determine a good choice of f Or nd another good scheme for rewarding the weatherman Stat 155 Game theory Yuval Peres Lectures 456 Fall 2004 In the last lecture we de ned N and P positions for a combinatorial game We will now show more formally that each starting position in a combinatorial game lies in either N or P Recall that the end position 0 of any game lies in P if the game is conducted under normal play Any position for which there is a move to a P position lies in N Any position where all moves lead to N positions lies in P Writing this more formally we de ne P0 0 N 1 positions x for which there is a move leading to P P positions 3 such that each move leads to N2 1 for each 2 E N We set NUN PUP 2 20 2 20 Consider a game where for each starting position x the game must end within Bw lt 00 moves no matter which moves the two players make We check by induction on Bw that all positions lies in N U P If Bw 0 this is true because P0 Q P Assume the inductive hypothesis for those positions x for which Bw S n and consider any position 2 satisfying Bz n 1 There are two cases to handle the rst is that each move from 2 leads to a position in N that is to a member of one of the previously constructed sets Ni Then 2 lies in one of the sets Pi and thus in P In the second case there is a move from 2 to some P position This implies that z E N Thus all initial positions lie in either N or P The metereologist question recall this problem from Lecture 2 By checking the derivative of gpw we see that fw logw or fw 71 7 w2 are such that gpp gt gpw for w E 0 1 7 Last time we stated a theorem on how to play optimally the game of nim We now present the proof Proof of Bouton s Theorem We write n m to be the nim sum of n m E N This operation is the one described in the statement of the theorem We write 71 and m in binary and compute the value of the sum of the digits in each column modulo 2 The result is the binary expression for the nim sum Lectures 4 56 2 n 69 m Another way of saying this is that the nim sum of a collection of values m1m2 mk is the sum of all the powers of two that occurred an odd number of times when we wrote each of the numbers mi as a sum of powers of two Here is an example m1 13m2 9m3 3 ln powers of two Lectures 4 56 3 m1 2322 20 m2 23 20 m3 21 20 In this case the powers of two that appear an odd number of times are 20 1 and 21 2 this means that the nim sum m1 69mg 69mg 12 3 For the case where m1m2m3 5615 we write in purely binary notation 5 O 1 O 1 6 O 1 1 O 15 1 1 1 1 1 1 O O making the nim sum 12 in this case We de ne 17 to be those positions with nim sum zero and N to be all other positions We claim that PP andNN To check this claim we need to show two things Firstly that O E 15 and that for all x E N there exists a move from w leading to 13 Secondly that for every 3 E 15 all moves from 3 lead to Note rstly that O E 13 is clear Secondly suppose that w m1m2 mk E N Set 5 ml 69 EB mk Writing each m in binary note that there are an odd number of values ofz E 1 k for which the binary expression for m has a 1 in the position of the left most one in the expression for 5 Choose one such 2 Note that mi 69 s lt mi because mi 69 s has no 1 in this leftmost position and so is less than any number whose binary expression does have a 1 there So we can play the move that removes from the i th pile mi 7 mi 69 s chips so that m becomes mi 69 s The nim sum of the resulting position m1 m1m EB sm 1 mk is zero so this new position lies in 13 We have checked the rst of the two conditions which we require A To verify the second condition we have to show that ify 31 yk E P then any move from 3 leads to a position 2 E N We write the y in binary m 31 ylmylnin r r 4110 2 313 70 m I M nkinf r 4110 Z 311 r 70 Lectures 4 56 4 A particular example 4 0100 22 6 01102221 15 1111 2322 21 20 13 1101 232220 By assumption 3 E This means that the nim sum 3 EB 69 31 O for each 9 In other means that ELI 310 is even for each 9 Suppose that we remove chips from pile Z We get a new position 2 21 2k with 2 y for 2 E 1 k 2 7 l and with 2 lt 31 The case where 2 O is permitted Consider the binary expressions for y and 2 31 ylngtylnilgt r r 450 21 21ngt2ln71gt 250 We scan these two rows of zeros and ones until we locate the rst instance of a disagreement between them In the column where it occurs the nim sum of y and 2 is one This means that the nim sum of 2 21 2k is also equal to one in this column Thus 2 E N We have checked the second condition that we needed and so the proof of the theorem is complete D Example the game of rims In this game a starting position consists of a nite number of dots in the plane and a nite number of continuous loops Each loop must not intersect itself nor any of the other loops Each loop must pass through at least one of the dots It may pass through any number of them A legal move for either of the two players consists of drawing a new loop so that the new picture would be a legal starting position The players aim is to draw the last legal loop We can see that the game is identical to a variant of nim For any given position think of the dots that have no loop going through them as being divided into different classes Each class consists of the set of dots that can be reached by a continuous path from a particular dot without crossing any loop We may think of each class of dots as being a pile of chips like in nim What then are the legal moves expressed in these terms Drawing a legal loop means removing at least one chip from a given pile and then splitting the remaining chips in the pile into two separate piles We can in fact split in any way we like or leave the remaining chips in a single pile This means that the game of rims has some extra legal moves to those of him However it turns out that these extra make no difference and so that the sets N or P coincide for the two games We now prove this Thinking of a position in rims as a nite number of piles we write Pmm and Nmm for the P and N positions for the game of nim so that these sets were found in Bouton s Theorem We want to show that p mm and that N NW 2 Lectures 4 56 5 where here P and N refer to the game of rims What must we check Firstly that O E P which is immediate Secondly that from any position in NMm we may move to Pmm by a move in rims This is ne because each nim move is legal in rims Thirdly that for any 3 E Pmm any rims move takes us to a position in Nm39m If the move does not involve breaking a pile then it is a nim move so this case is ne We need then to consider a move where y is broken into two parts u and 1 whose sum satis es n1 lt 3 Note that the nim sum uEBv of u and 1 is at most than the ordinary sum u 1 this is because the nim sum consists of the sum of the odd powers that appear in the expression for u 1 as a sum of powers of two that is it involves omitting from this expression certain powers of two Thus u 69 11 S u 11 lt 31 So the rims move in question amounted to replacing the pile of size 3 by one with a smaller number of chips u 69 1 Thus the rims move has the same effect as a legal move in nim so that when it is applied to y E Pmm it produces a position in Nmm This is what we had to check so we have nished proving Stat 155 Game theory Yuval Peres Lecture 1 Fall 2004 In this course on game theory we will be studying a range of mathemat ical models of con ict and cooperation between two or more agents The course will attempt an overview of a broad range of the models that are studied in game theory and that have found application in for example economics and evolutionary biology This rst lecture gives an inkling of what is to come in the form of numerous examples One class of games that we begin by studying are combinatorial games An example of a combinatorial game is that of hex which is played on an hexagonal grid shaped as a square think of a large square shaped region that is tiled by a grid of small hexagons Two players R and G alternately colour in hexagons of their choice either red or green the red player aiming to produce a red crossing from left to right in the square and the green player aiming to form a green one from top to bottom Finding the optimal strategy for either player remains an unsolved problem except in a few cases where the number of hexagons is small An interesting variant of the game is that in which instead of taking turns to play a coin is tossed at each turn so that each player plays the next turn with probability one half A second example which is simpler to analyse is the game of Mm There are two players and several piles of sticks at the start of the game The players take turns and at each turn most remove at least one stick from one pile The player can remove any number of sticks that he pleases but these must be drawn from a given pile The aim of the game is to force the opponent to take the last stick remaining in the game We will nd the solution to Mm it is not one of the harder examples Thirdly there are congestion games lmagine two drivers I and II who aim respectively to travel from cities B to D or A to C 35 24 R 3 4 0 The costs incurred to the drivers depend on whether they travel the roads alone or along with the other driver The vectors 11 attached to each road mean that the cost paid by wither driver for the use of the road is a if he travels the road alone and b if he Lecture 1 2 shares its use with the other driver For example if I and II each use the road AB which means that I chooses the route via A and II that via B then each pays 5 units for doing so whereas if only one of them uses that road the cost is 3 units to that driver We write a cost matrix to describe the game HE D l A 68 43 C 56 75 d The vector notation enotes the costs to players I and II of their joint choice A fourth example is that of penalty kicks in which there are two partici pants the penalty taker and the goalkeeper The notion of left and right will be determined by the goalkeeper not the penalty taker The penalty taker chooses to hit the ball either to the left or the right and the goalkeeper dives in one of these directions We display the probabilities that the penalty is scored in the following table GK L R PT L 08 1 R 1 05 That is if the goalie makes the wrong choice he has no chance The penalty taker has a strong left foot and has a better chance if he plays left The goalkeeper aims to minimise the probability of the penalty being scored and the penalty taker aims to maximise it We could write a payoff matrix for the game but since it is zero sum with the interests of the players being diametrically opposed one value sums up the outcome of each joint strategy for the players so that doing so is redundant We will determine the optimal strategy for the players for a class of games that include this one and often it will turn out to be a random one Two person zero sum games have been applied in a lot of contexts in sprots like this example in military contexts in a few economic applica tions in evolutionary biology These games have a very complete theory so that it has been tempting to try to apply them Real life is often more complicated however with the possibility of cooperation between players to realize a mutual advantage The theory of games that model such an effect is much less complete The mathematics associated to zerosum games is that of convex geom etry A convex set is one where for any two points in the set the straight line segment whose endpoints are these two itself lies in the set Lecture 1 3 The relevant geometric fact for this aspect of game theory is that given any closed convex set in the plane and a point lying outside of it we can nd a nd that separates the set from the point There is an analogous statement in higher dimensions Von Neumann exploited this fact to solve zero sum games using a minimax variational principle We will prove this result A related concept is that of Nash equilibrium is there a rational choice for the two players and if so what could it be The meaning of rational here and in many contexts is a valid subject for discussion There are anyway often many Nash equilibria and further criteria are required to pick out relevant ones A development of the last twenty that we will discuss is the application of game theory to evolutionary biology ln economic applications it is often assumed that the agents are acting rationally and a neat theorem should not distract us from remembering that this can be a hazardous assumption In some biological applications we can however see Nash equilibria arising as stable points of evolutionary systems composed of agents who are just doing their own thing without needing to be rational Another interesting topic is that of signalling If one player has some information that another does not that may be to his advantage But if he plays differently might he give away what he knows thereby removing this advantage A quick mention of other topics that of voting Arrow s impossibility theorem states roughly that if there is an election with more than two can didates then no matter which system one chooses to use for voting there is trouble ahead at least one desirable property that we might wish for the election will be violated A recent topic is that of eliciting truth In an or dinary auction there is a temptation to underbid For example if a bidder values an item at 100 dollars then he has no motive to bid any more or even that much because by exchanging 100 dollars for the object at stake he has gained an item only of the same value to him as his money The second price auction is an attempt to overcome this aw in this scheme the lot goes to the highest bidder but at the price offered by the second highest bid der This problem and its solutions are very relevant to bandwidth auctions made by governments to cellular phone companies A nal question for this rst lecture suppose that we seek to reward a metereologist who is asked for the probability of rain tomorrow She offers a probability between 0 and 1 and we want to devise a strategy for paying here so that she is motivated to get at least roughly the right answer We will later see a good example of a scheme for doing this Stat 155 Game theory Yuval Peres Lectures 456 Fall 2004 In the last lecture we de ned N and P positions for a combinatorial game We will now show more formally that each starting position in a combinatorial game lies in either N or P Recall that the end position 0 of any game lies in P if the game is conducted under normal play Any position for which there is a move to a P position lies in N Any position where all moves lead to N positions lies in P Writing this more formally we de ne P0 0 N 1 positions x for which there is a move leading to P P positions 3 such that each move leads to N2 1 for each 2 E N We set NUN PUP 2 20 2 20 Consider a game where for each starting position x the game must end within Bw lt 00 moves no matter which moves the two players make We check by induction on Bw that all positions lies in N U P If Bw 0 this is true because P0 Q P Assume the inductive hypothesis for those positions x for which Bw S n and consider any position 2 satisfying Bz n 1 There are two cases to handle the rst is that each move from 2 leads to a position in N that is to a member of one of the previously constructed sets Ni Then 2 lies in one of the sets Pi and thus in P In the second case there is a move from 2 to some P position This implies that z E N Thus all initial positions lie in either N or P The metereologist question recall this problem from Lecture 2 By checking the derivative of gpw we see that fw logw or fw 71 7 w2 are such that gpp gt gpw for w E 0 1 7 Last time we stated a theorem on how to play optimally the game of nim We now present the proof Proof of Bouton s Theorem We write n m to be the nim sum of n m E N This operation is the one described in the statement of the theorem We write 71 and m in binary and compute the value of the sum of the digits in each column modulo 2 The result is the binary expression for the nim sum Lectures 4 56 2 n 69 m Another way of saying this is that the nim sum of a collection of values m1m2 mk is the sum of all the powers of two that occurred an odd number of times when we wrote each of the numbers mi as a sum of powers of two Here is an example m1 13m2 9m3 3 ln powers of two Lectures 4 56 3 m1 2322 20 m2 23 20 m3 21 20 In this case the powers of two that appear an odd number of times are 20 1 and 21 2 this means that the nim sum m1 69mg 69mg 12 3 For the case where m1m2m3 5615 we write in purely binary notation 5 O 1 O 1 6 O 1 1 O 15 1 1 1 1 1 1 O O making the nim sum 12 in this case We de ne 17 to be those positions with nim sum zero and N to be all other positions We claim that PP andNN To check this claim we need to show two things Firstly that O E 15 and that for all x E N there exists a move from w leading to 13 Secondly that for every 3 E 15 all moves from 3 lead to Note rstly that O E 13 is clear Secondly suppose that w m1m2 mk E N Set 5 ml 69 EB mk Writing each m in binary note that there are an odd number of values ofz E 1 k for which the binary expression for m has a 1 in the position of the left most one in the expression for 5 Choose one such 2 Note that mi 69 s lt mi because mi 69 s has no 1 in this leftmost position and so is less than any number whose binary expression does have a 1 there So we can play the move that removes from the i th pile mi 7 mi 69 s chips so that m becomes mi 69 s The nim sum of the resulting position m1 m1m EB sm 1 mk is zero so this new position lies in 13 We have checked the rst of the two conditions which we require A To verify the second condition we have to show that ify 31 yk E P then any move from 3 leads to a position 2 E N We write the y in binary m 31 ylmylnin r r 4110 2 313 70 m I M nkinf r 4110 Z 311 r 70 Lectures 4 56 4 A particular example 4 0100 22 6 01102221 15 1111 2322 21 20 13 1101 232220 By assumption 3 E This means that the nim sum 3 EB 69 31 O for each 9 In other means that ELI 310 is even for each 9 Suppose that we remove chips from pile Z We get a new position 2 21 2k with 2 y for 2 E 1 k 2 7 l and with 2 lt 31 The case where 2 O is permitted Consider the binary expressions for y and 2 31 ylngtylnilgt r r 450 21 21ngt2ln71gt 250 We scan these two rows of zeros and ones until we locate the rst instance of a disagreement between them In the column where it occurs the nim sum of y and 2 is one This means that the nim sum of 2 21 2k is also equal to one in this column Thus 2 E N We have checked the second condition that we needed and so the proof of the theorem is complete D Example the game of rims In this game a starting position consists of a nite number of dots in the plane and a nite number of continuous loops Each loop must not intersect itself nor any of the other loops Each loop must pass through at least one of the dots It may pass through any number of them A legal move for either of the two players consists of drawing a new loop so that the new picture would be a legal starting position The players aim is to draw the last legal loop We can see that the game is identical to a variant of nim For any given position think of the dots that have no loop going through them as being divided into different classes Each class consists of the set of dots that can be reached by a continuous path from a particular dot without crossing any loop We may think of each class of dots as being a pile of chips like in nim What then are the legal moves expressed in these terms Drawing a legal loop means removing at least one chip from a given pile and then splitting the remaining chips in the pile into two separate piles We can in fact split in any way we like or leave the remaining chips in a single pile This means that the game of rims has some extra legal moves to those of him However it turns out that these extra make no difference and so that the sets N or P coincide for the two games We now prove this Thinking of a position in rims as a nite number of piles we write Pmm and Nmm for the P and N positions for the game of nim so that these sets were found in Bouton s Theorem We want to show that p mm and that N NW 2 Lectures 4 56 5 where here P and N refer to the game of rims What must we check Firstly that O E P which is immediate Secondly that from any position in NMm we may move to Pmm by a move in rims This is ne because each nim move is legal in rims Thirdly that for any 3 E Pmm any rims move takes us to a position in Nm39m If the move does not involve breaking a pile then it is a nim move so this case is ne We need then to consider a move where y is broken into two parts u and 1 whose sum satis es n1 lt 3 Note that the nim sum uEBv of u and 1 is at most than the ordinary sum u 1 this is because the nim sum consists of the sum of the odd powers that appear in the expression for u 1 as a sum of powers of two that is it involves omitting from this expression certain powers of two Thus u 69 11 S u 11 lt 31 So the rims move in question amounted to replacing the pile of size 3 by one with a smaller number of chips u 69 1 Thus the rims move has the same effect as a legal move in nim so that when it is applied to y E Pmm it produces a position in Nmm This is what we had to check so we have nished proving Stat 155 Game theory Yuval Peres Lectures 1415 Fall 2004 The game of battleship and salvo A battleship is located on two adjacent squares of a three by three grid shown by the two Xs in the example A bomber who cannot see the sub merged craft hovers overhead He drops a bomb denoted by B in the gure on one of the nine squares He wins if he hits and loses if he misses the sub marine There are nine pure strategies for the bomber and twelve for the submarine That means that the payoff matrix for the game is pretty big We can use symmetry arguments to simplify the analysis of the game Indeed suppose that we have two bijections glzmovesofIHmovesofI and 92 moves ofII a moves ofII for which the payoffs aij satisfy 1940310 127 1 If this is so then there are optimal strategies for player I that give equal weight to 912 and 2 for each 2 Similarly there exists a mixed strategy for player I that is optimal and assigns the same weight to the moves 92 and j for each 9 In the example we may take 91 to the the map that ips the rst and the third columns Similarly we take 92 to do this but for the battleship location Another example of a pair of maps satisfying 1 for this game 91 rotates the bomber s location by 90 degrees anticlockwise whereas 92 does the same for the location of the battleship Using these two symmetries we may now write down a much more manageable payoff matrix BOMBER corner Lectures 1415 2 These are the payoff in the various cases for play of each of the agents Note that the pure strategy of corner for the bomber is this reduced game in fact corresponds to the mixed strategy of bombing each corner with 14 probability in the original game Similarly for each of the pure strategies in the reduced game We use domination further to simplify things For the bomber the strategy midside dominates that of corner We have busted down to SHIP centre off centre BOMBER midside 1 4 1 4 middle 1 0 Now note that for ship that is trying to escape the bomb and thus is heading away from the high numbers on the table off centre dominates centre SHIP off centre BOMBER midside 1 4 middle 0 The bomber picks the better alternative technically another application of domination and picks midside over middle The value of the game is 14 the bomb drops on one of the four middles of the sides with probability 14 for each and the submarine hides in one of the eight possible locations that exclude the centre choosing any given one with a probability of 18 Preparing for the proof of the minimax theorem We mentioned that convex geometry plays an important role in the Von Neumann minimax theorem Recall that De nition 1 A set K Q Rd is convex if for any two points ab E K the line segment that connects them 233 1 imb 1p 6 07 ll also lies in K The main fact about convex sets that we will need is Theorem 1 Separation theorem for convex sets Suppose that K Q Rd is closed and convex IfO K then there exists z 6 Rd and c E R such that O lt c lt va for allvEK Lectures 1415 3 What the theorem is saying is that there is a hyperplane that separates 0 from K this means a line in the plane or a plane in R3 The hyperplane is given by X 6 Rd sz c The theorem implies that on any continuous path from O to K there is some point that gets mapped into the hyperplane Proof We may nd 2 E K for which 1 Hz 23 2 1 This is because the function K O x 6 Rd S R 7 000 v 7 with R large is continuous with its domain being a closed and bounded set Therefore it attains its in mum at a point that we have called 2 Since S R there can be no point in the part of K not in the domain of this map with a lower norm Choose 0 12z2 gt 0 We have to check that c lt zTv for each v E K To do so consider such a v For e 6 01 we have that V 17 ev E K Hence inf VEK Z2 S EV 1 EV2 EVT 1 VTr V 1 VT7 the rst inequality following from the fact that 2 has the minium norm of any point in K We obtain sz S ezvtv 17 gt2WTW 2517 VTW Multiplying out and cancelling an e 52vtz 7 vtv 7 ztz S 2vtz 7 ztz Taking e l 0 we nd that O S vtz 7 ztz which implies that vtz 2 20 gt c as required D

×

×

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

×

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

Bentley McCaw University of Florida

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

Allison Fischer University of Alabama

#### "I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over \$600 per month. I LOVE StudySoup!"

Steve Martinelli UC Los Angeles

Forbes

#### "Their 'Elite Notetakers' are making over \$1,200/month in sales by creating high quality content that helps their classmates in a time of need."

Become an Elite Notetaker and start selling your notes online!
×

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.