Game Theory

Game Theory: An Introduction
Derek Hao HU
HKUST COMP221, Fall 2007

Is this game theory?
• We’ve learnt minimax (adversarial search)
– Perfect play for deterministic games
– Idea: Choose move to a position with highest minimax
value.
– Goal: Find optimal moves

11/28/2007

HKUST COMP221, Fall 2007

2

What is game theory?
• We focus on games where:
There are at least two rational players
Each player has more than one choices (moves, strategies)
The outcome depends on the strategies chosen by all players; 
there is strategic interaction

• Example: Six people go to a restaurant.
Each person pays his/her own meal – a simple decision problem
Before the meal, every person agrees to split the bill evenly 
among them – a game

11/28/2007

HKUST COMP221, Fall 2007

3

What is game theory?
• Game theory is a formal way to analyze 
strategic interaction among a group of rational 
players (or agents) who behave strategically
• Game theory has applications
Economics
Politics
Biology
Computer Science
Etc…
11/28/2007

HKUST COMP221, Fall 2007

4

Nobel Prizes
• 1994, John Harsanyi, John Forbes Nash and Reinhard Selten, 
WON NOBEL PRIZE IN ECONOMIC SCIENCES, “for their 
pioneering analysis of equilibria in the theory of non‐
cooperative games”.
• 2005, Robert Aumann, Thomas Schelling, WON NOBEL PRIZE 
IN ECONOMIC SCIENCES, “for having enhanced our 
understanding of conflict and cooperation through game 
theory analysis”.
• 2007, Leonid Hurwicz, Eric Maskin and Roger Myerson, WON 
NOBEL PRIZE IN ECONOMIC SCIENCES, “for having laid the 
foundations of mechanism design theory”.
11/28/2007

HKUST COMP221, Fall 2007

5

Game Theory vs. Combinatorial Game 
Theory
• They DIFFER in nature!
– In this lecture, we focus on game theory.
– Combinatorial Game Theory only studies two‐player games which 
have a position in which the player take turns changing in defined ...