ECE 586 Spring 2013: Topics for Midterm Exam I
- Normal or strategic form matrix games: Existence of a Nash equilibrium and its proof using the Kakutani fixed point theorem; sufficient conditions for uniqueness of NE for continuous games, dominant and dominated strategies; (deleting strictly dominated strategies does not eliminate any Nash equilibrium; if elimination of weakly dominated strategies leaves one strategy profile remaining that profile is a NE but there may exist other NE), convergence of best and better response dynamics for potential games
- Two-player zero-sum matrix Games: von Neumann's minimax theorem (every pair consisting of a min max strategy for player 1 and a max min strategy for player 2 is an NE, also called a saddle point). Min max and max min strategies can be found using linear programing (LP), the min max problem for player 1 is the LP dual of the max min problem for player 2. (A mixed strategy that yields the same payoff as the value of the game is not necessarily a saddle point.) Fictitious play for zero-sum games: fictitious play iterations in discrete time for zero-sum games; perturbation using the soft max function, continuous-time approximation and its convergence using a Lyapunov function
- Evolutionarily stable strategies (ESS) and classification of stable points of the replicator dynamics, for symmetric, two person games: equilibrium, stable equilibrium, asymptotically stable equilibrium. Proof of asymptotic stability of ESSs for replicator dynamics using divergence function as a Lyapunov function.
- Prediction based on experts, regret minimization, and a potential function; Hannan consistent estimators, Blackwell approachability theorem
- Extensive form games with imperfect information: Normal form representation, behavioral strategies, behavioral representation of a mixed strategy and equivalence for games with perfect recall, subgame perfect equilibrium, sequential equilibrium, trembling hand perfect equilibrium for normal form representation always exists and the corresponding behavioral strategy is a sequential equilibrium scenario.
- Also, make sure that you understand how to solve every homework problem and understand the proofs of all the results shown in class.
ECE 586 Spring 2013: Topics for Midterm Exam II
- Material for this exam could include anything from the topic list for exam I, noted above.
- Multistage games with observed moves: the one-step deviation principle for SPE.
- Repeated games: trigger strategies and the general feasibility theorems (aka folk theorems)
- Revenue optimal selling mechanisms (Myerson theory): revelation principle (mapping an equilibrium of any mechanism to a truthful reporting equilibrium for a direct mechanism), revenue equivalence for incentive compatible seller mechanisms (probability of winning function q_i(x) determines expected payment m_i(x)), virtual valuation functions, revenue optimal mechanisms.
- Auctions with interdependent signals (Milgrom-Weber theory) Affiliated random variables, symmetric Bayes-Nash equilibrium for symmetric signal distributions and payoff structure, for second price auctions and English (ascending price) auctions. Revenue comparisons (first, second, and English auction in symmetric setting with independent private values all yield the same revenue. For affiliated signals and values the revenue ordering is R(English) \geq R(2nd price) \geq R(first price) (though we didn't consider first price auctions with interdependent signals)
- Coalition games with transferable payments: Cohesive characteristic function, core, Bondareva-Shapely theorem giving necessary and sufficient condition for a non-empty core, k-fold replication of an coalition game with transferable payoffs had nonempty core for all k equal to a multiple of some positive integer K (Koneko & Wooders(1982) result), Shapley value.
Markets with transferable payment (the coalitional game form, competitive equilibrium pairs (p,z) with associated payoff vector being in the core, k-fold replica.)
