## Department of Electrical and Computer Engineering

### ECE 586GT: FALL 2017 Topics in Decision and Control: Static and Dynamic Game Theory

Exam 1 Solutions
COURE NOTES
LINK TO SPRING 2013 OFFERING OF COURSE

Description: Game theory is the theory of decision problems with multiple decision makers, often with conflicting objectives. The theory seeks to describe the actions of decision makers in various settings, and, in some cases, to aid in the design of incentives to steer the collective actions towards specified objectives. The course focuses on fundamental theory, with applications to a broad range of problems arising in networks, such as resource allocation, incentives for investment, and pricing.

Grading scheme: Homework (40%), two ninety minute midterms (20% each), project (20%).

Prerequisites: Familiarity with dynamic systems (at the level of ECE 515), background in probability theory (at the level of ECE 313, and preferably ECE 534), familiarity with the basics of linear and nonlinear programming (at the level of ECE 490).

Assigned Reading: There will be no required text, but there will be selected readings from books, journal papers, and other information availalble online.

Meeting times: 9:30-10:50 a.m. TuTh in 3015 ECE Building

Instructor: Professor Bruce Hajek

Teaching assistant: Muhammed Sayin

Office hours: BH: Wednesdays, 1-2pm, 105 CSL, MS: Mondays, 5-6pm, 101 CSL

Tentative summary of topics:

• I. Static games of complete information
• Dominant strategies, iterated elimination of dominated strategies, mixed strategies, Nash equilibrium, saddle-point theory,
• Conditions for existence, and conditions for uniqueness, of Nash equilibrium
• Correlated equilibria
• Fictitious play and convergence results
• Evolutionarily stable strategies (ESS) and evolutionarily stable states of replicator dynamics
• Trembling hand equilibrium
• Blackwell's approachability theorem and learning
• II. Dynamic games of complete information
• Extensive form games with imperfect information: normal form, subgame perfect equilibrium, sequential equilibria
• Multistage games with observed actions: one step deviation principle
• Repeated games: trigger strategies, feasibility theorems (aka folk theorems)
• III. Static games of incomplete information
• Bayes-Nash equilibrium
• IV. Mechanism design and the theory of auctions
• Vikrey second price auction and its generalization (VCG mechanism)
• Revenue optimal auctions (direct revelation principle, revenue equivalence, virtual valuations (Myerson theory)
• Equilbrium bidding strategies and revenue ordering for second price and ascending auctions with correlated private information (Milgrom and Weber theory)
• V. Coalitions in cooperative games
• Core, exchange economies with transferrable payments, Shapley value

About the project: For the project you are to choose a topic related to the course content and understand and critically evaluate two or three major papers in that area. Then demonstrate knowledge of the papers by working an example based on a paper or possibly extending the theory of a paper. You will need to write a project report of five to ten pages in length, and prepare a fifteen minute presentation.

Additional policy: Collaboration on the homework is permitted, however each student must write and submit independent solutions. Homework is due within the first 5 minutes of the class period on the due date. No late homework will be accepted (unless an extension is granted in advance by the instructor).

You may bring two sheets of notes to the first exam and three sheets of notes to the second exam. You may use both sides of the sheets, with font size 10 or larger printing (or similar handwriting size). The examinations are closed book otherwise. Calculators, laptop computers, tables of integrals, etc. are not permitted.