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
• Mech

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

Goobix Nim

• 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

• Payoff: (row, column)
Row \ Column $$\alpha$$ $$\beta$$
$$\alpha$$ (B-, B-) (A, C)
$$\beta$$ (C, A) (B+, B+)