Instructors: Dave Pennock (dpennock@dimacs.rutgers.edu) and Ariel Schvartzman (as3569@dimacs.rutgers.edu).
Purpose and goals: The purpose of this course is to offer a graduate-level introduction to algorithmic game theory and mechanism design. The course will introduce algorithmic tools that align the interests of possibly strategic and selfish users with those of a designer or central planner. Applications include problems like voting, routing packets over a network, auction design and matching markets. By the end of the course, students should be able to reason about the ways in which users may manipulate algorithms as well as how to design algorithms that preclude this behavior.
Expected Background: This is intended as an introductory graduate course. Students should have prior exposure to algorithmic tools such as randomized algorithms, linear programming and duality, graph algorithms and discrete structures. Students should be mathematically mature and will be expected to write proofs and read research papers.
Voting, Elections, Rankings: May’s Theorem. Arrow’s Impossibility Theorem. Gibbard-Satterthwaite Theorem. Single-peaked preferences and Median Voting. Manipulations in Voting. Picking more than one Alternative. Selecting a Committee Board. Equitable Voting.
Games and Equilibria: Dominant, dominated strategies. Normal form games, expanded form games. Nash-Equilibria, Bayes-Nash Equilibria. Subgame perfect equilibria. Backward induction. Min-max Theorem. Computing Equilibria in 2-Player Zero-Sum Games. Computing Equilibria in General 2-Player Games. Lemke-Howson Algorithm. Correlated and Coarse Correlated Equilibria. No regret-learning in games. Multiplicative Weights Algorithm. Price of Anarchy/Price of Stability. Braess’ Paradox. Selfish routing.
Mechanism Design and Auctions: First-price, second-price, ascending price, English auctions. Bidding strategies. Revenue Equivalence Theorem. Revelation Principle. Myerson’s Optimal Auction for single-item settings. Vickrey-Clarke-Groves Mechanism. More complex settings: ad-auctions, combinatorial auctions, etc. Online and Approximation algorithms. Prior-Independence, Bulow-Klemperer and related results. Correlated bidders: Cremer-McLean, Ronen’s auction. Robust Mechanism Design.
Mechanism Design Without Money: Matching Markets for School Choice. Stable Matchings. Gale-Shapley and Deferred Acceptance. Matching Markets for One-sided Preferences (e.g. housing, roommates). Other applications: kidney exchange, blood transfusions.
Forecasting: Prediction Markets. Proper Scoring Rules, Shared Scoring Rules, Forecasting contests
Fair Division: Cake Cutting. Indivisible goods. Participatory Budgeting.
Decentralized Markets: The Bitcoin Protocol and Selfish Mining.
Homework assignments: 60%, 5 or 6 homework assignments in total, one every two weeks.
Final Project: 30%.
In-class participation: 10%.
Handbook of Computational Social Choice by Brandt, Connitzer, Endriss, Lang and Procaccia (see Ariel's link for instructions).
Game Theory, Alive by Karlin and Peres.
Algorithmic Game Theory by Nisan, Roughgarden, Tardos and Vazirani (see "The AGT Book" and follow Tim's link).
Twenty Lecture in Algorithmic Game Theory by Roughgarden. The book is not available online as far as I know but it is based on Tim's lecture notes for the course Incentives in Computer Science.
Rutgers Computer Science Department is committed to creating a consciously anti-racist, inclusive community that welcomes diversity in various dimensions (e.g., race, national origin, gender, sexuality, disability status, class, or religious beliefs). We will not tolerate micro-aggressions and discrimination that creates a hostile atmosphere in the class and/or threatens the well-being of our students. We will continuously strive to create a safe learning environment that allows for the open exchange of ideas and cherished freedom of speech, while also ensuring equitable opportunities and respect for all of us. Our goal is to maintain an environment where students, staff, and faculty can contribute without the fear of ridicule or intolerant or offensive language. If you witness or experience racism, discrimination micro-aggressions, or other offensive behavior, you are encouraged to bring it to the attention to the undergraduate program director, the graduate program director, or the department chair. You can also report it to the Bias Incident Reporting System http://inclusion.rutgers.edu/report-bias-incident/