Networks and Markets

Computer Science 5854
Cornell Tech
Fall 2016

Instructor: Rafael Pass

Time: M/W 4pm-5.15
Place: Big Red, Cornell Tech
Course Web page: http://www.cs.cornell.edu/courses/cs5854/2016fa/

TA: Andrew Morgan (asm354 at cornell.edu)

Office Hours: TBA

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, voting, and crypto-currencies (e.g. bitcoin).

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]

Course Administration

We are using the course management system, CMS.  Please login to http://cms.csuglab.cornell.edu/ and check whether you are registered. There will be a list of courses you are registered for, and CS 5854 should be one of them.  If not, please send your full name and Cornell netid to the TA so they can register you.  You can check your grades and submit homework in CMS. 

Grading

There will be 4-6 homeworks, and potentially a project.

Homeworks need to be handed in before the beginning of class. Additionally, you have a total of 4 “late-days” that you can use throughout the semester.

Homework Policy

You are free to collaborate with other students on the homework (in fact, I highly encourage you to work in pairs), 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. Assignments will be posted in CMS. Submit hardcopy in class or to the TA by the due date, or as a .pdf, .ps, .doc, or .txt file in CMS. Typed problem sets are strongly preferred.

Reading

We will largely follow the beautiful book Networks, Crowds and Markets (Cambridge University Press, 2010) by Kleinberg and Easley (KE). A complete free on-line version of the book is available at the Web page for the book.

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

Finally, DRAFT lecture notes (which only are minimally proof read) are posted here. These lecture notes may be lagging behind what we cover in class.

Topics Outline (subject to change)

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

• Graph Theory [Chapters 2-4 excl. adv material, 10.1-10.2, 10.6, 13 in KE; Chapter 2,3 in the notes]
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. the effect of local properties: triadic closure, strong and weak ties
5. max-flow, min-cut, edge-disjoint paths
6. bipartite graphs, maximum and perfect matching, the Hall Marriage problem

• Games on Networks [Chapter 8,19 in KE; Chapter 4,5,6 in the notes]
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”

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

• Bargaining in Networks
1. Bargaining and how to trade with outside options.
2. Stable and balanced outcomes; relationship to market clearing and VCG
3. Markets with intermediaries

• Web search and Voting
1. The PageRank and Hubs and Authority Algorithms: using links as “votes”
2. Converge and Interpretation of the PageRank Algorithm
3. Manipulation of search algorithms: search engine optimization
4. Voting, strategy-proofness
5. Gibbard’s impossibility results
6. Single-peaked preferences and the Median Voter theorem

• Information and Belief.
1. Kripke’s possible worlds models of knowledge; common knowledge
2. The Heart&Ace game
3. Common Knowledge of rationality as a characterization of iterated removal of strictly dominated strategies
4. The power of higher-order beliefs: Valuation “Bubbles”; connection to contagion
5. The “Wisdom” of crowds: The Chernoff Bound
6. The “Foolishness” of Crowds: Information Cascades; Information Cascades with costly information gathering

• Markets with Network effects
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

• Decentralized Currencies
1. Decentralized ledgers
2. Digital signatures and the Bitcoin system

• Towards “Physical Laws” governing Social Networks
1. The preferential attachment model and power laws
2. Small worlds models, decentralized search
3. Networks in the brain