CS 269I: Incentives in Computer Science

Announcements

• Sept 26: Welcome to CS269I!

• Tim Roughgarden (Office hours (note new time): Mondays 12:15-1:15 PM, Gates 474. Email: tim@cs.stanford.edu.)

Course Assistants:

• Vaggos Chatziafratis (Office hours: Wednesdays 4-6PM, Gates 460. Email: vaggos@stanford.edu.) (Starting 10/5.)
• Okke Schrijvers (Office hours: Tuesdays 10:30AM-12:30PM, Gates 482. Email: okkes@stanford.edu.) (Starting 10/4.)
• Warut Suksompong (Office hours (note new time): Fridays 2-4PM, Gates 466. Email: warut@cs.stanford.edu.) (Starting 9/30.)

Time/location (new room!): 10:30-11:50 AM Mon/Wed in room 128 of the Education building.

Piazza site: Here

Prerequisites: Mathematical maturity at the level of undergraduate algorithms (CS161). Programming maturity at the level of 106B/X.

Course Description: Many 21st-century computer science applications require the design of software or systems that interact with multiple self-interested participants. This course will provide students with the vocabulary and modeling tools to reason about such design problems. Emphasis will be on understanding basic economic and game theoretic concepts that are relevant across many application domains, and on case studies that demonstrate how to apply these concepts to real-world design problems. Topics include auction and contest design, equilibrium analysis, cryptocurrencies, design of networks and network protocols, matching markets, reputation systems, and social choice. Possible case studies include BGP routing, Bitcoin, eBay's reputation system, Facebook's advertising mechanism, Mechanical Turk, and dynamic pricing in Uber/Lyft.

General references: Twenty Lectures on Algorithmic Game Theory, Cambridge University Press, 2016. See also the Amazon page.

• This textbook is based on the course CS364A. The overlap with 269I will be roughly 20-25%. Though if you enjoy this course, you're likely to also enjoy many of the topics in this book.

• Algorithmic Game Theory, Cambridge University Press, 2007. Read the entire book online by clicking here (look under the "Resources" tab).

• Parkes and Seuken, Economics and Computation (draft), 2016. (Stanford access only.)
• Easley and Kleinberg, Networks, Crowds, and Markets, 2010.

Lecture notes

• Lecture 1 (The Draw/College Admissions) [beta version]
• Lecture 2 (Stable Matching) [beta version]
• Lecture 3 (Strategic Voting) [beta version]
• Lecture 4 (Voting Rules as MLE/Knapsack Voting) [beta version]
• Lecture 5 (Incentives in P2P Networks) [beta version]
• Lecture 6 (Incentivizing Participation) [beta version]
• Lecture 7 (Selfish Routing) [beta version]
• Lecture 8 (Incentives in BGP Routing) [beta version]
• Lecture 9 (Incentives in Bitcoin) [beta version]
• Lecture 10 (Incentives in Crowdsourcing) [beta version]
• Lecture 11 (slides) (Incentives in Societal Networks) [guest lecture by Balaji Prabhakar]
• Lecture 12 (Reputation Systems) [beta version]
• Lecture 13 (Auction Basics) [beta version]
• Lecture 14 (Sponsored Search) [beta version]
• Lecture 15 (VCG Mechanism) [beta version]
• Lecture 16 (Revenue-Optimal Auctions) [beta version]
• Lecture 17 (Incentiving Forecasts and Feedback) [beta version]
• Lecture 18 (Prediction Markets) [beta version]
• Lecture 19 (Time-Inconsistent Planning) [beta version]
• Lecture 20 (Fair Division) [beta version]

Coursework

• Exercise Sets (50%): Exercise sets will be handed out on Wednesdays and will be due one week later. You can work in pairs, if you wish.
  • Here's a LaTeX template that you can use to type up solutions. Here and here are good introductions to LaTeX.
  • Week 1 Exercises
  • Week 2 Exercises
  • Week 3 Exercises
  • Week 4 Exercises
  • No exercises for Week 5!
  • No exercises for Week 6!
  • Week 7 Exercises
  • Week 8 Exercises
  • Week 9 Exercises

• Final Project (50%): For details and some example topics, see here.

