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 9am10.15am; all lectures are posted in the calendar. The zoom link to the lectures is here.
The lectures will be recorded, but your attendance and participation is highly encouraged. There will also be plenty of office hours, both by the TAs and by the instructor.
Office hours:

Instructor: Rafael Mon/Wed 10.1510.45am (will only discuss material in lectures, not HW).
Rafael's Zoom room.  TA: Cody Freitag, Tuesday 9am10am and Friday 11am12pm (for questions about HW or course material in general) Cody's Zoom room
 TA: Benjamin Chan, 6pm7pm on Mon (for questions about HW and course materials). Ben's Zoom room
Contact:
 TA: Cody Freitag: crf87@cornell.edu
 TA: Benjamin Chan: byc25@cornell.edu
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: [PassTseng]
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 “latedays” that you can use throughout the semester, except on the last HW. HW due dates:
 HW 1: March 3
 HW2: March 31
 HW 3: April 28
 HW 4: May 20 (this is a firm deadline, no "latedays" allowed)
HW 4 will contain a review component that you need to complete individually.
The grade is based on your performance on the homework, 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.
Slack
We will use slack as the main communication channel with the TAs and for questions about the homeworks. The (temporary) link to join is here: SLACK
Reading
Required: We will be closely following the material from the book Networks and Markets: Gametheoretic Models and Reasoning (The MIT Press, 2019) (NM below). A free online 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 online 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: [PassTseng]
Topics Outline (subject to change)

Introduction [preface in the NM, Chapter 1 in KE]
 Game Theory [Chapter 1 in NM, Chapter 6 in KE]
 Definition of a Game
 Dominanted strategies, and iterated deletion procedures
 Nash Equilibrium
 Best response dynamics.
 Graph Theory [Chapter 2,4 in NM, Chapters 24 excl. adv material, 10.110.2, 10.6, 13 in KE]
 directed, undirected graphs; paths and connectivity
 connected components; the giant component and the internet
 shortest paths and the small world phenomena
 maxflow, mincut, edgedisjoint paths
 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]
 Bestresponse dynamics as graph traversal; ordinal potential games
 Coordination games on networks (the iPhone/Andoid game);
 Contagion in networks: what makes a node “influential”
 Traffic Networks; Braess “paradox”
 Markets and Auctions on Networks [Chapter 7,8,9 NM; Chapters 9,10,15 in KE]
 Matching markets, market clearing prices.
 Exchange networks
 Auctions and the VickeryClarkGrove (VCG) mechanism
 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]
 Voting, strategyproofness
 Gibbard’s impossibility results
 Singlepeaked preferences and the Median Voter theorem
 The House Allocation problem
 Twosided Matching, The Stable Marriage problem
 The PageRank and Hubs and Authority Algorithms: using links as “votes”
 Manipulation of search algorithms: search engine optimization
 Information and Belief [Chapters 15,16,17 in NM]
 The “Wisdom” of crowds: The Chernoff Bound
 The “Foolishness” of Crowds: Information Cascades; Information Cascades with costly information gathering
 Kripke’s possible worlds models of knowledge; common knowledge
 The Muddy Children Puzze, Can we Agree to Disagree and the NoTrade Theorem
 Common Knowledge of rationality as a characterization of iterated removal of strictly dominated strategies
 The power of higherorder beliefs: Valuation “Bubbles”
 Markets with Network effects [Chapter 18 in NM]
 Price v.s. Demand in markets without network effects
 Price v.s. Demand in markets with network effects; selffulfilling equilibria
 Markets with asymmetric information: market crashes (the market for lemons) and signaling models