IA168 Algorithmic Game Theory
Survey
Tomáš Brázdil
364
Evaluation
� Oral exam
� Homework
(occasionally)
Strictly dominated strategies for the exam:
� No preparation (skim-through)
� Learn only a strict subset
THE strictly dominant strategy:
Learn all definitions, algorithms, theorems and proofs.
365
What we did ...
Types of games:
� strategic-form games
� extensive-form games
� (strict) incomplete information games & Bayesian games
Types of strategies:
� pure
� mixed
366
What we did ... strategic-form games
Solution concepts:
� strictly dominant strategy equilibrium
� iterated elimination of strictly dominated strategies
� rationalizability
� Nash equilibria
We studied all these concepts in both pure and mixed strategies.
We studied computational complexity of solving strategic-form games
w.r.t. all above concepts.
In particular, we considered classical algorithms for computing mixed
Nash equilibria for two-player games:
� support enumeration
� Lemke-Howson
For zero-sum two-player games a polynomial time algorithm based
on von Neumann’s theorem was presented.
367
What we did ... extensive-form games
We considered three levels of expressiveness:
� perfect-information extensive-form games
� imperfect-information extensive-form games
� perfect and imperfect-information extensive-form games
with chance nodes
In all cases we considered the following types of strategies:
� pure
� mixed
� behavioral
Solution concepts:
� Nash equilibria
� subgame perfect equilibria (SPE)
368
What we did ... extensive-form games ... results
For finite perfect-information extensive-form games:
� there always exists a pure strategy SPE (in pure as well as
behavioral strategies)
� backward induction for computing SPE (can be used also
for perfect-information games with chance nodes)
� equivalence of mixed and behavioral strategies
For finite imperfect-information extensive-form games:
� there always exists a behavioral strategy Nash equilibrium
� backward induction on "perfect information" nodes
� mixed and behavioral strategies are not equivalent in
general, they are equivalent for games with perfect recall
369
What we did ... repeated games
Strategic-form games played repeatedly for either finitely many,
or infinitely many rounds.
Behavior of players may depend (arbitrarily) on the history of
the play.
They are a special case of imperfect-information extensive-form
games.
Solution concepts:
� For finitely repeated: average payoff (sum of payoffs)
� For infinitely repeated:
� discounted payoff
� long-run average payoff
We have considered only pure strategies.
370
What we did ... repeated games ... results
For finitely repeated:
� There is a unique SPE if the strategic-form game has
a unique pure str. NE
� SPE obtained by iterating a NE from the strategic-form
game
� other SPE (punishing equilibria)
For infinitely repeated:
� discounted payoff:
� one-shot deviation property iff SPE
(for bounded payoff functions)
� grim trigger strategy profiles & simple Folk theorem for SPE
(for bounded payoff functions)
� an approximate version of general Folk theorem for SPE
(repeated finite strategic-form games only)
(feasible payoffs)
� long-run average payoff:
� (almost) general Folk theorems for SPE and NE
(repeated finite strategic-form games only)
(feasible and individually rational payoffs) 371
What we did ... incomplete information games
� strict incomplete information games
� solution concepts: weak dominance, ex-post-Nash
equilibrium
� Bayesian games
� solution concepts: weak dominance, Bayesian Nash
equilibrium
Only pure strategies.
Auctions:
� Second-price auction:
� truth telling strategies are weakly dominant in both strict
imperfect information as well as Bayesian model
� First-price auction:
� Bayesian games needed to obtain a solution, solved for
uniform common prior
Revenue equivalence.
372