Course Syllabus

Course Overview

The course examines how the computing, economic and sociological worlds are connected and how these connections affects these worlds. Tools from game theory and graph theory are introduced and then used to analyze network structures present in everyday life, with a focus on various types of markets. Topics covered include social networks, web search, auctions, matching markets, and voting.

Instructor: Rafael Pass

 

Lecture times & Office Hours

The lectures will be on Mon and Wed from 10.10am-11.25am

Office hours:

  • Instructor: Rafael Mon/Wed 11.25-11.55am (will only discuss material in lectures, not HW).
  • TA: Benjamin Chan. Wed 12-1pm (Bloomberg 260) and on request (for questions about HW or course material in general).

Contact:

Prerequisites

Basic familiarity with mathematical definitions and proofs. Familiarity with sets, basic probability and basic proof techniques are useful; see Chapters 1,2 and 5 in the following lecture notes: [Pass-Tseng]

You also need to be comfortable with programming. 

 

Grading

There will be 4 homeworks. Homeworks needs to be submitted 11:59 pm Eastern Time on the day it is due. Additionally, you have a total of 4 “late-days” that you can use throughout the semester, except on the last HW. HW due dates:

  • HW 1: Sep 23
  • HW2: Oct 18 
  • HW 3: Nov 18 
  • HW 4: Dec 9 (this is a firm deadline, no "late-days" allowed)

HW 4 will contain a review component that you need to complete individually.

Additionally, HW 4 contains an open-ended research/project question where you will be asked to apply concept from this class to a real-life problem; you may work in groups for this part of the HW and your write-up should be roughly 1 page.

The grade is based on your performance on the homeworks, with an additional 1% for course participation/quality of solutions.

 

Homework Policy

You are free to collaborate in groups of up to 3 students on the homework (in fact, it is highly encouraged!), but you must turn in your own individually written solution and you must specify the names of your collaborators. Additionally, you may make use of published material, provided that you acknowledge all sources used. Note that it is a violation of this policy to submit a problem solution that you are unable to explain orally to a member of the course staff. Problem sets need to be typed up. For more detailed information on the homework policy, see the guidelines on the front page of the homework.

 

Ed Discussion

We will use Ed Discussion as the main communication channel with the TAs and for questions about the homeworks. 

Reading

Required: We will be closely following the material from the book Networks and Markets: Game-theoretic Models and Reasoning (The MIT Press, 2019) (NM below).  A free on-line version is available here.

Optional: Supplementary material can also be found in the beautiful book Networks, Crowds and Markets (Cambridge University Press, 2010) by Kleinberg and Easley (KE). A free on-line version of the book is available here.

 For additional background on sets, proofs and probability theory, please consult the following lecture notes on discrete mathematics: [Pass-Tseng]

 

Topics Outline (subject to change)

  • Introduction [preface in the NM, Chapter 1 in KE]

  • Game Theory [Chapter 1 in NM, Chapter 6 in KE]
  1. Definition of a Game
  2. Dominanted strategies, and iterated deletion procedures
  3. Nash Equilibrium
  4. Best response dynamics.

 

  • Graph Theory [Chapter 2,4 in NM, Chapters 2-4 excl. adv material, 10.1-10.2, 10.6, 13 in KE]
  1. directed, undirected graphs; paths and connectivity
  2. connected components; the giant component and the internet
  3. shortest paths and the small world phenomena
  4. max-flow, min-cut, edge-disjoint paths
  5. bipartite graphs, maximum and perfect matching, the Hall Marriage problem

 

  • Games on Networks [Chapters 2,3,4,6 in NM, Chapters 8,19 in KE]
  1. Best-response dynamics as graph traversal; ordinal potential games
  2. Coordination games on networks (the iPhone/Andoid game);
  3. Contagion in networks: what makes a node “influential”
  4. Traffic Networks; Braess “paradox”

 

  • Markets and Auctions on Networks [Chapter 7,8,9 NM; Chapters 9,10,15 in KE]
  1. Matching markets, market clearing prices.
  2. Exchange networks
  3. Auctions and the Vickery-Clark-Grove (VCG) mechanism
  4. Auctions in matching markets; VCG and the Generalized Second Price (GSP) Auctions; application to sponsored search.

 

  • Mechanisms with Money Transfers: Voting, Matchings and Web search [Chapters 10,11,12,13,14 in NM]
  1. Voting, strategy-proofness
  2. Gibbard’s impossibility results
  3. Single-peaked preferences and the Median Voter theorem
  4. The House Allocation problem
  5. Two-sided Matching, The Stable Marriage problem
  6. The PageRank and Hubs and Authority Algorithms: using links as “votes”
  7. Manipulation of search algorithms: search engine optimization

 

  • Information and Belief [Chapters 15,16,17 in NM]
  1. The “Wisdom” of crowds: The Chernoff Bound
  2. The “Foolishness” of Crowds: Information Cascades; Information Cascades with costly information gathering
  3. Kripke’s possible worlds models of knowledge; common knowledge
  4. The Muddy Children Puzze, Can we Agree to Disagree and the No-Trade Theorem
  5. Common Knowledge of rationality as a characterization of iterated removal of strictly dominated strategies
  6. The power of higher-order beliefs: Valuation “Bubbles”

 

  • Markets with Network effects [Chapter 18 in NM]
  1. Price v.s. Demand in markets without network effects
  2. Price v.s. Demand in markets with network effects; self-fulfilling equilibria
  3. Markets with asymmetric information: market crashes (the market for lemons) and signaling models

 

Detailed Schedule

Aug 25: Overview, Intro to Game-Theory

Aug 28 Basic Game-Theory

Sep 2: Labor Day [no class] 

Sep 4: More on Games, Basic Graph Theory

Sep 9: Best-response Dynamics (BRD) 

Sep 11: Coordination Games 1

Sep 16: Coordination Games 2

Sep 18: Recitation/Review of concepts for HW 1.

Sep 23: Cascades [HW1 due]

Sep 25: Flows and Matchings

Sep 30: Traffic Games [end of content for HW 2]

Oct 2:  Jewish Holiday: Rosh Hashana [no class], 

Oct 7: Matching Markets I

Oct 9: Recitation/Review of concepts for HW 2.

Oct 14: Fall Break [no class]

Oct 16: Matching Markets II [HW 2 Oct 18 due]

Oct 21: Exchange Networks

Oct 23: Mechanism Design I 

Oct 28: Mechanism Design II 

Oct 30: Mechanism Design III (end of content for HW 3)

Nov 4: Voting

Nov 6:  Two-sided Matchings

Nov 11: Recitation/Review of concepts for HW 3. 

Nov 13: Page Rank 

Nov 18: Wisdom/Foolishness of Crowds  [HW 3 due]

Nov 20: Knowledge I

Nov 25: Knowledge II [end of content for HW 4]

Nov 27: Thanksgiving [no class]

Dec 2:  Recitation/Review of concepts for HW 4

Dec 4: Guest Lecture: Yanyi Liu 

Dec 9: no class [HW 4 due]