Cornell Tech

Fall 2017

Instructor: Rafael Pass

Time: M/W 1.45-3pm

Place: B61, Cornell Tech

Course Web page: http://www.cs.cornell.edu/courses/cs5854/2017fa/

TAs:

· Andrew Morgan (asm354 at cornell.edu)

· Antonio Marcedone (a.marcedone at gmail.com)

Office Hours: TBA

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.

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]

We are using the course management system, **CMS**. Please login to
https://cmsx.cs.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.

There will be **4-6 homeworks**.

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.

You are free to collaborate with other students on the homework (in fact, I
highly encourage you to work in pairs or groups of 3), 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**.

We will be following the following [draft lecture notes]. These notes are only minimally proof read, and I may update them throughout the year. If you find typos, mistakes, or more generally things that are unclear, please let me know. You will get bonus point for every serious issue found (including the advanced section in the notes that we won’t cover in the course)!

A lot of supplementary material can also be found in 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 here.

* *

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

**Introduction**[preface in the notes, Chapter 1 in KE]**Game Theory**[Chapter 1 in the notes, 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 the notes, Chapters 2-4 excl. adv material, 10.1-10.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
- max-flow, min-cut, edge-disjoint paths
- bipartite graphs, maximum and perfect matching, the Hall Marriage problem

**Games on Networks [**Chapters 2,3,4,6 in the notes, Chapters 8,19 in KE]- Best-response 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 in the notes; Chapters 9,10,15 in KE]- Matching markets, market clearing prices.
- Exchange networks
- Auctions and the Vickery-Clark-Grove (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 the notes]- Voting, strategy-proofness
- Gibbard’s impossibility results
- Single-peaked preferences and the Median Voter theorem
- The House Allocation problem
- Two-sided 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 the notes]- 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 No-Trade Theorem
- Common Knowledge of rationality as a characterization of iterated removal of strictly dominated strategies
- The power of higher-order beliefs: Valuation “Bubbles”

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

**Additional Topics**- Networks in the brain
- Decentralized currencies: Bitcoin and beyond