CAS CS 591B2 - Fall 2020 - Networks and Markets: Theory and Applications
The concept of a network has outgrown the narrower engineering mindset of a collection of
interconnected machines to become more broadly relevant in a variety of applied settings which feature
connectedness. Biological networks, social networks, online advertising networks, and networks involving
hyperlinks like the WWW, are all examples of domains in which the theory and practice of networking
science has now being applied. In parallel with this trend is the rise of online markets as a mediation
point for commercial activity. Beginning with the advent of Internet platforms like eBay that employ online
auctions, are many fascinating new markets: pay-per-click advertising markets, prediction markets, and
two-sided platforms such as Uber and Airbnb. All of these application domains draw deeply on established
methodologies that are highly familiar to computer scientists, notably graph theory and algorithms.
However, they also build on theoretical foundations that is often unfamiliar territory to computer scientists,
such as auction design, mechanism design, and the theory of matching markets. Finally, many important new
technologies incorporate a mix of networks and markets, including information networks and recommender systems.
In this class, we will build on the highly successful undergraduate text of Easley and Kleinberg to learn about
the underlying theory of networks and markets, understand how modern-day digital applications connect to these
foundations, and conduct our own independent projects to explore an aspect of a digital market more deeply.
In this class, we will consider networks and markets from a broad and inter-disciplinary perspective,
drawing primarily from insights from the Computer Science, Economics, and Marketing communities.
This course is designed for students who are potentially interested in either pursuing a career in or
conducting research related to online networked platforms. Please note that this course is not about
entrepreneurship per se, but does provide some useful background for prospective entrepreneurs.
The capstone project of the course will be a research effort, conducted by teams of two or three,
in which students conduct a quantitative
measurement-driven analysis of a computational aspect of an e-commerce firm or of consumer
behavior with respect to an e-commerce marketplace.
This course is designed for declared CS majors who are fulfilling 400-level electives,
as well as Masters students and entering Ph.D. students. CS 112, CS 131, and some knowledge of probability and
statistics is required. CS 330 is suggested as a co-requisite.
While students' backgrounds will vary, it is expected that students are nearing completion
of an undergraduate CS major or are beginning their graduate studies. Seniors who are not CS majors should
seek the instructor's permission to enroll.
Lectures: Tues/Thurs 2:00-3:15, FRC 122, and live-streamed on Zoom.
The Zoom link is available to registered students on our
The COVID capacity of our classroom is 14 students, just big enough to accommodate all of the students who
elected the "In Person" option on the BU Student Link, as of 9/2. Provided you did that, and are in compliance
with daily BU attestations to be allowed on campus (to enter the FitRec building, you will need to show
your attestation), you are welcome to attend.
I expect students to be in class, to come on time, and to be prepared to actively engage in class discussion.
I will be eliciting responses from all students to hear their opinions.
As an elective, interactive seminar, this class will not be a great fit for asynchronous learning.
Lecture portions will be recorded and available to students on Piazza. Class presentations and
discussions will be live-streamed but will generally not be recorded.
Prof. John W. Byers
Email: byers @ cs . bu . edu [preferred]
Office Hours (Fall 2020):
LfA mode: Tues/Thurs 3:15 - 4, inside our FitRec classroom.
Online: Please email me to set up an appointment.
For technical questions beyond what Piazza can answer (see below), or when you need a consultation.
The best way to reach me is via Piazza or on email.
Academic: John is Professor of Computer Science and Associate Dean of the Faculty at
Boston University. His academic research interests are broadly focused on algorithmic and economic
aspects of e-commerce, networking, and large-scale data management. His work strikes a balance between
theoretical foundations and rigorous data-driven experimentation.
Entrepreneurial: John is founding Chief Scientist and Board Member at Cogo Labs, a start-up based in Cambridge, MA, where
he has had an executive role since the company's founding in 2005. Cogo leverages a unique proprietary
technology platform for algorithmic marketing, data mining, and quantitative business analytics to guide incubated
portfolio companies from inception to profitability and beyond.
Textbook and Readings
Primary Text: "Networks, Crowds, and Markets: Reasoning About a Highly Connected World",
by Easley and Kleinberg. ISBN: 9780521195331
A/B testing and running controlled experiments.
"Controlled experiments on the web: survey and practical guide",
R. Kohavi, R. Longbotham, D. Sommerfield, R. Henne, DMKD (18) 140-181, 2009.
J. Feigenbaum, D. Parkes, and D. Pennock,
in E-Commerce", CACM, January 2009, 52(1), pp. 70-74.
- Recommender systems: overview of objectives and basic methods.
The 2005 survey
by Adomavicius and Tuzhilin, IEEE TKDE 17(6), June 2005, still serves as a useful
- The Netflix Prize. Several good summaries of the Netflix competition are out there,
including from Smyth (UCI)
Technical foundation: "Modeling
Relationships at Multiple Scales to Improve Accuracy of Large Recommender Systems",
by R. Bell, Y. Koren, and C. Volinsky.
We will be using Piazza for all discussions outside of class. We will also use Piazza to post announcements,
homework assignments, etc.
Rather than emailing questions about the class to me, I encourage you to post your questions on Piazza, where
you are also welcome to answer questions posted by others.
Our class page is located at:
Registered students have been signed up automatically, but new students should sign themselves up.
Course Requirements and Grading:
There will be three components of the grade in the class:
For class, we will be drawing primarily from the Easley-Kleinberg textbook, but as this is an
introductory text, we will also be going deeper with additional lecture material and some outside readings
tailored for advanced CS undergraduates and beginning graduate students.
- Summarization and in-class discussion of the readings in the course (10%).
- Homework assignments (25%).
- In-class quizzes/exams (25%).
- Comprehensive, semester-long research project (40%).
We will have periodic homework assignments, in-class quizzes comprising short answer problems, and perhaps a few
longer homework problems.
Project: The capstone project for the course will be a semester-long research project, culminating in a writeup and a
presentation to the class, which will take the form of a poster and/or a demo at a class-wide poster+demo session, held
online in LfA style as best we can manage.
The topic of the research project will be for students to conduct a study of a computational aspect of an e-commerce firm
or of consumer behavior with respect to an e-commerce marketplace. Students may work in teams of two or three,
with the expected output of the teams to be commensurately larger. Suggested project topics and project deadlines will be
announced after the first few weeks of the course, with regular milestones throughout the semester. I will expect
students in this class to take the project very
seriously and there will be regular interaction with the instructor outside of class to work on the projects ---
ideally, several of the best projects in the class will eventually continue beyond the class, in a direction towards
publication or commercialization.
Research studies may take a variety of forms, depending on students' interests and aptitudes. The most typical
project will be to conduct and write up a research study that is a quantitative, i.e., data-driven, analysis of a
computational aspect of an e-commerce firm or of consumer behavior with respect to a networked marketplace. We
will discuss several examples of these a few weeks into the semester. An ambitious, but reasonable goal for CS
graduate students, would be to initiate a line of work with the potential to further develop as a publishable paper
in the experimental track of the ACM Symposium on Economics and Computation,
or to develop into a Masters thesis or dissertation chapter. Work will be graded based both on the effort
demonstrated in the pilot study and on the promise of the proposed future work.
A second option is to design and write up an app, or other software system, that addresses a challenging direction
in the general space of networked platforms. Work will again be graded based both on the demonstrated output and
in the promise of the proposed future work, using grading at Hackathons as a barometer.
A third (and perhaps the most difficult) option is to develop a business plan to tackle a problem in this space,
formatted both as a writeup and as a presentation pitch deck for seed funding in the $50K range (which will also be
presented as a poster at the poster session). Work will be graded based on the quality of the pitch from the
perspective of an investor, using competitiveness at a student business plan competition as a barometer.
If a team has an alternative project idea in mind that they believe is in scope, they should feel free to pitch it
as a potential project direction at the appropriate early milestone in the class.
- Course overview. Technical backdrop, graphs [EK, Chapters 1 & 2]
- Strong and weak ties [EK, Chapter 3]
- Homophily and network structure [EK, Chapter 4 and 5]
- Game theory and strategic behavior [Ek, Chapter 6]
- Auction design and auction theory, Ebay [EK, Chapter 9]
- Methods and practice of large-scale data analysis [outside readings]
- Matching markets and applications to ad auctions [EK, Chapter 10, 15]
- Network equilibria and bargaining [EK, Chapter 11]
- Web structure, page rank [EK, Chapter 13-14]
- Recommender systems and personalization. Netflix challenge. [outside readings]
- Information cascades, network effects and power laws [EK, Chapter 16-18]
- Diffusion, epidemics and "small-worlds" [EK, Chapter 19-21]
- Markets with information [Ek, Chapter 22]
- Peer-to-peer markets, e.g., Uber, Airbnb [outside readings]
Course Schedule (as it evolves). Handouts, lecture slides, and lecture recordings are available on Piazza.
- [Thurs, 9/3]: Class syllabus and overview/review of networks.
Reminder of graph definitions, data structures and basic graph
algorithms. Reading EK: Chapter 1.
- [Tues, 9/8]: Class introductions: everyone was asked to introduce themselves
and give an example of an interesting website they have visited recently that could
be a good candidate for study (not recorded). Wrap up graph algorithms review.
Reading EK: Chapter 2 (review).
- [Thurs, 9/10]: Graph properties and graph structure. Strong and weak ties, triadic closure,
centrality, Girvan-Newman decomposition algorithm and implementation.
Reading EK: Chapter 3.
- [Tues, 9/15]: Concepts and applications of node importance and more notions of
centrality. Various measures: betweenness, closeness, eigenvector. PageRank.
- [Thurs, 9/17]: PageRank example and walkthrough. Structural holes and network constraint measure.
More on edge attributes and link formation: weights, signs, tie strength. EK Chapter 4.
- [Tues, 9/22]: Homophily and structural balance. Group formation and community detection.
Modularity definition and use as a stopping condition in clustering algorithms. EK Chapter 5.
- [Thurs, 9/24]: Intro to game theory: players, strategies, payoff matrix. Prisoner's dilemma and
many other examples. Dominant strategies, best response, Nash equilibria.
Reading: EK Chapter 6.
- [Tues, 9/29]: Computing Nash equilibria: brute-force algorithms and NP-hardness. Mixed strategies, various notions of optimality. Applications to evolutionary biology. Reading: EK Chapter 7.
- [Thurs, 10/1]: Short class due to conflicting conference talk. Discussion of the class project.
- [Tues, 10/6]: Congestion in computer and traffic networks, modeled as a game. Braess's paradox.
Introductory discussion of auctions in historical contexts and in e-commerce. Basic designs and modeling
Reading: EK Chapter 8.
- [Thurs, 10/8]: Auctions: sellers, buyers, auctioneers, and goals of these agents.
Concept of mechanism design. Reasoning about buyer behavior in a single-item auction
with unknown valuations. Open cry auctions: English and Dutch auctions.
Reading: EK Chapter 9.
- [Tues, 10/13]: BU was on a Monday schedule due to Columbus Day. No class.
- [Thurs, 10/15]: Day 1 of project pitch presentations. No class recording but slides are in our shared Google drive, see Piazza for link.
- [Tues, 10/20]: Day 2 of project pitch presentations.
Sealed bid auctions: first and second price. Bidder behavior and expectations.
- [Thurs, 10/22]: Auctions wrap up. Equilibrium strategies in various auction formats.
Truthfulness in second-price auctions, optimal shading of bids in first-price auctions with uniform valuations.
- [Tues, 10/27]: Matching markets, part I. Review of bipartite graphs, perfect matchings, and constricted sets.
Adding prices and valuations. Rules of the game, notion of preferred seller and market-clearing prices (MCPs).
Examples and algorithm to compute MCPs.
Reading: EK Chapter 10.
- [Thurs 10/29]: Matching markets, part II. Proofs of correctness, termination and running time for
MCP algorithm. Discussion of social optimality. Connections to online advertising and markets for ad slots.
Reading: EK Chapter 15.
- [Tues 11/3]: Ad auctions as a matching market. Reasoning about generalizing second-price auctions,
potential pitfalls. VCG solution concept.
EK Chapter 15.
- [Thurs 11/5]: Defining the VCG principle, proof that truthfulness is dominant strategy with VCG
pricing, outcomes and equilibria.
- [Tues 11/10]: Wrapup of ad auctions: VCG vs. GSP-based ad auctions, quality score considerations and
GSP in the real world. Brief intro to recommender systems.
- [Thurs 11/12]: Class time was used for project discussions. No lecture.
Next topic: Recommender systems: overview of objectives and basic methods. Emphasis on
collaborative filtering. The 2005
survey by Adomavicius and Tuzhilin, IEEE TKDE 17(6), June 2005, still serves as a useful
basic reference. (You only need to read the first five pages).
- [Tues 11/17]: Recommender systems and Netflix prize competition.
- [Thurs 11/19]: In-class midterm, fully remote, conducted on Zoom. Covers material up through and including ad auctions. Open notes. Alternative timeslot for those in inconvenient
timezones: Mon 9:45 - 11AM.