Table of Contents

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

    • TODO

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+)