## Sunday, October 8th, Introduction to Game Theory

Game theory is the study of rational players' behaviors and different games, or situations.

Denote (a,b) be the payoffs, or the rewards, to players a and b.

We started with a few examples of simple games, including:

The prisoner's dilemma, with both players confessing yielding in (-5,-5), both denying yielding in (-2,-2), but one player confessing yielding in -1 for that player and -10 for the other.

The take or pass game, with the player receiving n and the other player receiving 0, or repeating the game but increasing n by 1, and changing the player that decides.

The dictator's game, where a player decides the splitting of the payoffs and another player decides whether that is accepted or both get 0.

The volunteering game, where a player can decrease their own payoff by 3 in exchange for increasing everyone else's payoff by 1

Rock, Paper, Scissors.

In order to determine the logical decisions at each situation, we define dominant strategies to be the strategy for the given player that maximizes their payoff irrespective of the other player's decisions. In other words, it is the best (or one of the best) choice for yourself no matter the circumstances.

Dominant strategies do not necessarily exist. There could also be more than 1.

Nash Equilibrium is the outcome(s) at which neither players can change their decisions to improve their payoff. i.e., there is no incentive to cheat, and this is always achieved in a game with 2 infinitely smart and logical players.

If a dominant strategy exists, there is almost always at least 1 nash equilibrium. If both players have 1 dominant strategy, there is guaranteed to be exactly 1 nash equilibrium.

Of the games mentioned above, all of them but rock paper scissors have nash equilibriums. In the dictator's game, there are multiple.

Learning about all of these, we can make better decisions in real life situations, and it really helps with problem solving. For example, let's look at the following problem I learned from a Chinese Mathematic Olympiad book:

5 Pirates, A,B,C,D,E, found a treasure consisting of 100 gold coins. They decide to use the traditional way of determining who gets how much.

Firstly, A proposes a way to split the coins. If he gets at least half of the votes (including his own), then the proposal is accepted and everyone gets that amount of coins. If he does not get at least half of the votes, however, he is executed.

If A gets executed, B proposes a way to split the coins. If B gets at least half of the votes (including his own), the the proposal is accepted and everyone gets that amount of coins. Otherwise, B gets executed.

Repeat the process until only E remains, or a proposal gets passed.

Assuming that all pirates are infinitely smart and perfectly logical, and will vote in favor of execution of the pirate if they get the same number of coins regardless of their vote. If you are Pirate A, how should you split the coins so that you get as many as possible, without dying?

This might seem like an extremely hard situation, with A keeping little coins to himself and using almost all coins to make the other members happy. However, this is not true. We can think backwards and use Nash Equilibria to solve this problem.

If only E remains, he gets to keep all coins to himself, which is nice for E.

If only D and E remains, E will disagree with the proposal regardless of the split, but D himself gets 50% of the votes from his own. Therefore, D can simply keep all 100 coins to himself. This is a nash equilibrium because E cannot change votes to obtain more coins than 0, and D has no incentive to change votes or the proposal.

If C, D, and E remains, all C needs to do is get the vote from either D or E. He can give E 1 coin and keep the rest to himself. If E disagrees, he will receive 0 from D's proposal. Therefore, E will vote in favor of C's proposal. This is again a nash equilibrium.

If B,C,D, and E remains, B needs 1 vote from C, D, or E. It is simply not efficient to give C all 100 coins to get the vote. B can either use 1 coin to get D's vote or 2 coins for C's vote. B can get a maximum of 99 coins if he gives 1 coin to D.

Finally, the initial situation. A needs 2 votes from B, C, D, and E. Note that in B's proposal, C and E both receive 0 coins, so A can simply give each one of them 1 coin to get their vote, keeping 98 coins to himself. This leads us to the nash equilibrium of the initial problem.

To summarize, this is a mathematical way to quantify "thinking logically" by creating all the possible outcomes visually. It is also a very useful tool to determine your best action, if it exists, and to break down complicated scenarios into simpler ones.

Game theory, dominant strategies, and nash equilibria can be much more complicated, and if you are into game theory, you should explore mixed strategy equilibria, collusion to create nash equilibria, and other interesting topics by google-ing or asking me. Hope to see you in future sessions!

## Comments