|
|
Game theory studies mathematical models of the interaction of multiple agents, where each agent is rational. In a highly connected world where large populations commonly interact, game theory finds applications both in the analysis and design of systems.
This is an introductory course, and our goal in this course is to understand the fundamentals of game theory, particularly focusing on algorithmic aspects. We will introduce a number of widely-studied games, and analyse equilibria and related problems in their context. Topics that I plan to cover include: games and their representation; equilibria and notions of stability; zero-sum games; bimatrix games; potential games; learning dynamics and convergence to equilibria; games on networks; price of stability and price of anarchy; mechanism design; revenue maximization; approximately optimal auctions. |
|
|
While most of the course will be self-contained, some lectures will require a basic course in algorithms and complexity. |
|
|
Classes will be held Wed/Fri 11:30-1pm in A-212.
Classes begin on August 12th. Evaluation will be on the basis of assigments (50%), a final exam (25%), and a presentation (25%). |
|
|
Although most of what we cover is available in the reference materials below, we won't be following any particular book or set of notes too closely. An outline of the day's lecture, as well as links to particularly relevant material, will be put up here following the lecture.
|
|
|
Guidelines and suggested topics. |
|
|
|
| Introduced Prisoner's Dilemma and Rock-Paper-Scissors. Prisoner's Dilemma has a solution in strictly dominant strategies. Concocted a 2-player, 3-strategy game, which has a solution by iterated dominance. Introduced Battle of the Sexes, which has a pure Nash equilibrium. By Nash's theorem, every finite game (including Rock-Paper-Scissors) has a mixed Nash equilibrium.
References: Slides by Tayfun Sonmez until slide 20, for a good description of dominance and the classical games we talked about. Lecture notes by Costis for a more concise explanation with notation. Note that we haven't covered approximate equilibria, or the proof of Nash's theorem. | |
| Computation of equilibria in 2-player zero-sum games via linear programming duality.
References: Lecture notes by Costis. | |
| Characterization of Nash equilibrium in 2-player games in terms of equilibrium support. Affine transformations of the payoff matrices don't affect equilibria. An exponential support-enumeration algorithm for computing equilibria in 2-player games. Symmetric games, and reducing equilibria in general 2-player games to symmetric 2-player games.
References: Sections 2.1 and 3.2 of Costis' lecture notes. From the book Game Theory and Mechanism Design, Theorem 7.1 is our "equilibrium support" lemma for an arbitrary number of players, and Chapter 11 discusses in detail examples of equilibrium computation using the support enumeration algorithm. | |
| Computing a symmetric equilibrium in symmetric bimatrix games with the Lemke-Howson algorithm.
References: The remainder of Costis' lecture notes, and the discussion of L-H from Chapter 2 of the AGT book (which also presents the example we discussed). | |
| A proof of Nash's theorem via Brouwer Fixed-Point Theorem. Sperner's Lemma, and a proof of Brouwer Fixed-Point Theorem.
We only got as far as the proof of Nash's theorem via BFPT, and an intuitive proof of Sperner's Lemma in 2-D. References: Lectures 39 and 40 from the course taught by Eva Tardos. | |
| Continuing from the previous lecture: proof of Sperner's Lemma, and it's use in proving BFPT for the simplex.
Complexity of Nash. The classes FNP, TFNP (this is as far as we got in this lecture), and PPAD. 2-Nash cannot be FNP-complete, but is PPAD-complete, as are 2-Sperner and 2-Brouwer. References: Lectures 39 and 40 from the course taught by Eva Tardos, for the proof of Nash's theorem. For the second part of the lecture, see Tim's lecture notes. Also good to read is the survey article by Daskalakis, Goldberg, and Papadimitriou (note though that it expands upon the material covered in class, and the treatment is somewhat different, e.g., Sperner is introduced on the grid rather than the simplex.) | |
| Continuing from the previous lecture: Complexity of Nash: Clarifications regarding FNP. 2-Nash cannot be FNP-complete, but is PPAD-complete, as are 2-Sperner and 2-Brouwer (without proof).
Dynamics in games. Fictitious play. If FP converges to a pure strategy profile, this is a pure Nash equilibrium. If FP converges in a time-average sense, this is a mixed Nash equilibrium. References: See above for references for the first part of the lecture. For the second part, we will use Asu Ozdaglar's slides until slide 19; we won't cover continuous-time fictitious play. We will be doing the 2-player version of the proofs, though the slides give proofs for n-player games. | |
| Coarse-correlated equilibria, computation. No-regret dynamics (we only got this far), the multiplicative weights algorithm, and convergence to CCE.
References: Section 3 of lecture 13 from Tim's notes for CCE, and lecture 17 for no-regret algorithms. | |
| No class. | |
| Continuing from Sep 4: the multiplicative weights algorithm and no-regret dynamics. Convergence to CCE. Correlated equilibria and swap regret.
References: Previous references from Sep 4, and Section 1 of lecture 18 for CCE and swap regret. | |
| A black box reduction from no external regret to no internal regret. Best-response dynamics, network atomic congestion games, and potential games.
References: From Tim's notes: Section 2 of lecture 18 for the reduction. Section 1 of lecture 13 covers what we discussed to atomic network congestion games, refered to in the notes as atomic selfish routing games. | |
| No class. | |
| Introduction to the "social cost" of strategy profiles, and the Price of Anarchy. The price of anarchy in network atomic congestion games with linear cost functions is exactly 5/2. Introduction to global connection games, and an example with large price of anarchy.
References: The first part of the lecture is from Section 2 of lecture 12 from Tim's notes. The second part, about global connection games, is from Section 19.3 of the AGT book. | |
| Existence of a potential function for, and the price of stability in, global connection games. A facility location game. Existence of a potential function for facility location games. Valid utility games; the facility location game is a monotone valid utility game. The price of anarchy in monotone valid utility games is 2.
References: Sections 19.3 and 19.4 from the AGT book. | |
| Recap of the proof of PoA in valid utility and atomic network congestion games. Smooth games, and a generalization of the proofs of PoA. Extension of the bound to CCE and approximate PNE. Selfish load balancing games, and a proof that the PoA for PNE in these games is at most log m / log log m.
References: For smooth games, Tim's notes lecture 14, particularly Sections 3 and 4. For selfish load-balancing games, Chapter 20 from the AGT book, and in particular Theorem 20.7. I would recommend reading the proof of existence of PNE (Proposition 20.3) as well. | |
| No class. We will resume on October 14. | |
| Mechanism design and games. Voting and Condorcet's Paradox. A proof of Arrow's Impossibility Theorem: Any social welfare function over 3 alternatives that satisfies unanimity and independence of irrelevant alternatives must be a dictatorship.
References: AGT book, Chapter 9 until section 9.2.4. | |
| Incentive compatibility. Gibbard-Satterthwaite Theorem: If a social choice function is onto at least 3 alternatives and is incentive compatible, it must be a dictatorship. Proof from Arrow's theorem. Vickrey's second price auction. Mechanisms with money.
References: AGT book, Chapter 9 until Section 9.3.1. | |
| Formal definition of mechanisms with money, weakly dominant strategies, incentive compatibility. Started with the special case of single-parameter environments and Myerson's lemma for differentiable allocation rules.
References: Tim Roughgarden's notes for lecture 3. | |
| A different way to define single-parameter environments and mechanisms more directly. Myerson's lemma for piecewise-constant allocation rules. Sponsored search auctions.
References: Tim Roughgarden's notes for lecture 3, continued. | |
| Single-parameter mechanisms continued: multi-unit auctions, knapsack auctions, and approximating the social welfare in polynomial time (we didn't cover the revelation principle).
References: Tim Roughgarden's notes for lecture 4. | |
| No class. | |
| Revenue-maximizing mechanisms. We defined the Bayesian single-parameter setting, the virtual valuation of a bidder, and regular distributions. By the Revenue Equivalence principle, expected revenue = expected virtual surplus for monotone allocation rules. Thus if distributions are regular, the mechanism that maximizes virtual social welfare is revenue-optimal.
References: Tim Roughgarden's notes for lecture 5. | |
| Another look at revenue-maximizing mechanisms, and the ironing procedure. The quantile of a distribution. Virtual valuation is the gradient of the revenue curve w.r.t the quantile. Thus if virtual valuations are nondecreasing, the revenue curve is concave. For irregular distributions, can take convex hull of revenue curve, and use this to define "ironed" virtual valuation. Then optimal revenue is obtained by mechanism that maximizes "ironed" virtual social welfare.
References: Chapter 3 of the mechanism design book by Jason Hartline, especially Sections 3.3 and 3.4. | |
| No class. Homework submission deferred to Nov 12. | |
| Simple auctions. Stopping rules, and the prophet inequality for threshold stopping rules. Application to mechanism design to obtain a simpler single-item auction. The Bulow-Klemperer theorem: for a single item with iid bidder valuations, revenue obtained by Vickrey's auction with an additional bidder is at least that of the optimal auction.
References: Tim Roughgarden's notes for lecture 6. The lecture notes also discuss a case study which I recommend reading. | |
| Multi-parameter mechanism design: the VCG mechanism. Principle for designing payment rule: payments should depend on bid only through the allocation. Three different interpretations for the payment rule. Challenges with VCG mechanism, including false-name bids. Efficient approximation through Maximal-In-Range (MIR) mechanisms. An example of multi-unit auctions, with "m" identical copies of a single good, where "m" is exponentially large.
References: For VCG mechanism, Tim Roughgarden's notes for lecture 7. For MIR and multi-unit auctions, the material was taken from "Mechanisms for multi-unit auctions" by Dobzinski and Nisan, available here, particularly Section 3.2. | |
| Mechanisms without money. The Top Trading Cycles Algorithm (TTCA) for the house allocation problem (our definition of core is slightly different from that in the reference below; we define core in terms of blocking coalitions. The difference is important for the uniqueness of the core.) and kidney exchange. The DSIC maximum matching algorithm for kidney exchange.
References: Tim's notes for lectures 9 (Section 3 onwards) and 10 (Section 1). | |
|
|
|
| |