Date | Topic | Materials |
8/29, 8/31 | Course at a glance. What problems are we trying to solve? Example applications: game playing, security, elections, electronic marketplaces, resource allocation, ... |
Slides:
ppt, pdf. Optional readings: Some CACM articles: Computer Science and Game Theory, Making Decisions Based on the Preferences of Multiple Agents, Designing the Perfect Auction. EC 2018 proceedings. |
9/5, 9/7 | Linear, integer, and mixed integer programs. |
Homework 0 out. Slides: ppt, pdf. SLB Appendices A and B (if you need them). GNU Linear Programming Kit. Guide to the modeling language. Here are also lecture notes I wrote those for a course on linear and integer programming; if you want to learn more about these topics there may be some useful resources on that course's website. Example files: painting.lp, painting.mod. knapsack.lp, knapsack.mod. cell.lp, cell.mod, hotdog.mod. |
9/10 | ("Bonus" lecture.) Ridiculously brief introduction to theoretical computer science: computational problems, algorithms, runtime, complexity. |
Slides: ppt, pdf. Modeling files: set_cover.mod, set_cover2.mod, matching.mod. Sorting spreadsheet. CACM article on P vs. NP. |
9/12 | Risk neutrality and risk aversion. Expected utility theory. |
Slides: ppt, pdf. SLB Section 3.1. |
9/12-? | Games in normal form. Dominance and iterated dominance. Computing dominated strategies. Minimax strategies. Computing minimax strategies. Nash equilibrium. Computing Nash equilibria. Correlated equilibrium. Computing correlated equilibria. |
Slides: ppt, pdf. Slides for Yu's guest lecture. Homework 1 out. Optional: 3.3.4, 4.2.2. Paper on computing dominated strategies. (You can skip the part on Bayesian games.) Paper on computing Nash equilibria. (You only need to read the part concerning 2-player games.) Paper on computing special kinds of Nash equilibria. (You can skip everything from Bayesian games on.) |
9/24-? | Games in extensive form. Backward induction. Subgame perfect equilibrium. Imperfect information. Equilibrium refinements. |
Slides: ppt, pdf. SLB 5.1 (alpha-beta is optional), 5.2.1, 5.2.2. Optional: 5.2.3. Paper on finding optimal strategies to commit to. |