Tentative Syllabus (will likely change)

• Week 1: Introduction to incentives through killer examples.
• Week 2: Social choice (voting, Arrow's impossibility theorem, etc.).
• Week 3: Incentives in peer-to-peer and social networks (e.g., incentives in BitTorrent).
• Week 4: Incentives in communication networks (routing, flow control, etc.).
• Week 5: Incentives in cryptocurrencies (like Bitcoin).
• Week 6: Reputation systems. Incentives in crowdsourcing.
• Week 7: Basic auction theory (eBay, sponsored search auctions).
• Week 8: Advanced auction theory and mechanism design (Facebook advertising auctions, contest design).
• Week 9: Scoring rules and prediction markets.
• Week 10: Lessons from behavioral economics (i.e., how do people make decisions, anyway?).

Detailed Lecture Schedule

• Lecture 1 (Mon Sept 26): The incentives of the Draw, past and present. Pareto optimality and strategyproofness. College admissions. One-sided vs. two-sided markets. The National Resident Matching Program (NRMP). Supplementary reading:
  • Check out the changes made to the Draw in 1970, as reported by the Stanford Daily. The other articles make for a fascinating time capsule, as well.
  • The original Gale-Shapley paper (1962). It's very easy to read!

• Lecture 2 (Wed Sept 28): Stable matchings. Properties of the deferred acceptance (Gale-Shapley) mechanism. Could college admissions go through a centralized clearinghouse? Supplementary reading:
  • Biró, Student Admissions in Hungary as Gale and Shapley Envisaged, 2008.
  • Section 2 of Lecture 10 from CS364A (or from the optional textbook).
  • The paper that compares the evolution of different resident-hospital matching algorithms in the U.K. (Roth, 1991).
  • Citation for the 2012 Nobel Prize (Roth and Shapley).

• Lecture 3 (Mon Oct 3): Participatory democracy. Strategic voting. Spoilers and the 2000 US election. Majority, plurality, ranked-choice voting, Borda counts. Gibbard-Satterthwaite and the impossibility of reasonable strategyproof voting rules. Arrow's Impossibility Theorem. Compromises, single-peaked preferences, and the median voting rule. Supplementary reading and resources:
  • Participatory budgeting in general and at Stanford.
  • The rank aggregation problem.
  • Reasonably short proofs of the Gibbard-Satterthwaite and Arrow impossibility theorems are here (see Sections 1.2.3 and 1.2.4).
  • Chapter 23 of the Easley/Kleinberg book (see general references).

• Lecture 4 (Wed Oct 5): Subjective vs. objective interpretations of voting rules. Metaphor: linear regression as the maximum likelihood solution with normally distributed errors. Marquis de Condorcet and majority rule as a maximum likelihood estimator. The Kemeny-Young rule. Knapsack voting and its properties. Supplementary reading and resources:
  • The dramatic life of Marquis de Condorcet.
  • See Pnyx for an implementation of the Kemeny rule.
  • Knapsack voting, by Goel/Krishnaswamy/Sakshuwong (2014).
  • Section 15.2 of the Parkes/Suen book (see general references).

• Lecture 5 (Mon Oct 10): Incentives in peer-to-peer (P2P) networks. History lesson: Napster, Gnutella, etc. Free riding on Gnutella. Prisoner's Dilemma. Repeated Prisoner's Dilemma: the grim trigger and Tit-for-Tat stategies. Tit-for-tat in the BitTorrent reference client. Strategic clients (BitThief and BitTyrant). Supplementary reading:
  • Chapter 5 of the Parkes/Seuken book draft, above.
  • Free Riding on Gnutella (Adar/Huberman, 2000)
  • The Axelrod tournaments: The Evolution of Cooperation (Axelrod/Hamilton, 1981)
  • Incentives Build Robustness in BitTorrent (Cohen, 2003) describes the motivation for the original design.
  • BitThief (Locher/Moor/Schmid/Wattenhofer, 2006)
  • BitTyrant (Piatek/Isdal/Anderson/Krishnamurthy/Venkataramani, 2007)

• Lecture 6 (Wed Oct 12): Coordination games. Technology adoption and network cascades. Individual vs. collective preferences in public good problems. Case study: badge design in Stack Overflow, Coursera, etc. Supplementary reading:
  • See CS 224W for much more on network cascades.
  • Steering User Behavior with Badges (Anderson/Huttenlocher/Kleinberg/Leskovec, 2013)
  • Engaging with Massive Online Courses (same authors, 2014)

• Lecture 7 (Mon Oct 17): Selfish routing and network over-provisioning. Braess's paradox and Pigou's example. The price of anarchy. Modest over-provisioning guarantees near-optimal routing.
  • Demonstration of Braess's paradox.
  • How Bad Is Selfish Routing? (Roughgarden/Tardos, 2000)
  • The Price of Anarchy is Independent of the Network Topology (Roughgarden, 2002)
  • See also Lectures 11 (Sections 1-3) and 12 (Section 1) from CS364A (or from the optional textbook).

• Lecture 8 (Wed Oct 19): The Border Gateway Protocol for Internet routing. Stable routings: non-uniqueness and non-existence. Dispute wheels and the convergence of BGP to a unique solution. Incentive issues. Incentive-compatability with path verification. Supplementary reading:
  • The Stable Paths Problem and Interdomain Routing (Griffin/Shepherd/Wilfong, 2002)
  • Stable Internet Routing Without Global Coordination (Gao/Rexford, 2001)
  • Interdomain Routing and Games (Levin/Schapira/Zohar, 2008)
  • A Survey of Interdomain Routing Policies (Gill/Schapira/Goldberg, 2013)
  • Latest draft of the BGPsec protocol (2016)

• Lecture 9 (Mon Oct 24): Incentives in Bitcoin mining. Transactions and the Bitcoin blockchain protocol. Forks. Incentive issues: the 51% attack, the double-spend attack, and selfish mining. Supplementary reading:
  • General reference: the book Bitcoin and Cryptocurrency Technologies. (Narayanan/Bonneau/Felten/Miller/Goldfeder, 2016)
  • See also Section 22.3 of the Parkes/Suen book (see general references).
  • Majority is not Enough: Bitcoin Mining is Vulnerable (Eyal/Gün Sirer, 2014)

• Lecture 10 (Wed Oct 26): Incentives in crowdsourcing. Bitcoin in a regime with high transaction fees. The DARPA Network Challenge and incentivizing recruitment. Sybil attacks and possible solutions. The "Wisdom of the Crowd": fact or fiction? Herding behavior and information cascades. Supplementary reading:
  • On the Instability of Bitcoin Without the Block Reward (Carlsten/Kalodner/Weinberg/Narayanan, 2016)
  • Time-Critical Social Mobilization (Pickard et al., 2011) describes the MIT group's winning strategy in the DARPA Network Challenge.
  • Less happy times in the 2011 DARPA Shredder Challenge.
  • On Bitcoin and Red Balloons (Babaioff/Dobzinski/Oren/Zohar, 2012)
  • Chapter 16 of the Easley/Kleinberg book (see general references).

• Lecture 11 (Mon Oct 31): Incentives in societal networks (guest lecture by Balaji Prabhakar). "Nudges" for changing behavior. Case studies in Bangalore, Singapore, and at Stanford.
  • Balaji's slides
  • An Incentive Mechanism for Decongesting the Roads: A Pilot Program in Bangalore (Merugu/Prabhakar/Rama, 2009)
  • INSINC: A Platform for Managing Peak Demand in Public Transit (Pluntke/Prabhakar, 2013)

• Lecture 12 (Wed Nov 2): Adverse selection, moral hazard, and reputation systems. The market for lemons. Analogs in health insurance, the labor market, and online platforms. Moral hazard. Reputational effects in the n-person Prisoner's Dilemma. Whitewashing and the pay-your-dues strategy. Sybil attacks. Case study: the evolution of eBay's reputation system. Supplementary reading:
  • Chapter 27 of the AGT book (see general references).
  • Chapter 20 of the Parkes/Suen book (see general references).
  • Sections 22.5-22.9 of the Easley/Kleinberg book (see general references).
  • The Social Cost of Cheap Pseudonyms (Friedman/Resnick, 2001)
  • The evolution of the eBay reputation system: The Limits of Reputation in Platform Markets: An Empirical Analysis and Field Experiment (Nosko/Tadelis, 2015)

• Lecture 13 (Mon Nov 7): Auction design basics. How would you bid in a first-price auction? The Vickrey auction and truthfulness. Welfare maximization. Introduction to sponsored search auctions.
  • This lecture is based on Lecture 2 from CS364A (or from the optional textbook).
  • Optional: The Economics of Internet Search (Varian, 2006)

• Lecture 14 (Wed Nov 9): The theory of first-price auctions. Externalities. VCG: a truthful sponsored search auction. GSP vs. VCG. Supplementary reading:
  • See Section 2.3 of Hartline's book for more about the Bayes-Nash equilibria of first-price auctions.
  • Sponsored search: see AGT book, Sections 28.1-28.3.1 (see general references).
  • Internet Advertising and the Generalized Second Price Auction: Selling Billions of Dollars Worth of Keywords (Edelman/Ostrovsky/Schwarz, 2007)
  • Position Auctions, (Varian, 2007)
  • See also this CS364B course for tons of subtopics and references on sponsored search auctions (circa late 2007).

• Lecture 15 (Mon Nov 14): Revenue equivalence of the GSP and VCG sponsored search auctions. VCG in AdSense and Facebook. The general VCG mechanism and its truthfulness. Practical issues with VCG. Supplementary materials:
  • The VCG Auction in Theory and Practice (Varian/Harris, 2014)
  • On How Machine Learning and Auction Theory Power Facebook Advertising, talk by Eric Sodomka (2015).

• Lecture 16 (Wed Nov 16): Revenue maximization. Bayesian optimal auctions. Monopoly prices. Optimality of Vickrey with a monopoly price reserve. Case study: reserve prices in Yahoo! keyword auctions. Prior-independent auctions and the Bulow-Klemperer theorem. Further reading:
  • For more details and proofs, see Lectures 5 and 6 from CS364A (or the optional textbook).
  • Ostrovsky/Schwarz, Reserve Prices in Internet Advertising Auctions: A Field Experiment, 2009.

• Lecture 17 (Mon Nov 28): Strictly proper scoring rules. Incentivizing honest opinions. Output agreement. Peer prediction. Further reading:
  • Section 27.4 of the AGT book (see general references).
  • Chapter 17 of the Parkes/Suen book (see general references).

• Lecture 18 (Wed Nov 30): Prediction markets. The Iowa Electronic Markets and continuous double auctions. The Policy Analysis Market and the Wisdom of Crowds. Market scoring rules and automated market-makers. Further reading:
  • Chapter 26 of the AGT book (see general references).
  • Chapter 18 of the Parkes/Suen book (see general references).
  • The Policy Analysis Market: A Thwarted Experiment in the Use of Prediction Markets for Public Policy (Hanson, 2007)

• Lecture 19 (Mon Dec 5): Behavioral economics. Time-inconsistent planning: procrastination, choice reduction, and undue obedience. Upper and lower bounds on cost ratios. Naive vs. sophisticated agents. Further reading:
  • Procrastination and Obedience (Akerlof, 1991)
  • Time-Inconsistent Planning (Kleinberg/Oren, 2014)
  • For tighter bounds, see Computational Issues in Time-Inconsistent Planning (Tang/Teng/Wang/Xiao/Xu, 2015)
  • Planning Problems for Sophisticated Agents with Present Bias (Kleinberg/Oren/Raghavan, 2016)

• Lecture 20 (Wed Dec 7): Fair division. The cut and choose protocol and envy-freeness. The Selfridge-Conway envy-free protocol for 3 players. Recent advances for 4 or more players. The rent division problem, and the maxmin envy-free solution. Further reading:
  • Quanta article about recent advances in envy-free cake-cutting (Klarreich, 2016)
  • A Discrete and Bounded Envy-free Cake Cutting Protocol for Any Number of Agents (Aziz/Mackenzie, 2016)
  • Which Is the Fairest (Rent Division) of Them All?, (Gal/Mash/Procaccia/Zick, 2016)
  • Fair division in practice: spliddit