CS 670 Exam 1 Review Sheet
Updated 6 October, 2007
- Framing of problem including diagram
- Shared consequences
- Sets of actions
- States of nature
- Different goals
- Different preferences
- Different utilities
- Payoff matrices
- 2 person, zero sum games
- 2 person, non-zero sum games
- 3 person, non-zero sum games
- Discuss normal and extensive forms
- what are they?
- how do you switch between them?
- how are they relevant for making choices?
- simultaneous moves versus turn-taking
- Utility
- lotteries
- axioms of preference
- constructing a utility
- proof of utility theorem
- Solution concepts
- Nash
- Pareto optimal
- Best response
- Strategically Dominant
- Minimax
- Satisficing equilibrium
- Mixed strategies:
- concept
- expected payoffs: how to use them
- fighters and bombers and similar problems
- Computing minimax strategies
- Computing minimax strategy in mixed strategy space for
two-action
games,
and 2x3 action games
- alpha-beta pruning
- Computing Nash equilibrium strategies
- Maximum security using "graphical intersection" technique
- Cournot adjustment
- Fictitious play
- Indifference points
- Evolutionary games
- Minimax proof
- Formalization of a 2 person, zero-sum game
- Formalization of a payoff for mixed strategies
- Security and maximal security.
- Regret and minimal regret.
- Relationship between maximin and minimax values.
- Nash's theorem
- Existence of the Nash equilibrium in all multiplayer games
- Equivalence of Minimax and Nash equilibrium in zero-sum games.
- Good against
- Extension of proof to 2 person, non-zero sum game
- Extension of proof to m person, non-zero sum game
- Fixed point theorem
- Transformations in function space.
- Fixed points.
- Existence of a fixed point implies existence of an
equilibrium.
- Existence of an equilibrium implies existence of a fixed
point.
- Topological closeness.
- Interesting games
- Prisoner's dilemma and free rider's dilemma
- Battle of the Sexes
- Chicken and volunteer's dilemma
- Leader
- Stag hunt
- Repeated play, and the emergence of cooperation
- Threats and bribes: how do they affect the payoff matrix
- Temporal discounting and probability of continued play
- A useful theorem sum_{i=0}^infty w^i = 1/(1-w)
- The Folk Theorem and trigger strategies
- Never forgive is a Nash equilibrium of the repeated play PD
- Repeated play prisoner's dilemma
- Tit for Tat
- TRSP, and characteristics of the dilemma
- Invasion
- Collectively stable
- Proofs of five interesting properties
- Ficitious play
- Cournot adjustment
- Using counting to form model probabilities
- Problems with correlated (temporal and across agents) choices
- Windowing counting history
- Discounting counting history
- Boltzmann model
- Evolutionary stable solutions
- Selection dynamics: which strategies get replicated and in
what proportions?
- Interaction dynamics: who plays whom?
- Equilibria and stable equilibria
- ESS may not always exist
- When does ESS implies NE and vice versa?
- Replicator dynamics and random pairings
- Relative fitness: difference and differential equations
formulation
- Imitator dynamics and neighborhood pairings