## Game Theory

**Game Theory** encompasses a wide variety of games, but they all have a common factor: They all have situations of conflict or cooperation
- 2 or more parties will interact with each other

## Topics

- Impartial Combinatorial Games
- Zero-sum Games
- General sum games
- Nash equilibria
- Evoluationary games, ESs, correlated equilibria

- Mechanism Design

## A General-Sum Game

- (Taken from Ben Polak’s class at Yale)
- Take a paper and write your name on it. Then, write either \(\alpha\) or \(\beta\).
- Here are the payoffs:
- \(\alpha\) and \(\alpha\): Both get B-
- \(\beta\) and \(\beta\): Both get B+
- \(\alpha\) and \(\beta\): \(\alpha\) gets A, \(\beta\) gets C.

- There is a dominant strategy:
**Picking \(\alpha\)**.

## Nimble

- Game rules:
- Board with 8 spaces, numbered 1~8. There is 1 coin on the first space, 2 on the third, and 1 on the sixth.
- Each turn, one coin can be moved any number of spaces to the left.
- When a coin is moved off the board, it is removed from play.
- Win condition: Last player to move a coin wins.

- Solution: This problem reduces to a Tweedledum & Tweedledee Strategy

- Player first reduces to Tweedledum & Tweedledee
- Can computer first win?

## Impartial/Partial Games (??)

- Games that ahve the same options available to both players
- Examples: Chess, Checkers, etc.

## Combinatorial Games

- No randomness (Chess, Go, Tic-tac-toe)

## Payoff Diagram Syntax

Row \ Column |
\(\alpha\) |
\(\beta\) |

\(\alpha\) |
(B-, B-) |
(A, C) |

\(\beta\) |
(C, A) |
(B+, B+) |