< back


Game Theory - Part I

[Web Version], [Moblie Version]

AUTHOR: Chaoqi Yang

DATE: 2019 / 3 / 23

1. Preview

I am longing to learn Game Theory, which feels like pretty cool before I get a hand on it. Now, I get the chance and time to learn systematically following Yale Open Class Game Theory 24 Series.It is really a good resource, so that I decide to write the lessons here, as a way to record my studying process and also share it to all of you.

2. Grade Game (Series 1)

2.1 The Game: game theory is about "Game", so let's start with a small game. Suppose that wehave two players: Alice and Bob, and their final grades of this class will be decided by their actions. Alice can choose a number from $\alpha$ and $\beta$, and Bob can also choose one from $\alpha$ and $\beta$. Now rules are below:

  • Alice chooses $\alpha$ and Bob chooses $\beta$, then Alice will get 'A' in this class, and Bob gets 'C'.
  • If Alice chooses $\beta$ and Bob chooses $\alpha$, then things get changed. Alicegets 'C' and Bob wins 'A'.
  • If Alice and Bob both choose $\alpha$, then they will get a same 'B-'.
  • If Alice and Bob both choose $\beta$, then they should get 'B+'s.

2.2 Math Tools: since it is about math, let's use matrix to present this game for each side. Supposethat Alice is me, and Bob is my pair, from our perspective, we can get differentpayoffs from this game according to our actions.

Of course, in game theory senario, a better way is to use a hybrid matrix. Becausethe above two matrices are identical in x-axis and y-axis, the only different lieson this entries, we can combine them using the following way. I need to emphasizethat this hybrid matrix is very important and useful in future game theory study.

2.3 What is your Decision? (Analysis): suppose you will play this game withme, then I believe the best result should be that you choose $\alpha$, and I chooses $\beta$, consequently yeilding 'A' for you. Pretty happy ha, however, for me, I will nottake a risk and does you such a big favor, so I am also likely to choose $\alpha$, as a result, we both get a 'B-'. Nevertheless, if we agree to choose $\beta$ simultaneously, then we can both get a 'B+'. So do you trust me?Do you dare to choose a $\beta$? No really, everybody will pick $\alpha$, but why?

2.4 Formally Analysis: the reason why we will both pick $\alpha$ rather than $\beta$ even if two $\beta$ will yeild a better situation than two $\alpha$ is that for one player, picking an $\alpha$ strictly dominates the action of pickinga $\beta$, because strategy $\alpha$ will always yield a better result than $\beta$regardless what your rival has picked.

(Strictly Dominating) strategy $\alpha$ strictly dominates $\beta$ if payoffs from $\alpha$ is strictly higher than that from strategy $\beta$ regardless of others' choices.

(Weakly Dominating) strategy $\alpha$ weakly dominates $\beta$ if payoffs from $\alpha$ is higher than or at least the same as that from strategy $\beta$ regardless of others' choices.
  • Lesson 1. We should never play a strictly dominated strategy.
  • Lesson 2. Rational play by rational players can lead to bad outcomes. (wisdom!)
  • Lesson 3. To figure out what actions you should choose in a game, a good first step is to figureout what are your payoffs (what do you care about) and what are other players' payoffs.
  • Lesson 4. If you do not have a dominated strategy, put yourself in your opponents' shoes totry to predict what they will do. For example, in their shoes, you would not choose a dominated strategy.

2.5 Something Interesting. Only about 15% of the Yale Econ class chose $\beta$ in the grade game. In larger experiments with normal people, about 30% choose $\beta$, which means people are tend to be 'evil'.

3. Choose $\frac23$ of The Avg. (Series 2)

We have played a game before, so let's look at the basic ingredients of a gameusing the following example.

3.1 The Game: Suppose that you are in a class with ~100 people, now everyone has to choose a number range from 1 to 100. The winner of this gameis the man whose number is the closest to $\frac23$ of the overall average of the class.

Example. If we get 5 people in the class, assume the numbers chosenby each guy are listed as 34, 12, 1, 44, 98. Then the average $\frac{34+12+1+44+98}{5}$ is 37.8, then the man/woman who chooses 34 is the winner.

3.2 Basic Ingredient.

  • (1) Players. We use notation like $i$ or $j$ to denote a player.
  • (2) Strategies. We use $s_i$ to denote the strategy of player $i$ and $s_{-i}$ to denote the combined strategy of all the other players.
  • (3) Payoffs. We use utility function over strategy to denote payoffs forplayer $i$, like $u_i(s_1, s_2, ..., s_n)$. Of course, payoffs of player $i$ can also be written as $u_i(s_i, s_{-i})$

3.3 Deletion: we can easily conclude that the biggest possiblesolution will be $\frac{100\times2}3$ = 66, where every other guy chooses 100. So wecan delete the choice (67, 100].

3.4 Stand on Others' Shoes: if everyone knows that no one willchoose a number from (67, 100], then what will happen? The upper boundary now is 66, so the biggest possible solution degrades to be $\frac{66\times2}3$ = 44.

3.5 Iterative Deletion: based on the notion stated in 3.3 and 3.4, we can narrow the possible solution scope from [0, 100] to [0, 66], from [0, 66]to [0, 44], from [0, 44] to [0, 29] ... finally the final solution should be 1, where everyone knows that if others are smart enough, and they (others) also knowthat others are smart from their respective view, then everyone will choose 1.

4. Stand on Others' Shoes (Series 2)

4.1 Problem. The question is quite simple as stated in thepayoff matrix. We have two players, the first player can move toward Top (T)or Bottom (B), while the second player can move towards Left (L), Center (C)or Right (R). Their payoffs according to action combination are shown below.

4.2 Analysis. We cannot find a dominating strategy for eitherplayer one or player two. However, when player 1 turn T, the best reaction of player 2 should be C; and when player 2 turn B, the best reaction of player 2is L, so that for player two, he/she will not turn R, Let us delete R!

4.3 Formal Notation.

(1). Player: 1, 2
(2). Strategies: s_1, s_2
(3). Payoffs: e.g., u_1(T, C)=11, u_2(B, L)=4
For player two, his/her strategy C(s_2) is strictly dominating strategy R(s_2'), because $\forall s_{-2}$, $u_2(s_2, s_{-2})$ > $u_2(s_2', s_{-2})$.

5. Median Voter Theorem (Series 3)

5.1 Problem. Suppose now there are two congressman who want torace for the president. And they can choose one position from 10 possible chairs.Now, all the voters can place their tickets on one place, and the congressman is able to win the vote if that place is closer to him. Also, votes are distributedevenly with respect to each position. If the vote to two congressman are of equaldistance, then they get half and half.

Example. if one congressman stands on Chair 2, and another standson Chair 6. Then the first congressman can get votes from Chair 1, Chair 2, Chair 3, and hald of Chair 4, and the second congressman can get votes from half of Chair 4, Chair 5, Chair 6, ... Chair 10. The race is about 3.5 : 6.5, then the second gentlemanwins.

5.2 Iterative Deletion: we can firstly compare several combination:

(1, 2):
for 1, payoff = 50%
for 2, payoff = 50%
(1, 2):
for 1, payoff = 10%;
for 2, payoff = 10% + 10% + ... + 10% = 90%
(1, 3):
for 1, payoff = 10% + 5% = 15%;
for 3, payoff = 5% + 10% + 10% + ... + 10% = 85%
...
(1, 9):
for 1, payoff = 10% + 10% + 10% + 10% + 5% = 45%
for 9, payoff = 5% + 10% + 10% + 10% + 10% + 10% = 55%
(1, 10):
for 1, payoff = 10% + 10% + 10% + 10% + 10% = 50%
for 10, payoff = 10% + 10% + 10% + 10% + 10% = 50%

5.3 Best Response: the strategy of standing on Chair 1 is a weakly dominated strategy! (Chair 10 is of the same mechaism)By knowing this, two congressmen will not choose Chair 1 or Chair 10, so that there are only 8 positionsleft. Iteratively, when we next delete Chair 2 and Chair 9, then delete Chair 3 and Chair 8 ... Only Chair 5 and Chair 6 will be left. In a nutshell, the center position is more favorable. This resultis found by Downs 1957 in "Political Science" and Hotelling 1929 in "Economics".

6. Nothing Dominated (Series 3)

6.1 Problem The problem is easily understood in matrix below. Please find the best Responsefor player 1 and player 2.

6.2 Best Reponse. For player 1, U is the best reponse against l and M is the bestreponse against r, but we cannot find an always winning strategy. We cannot expect our life to beguided under one strategy because it usually turns out just like this game, we cannot find a best action. For either player 1 or player 2, we need to take actions depended on the situations.

6.3 Expected Payoffs. Assume that player 2 do l and r in an equal frequency. For player 1, we can calculate his expected payoffs according to this matrix.

Expected Payoffs of U vs ($\frac12$, $\frac12$): $5\times\frac12 + 0\times\frac12 = \frac52$

Expected Payoffs of M vs ($\frac12$, $\frac12$): $1\times\frac12 + 4\times\frac12 = \frac52$

Expected Payoffs of R vs ($\frac12$, $\frac12$): $4\times\frac12 + 2\times\frac12 = \frac62$

However, in this sense, we still cannot say that R is the best reponse, we can only conclude that R is relatively better in player 2 ($\frac12$, $\frac12$) sistuation. The best way to solvethis issue is to list all the possiblility and pick the best combination if necessary.

[Resource Download]