**PENN CIS 677, FALL 2009: SOCIAL NETWORKS AND ALGORITHMIC GAME THEORY
**

Prof. Michael Kearns

mkearns@cis.upenn.edu,

Tuesdays
12-3 PM (First meeting Tue Sep 15)

307 Levine Hall

URL for this page:
www.cis.upenn.edu/~mkearns/teaching/NetworksAGT

**SEMINAR DESCRIPTION**

This seminar course will be an advanced mathematical study of the modeling of social and other large-scale networks, and the strategic issues they give rise to. Broadly speaking, in the seminar we will:

To a first approximation, the seminar can be viewed as a graduate-level treatment of many the core topics covered in the Penn undergraduate course Networked Life.

The course will draw heavily on two (required) texts:

These books are available at the Penn Bookstore. Alternatively, both can be purchased through Amazon or other online sources.

The current plan is to work our way sequentially through the Jackson book more or less in its entirety, supplementing it in many places with the more mathematical source papers discussed there. We will then move on to selected topics covered in the Nisan et al. volume (again with supplemental readings), focusing mainly on the chapters in which networks play an important role.

A partial list of topics to be covered includes:

**COURSE FORMAT, REQUIREMENTS, AND PREREQUISITES **

This course will be run as a highly participatory seminar. While I will sometimes lead the discussions and sometimes give more formal lectures on the material, it is expected that class participants will often be responsible for leading the presentations and discussion. I tend to guide such presentations in "Oprah/O'Reilly" fashion.

The course will meet once a week on Tuesdays from 12 to 3. Lunch will be served.

While there are no formal prerequisites, "mathematical maturity" will be expected. Background in at least some of the following topics will be helpful: graph theory, statistics and probability theory, game theory and microeconomics, design and analysis of algorithms. If you have no exposure to any of these topics, and don't otherwise have a strong math background, you will find portions of the course difficult to follow. We will often examine formal proofs in some detail.

Auditors and occasional participants are welcome, as are qualified undergraduates.

The course requirements for registered students are active in-class participation, leading one week's presentation and discussion, and occasional problem sets.

**DETAILED MEETING/TOPIC SCHEDULE
**

READING: Jackson Chapters 1-3.

RELATED LINKS: NetLogo Erdos-Renyi and preferential attachment demos.

Tue Sep 22

Poisson (Erdos-Renyi) random networks: degree distributions, connectivity, diameter, component sizes,
threshold phenomena.

READING: Jackson Chapter 4, and the following paper:

We will at least study the main statement of the Friedgut-Kalai paper, but at most sketch the high-level tools and argument, so don't sweat the math if it's beyond your background. However, for you aficionados/gluttons out there, here is a link to the awesome course page of Ryan O'Donnell at CMU on the unbelievable variety of applications of the influence of functions.

Tue Sep 29

More stochastic network formation: Erods-Renyi continued, preferential attachment,
small worlds, configuration model, and others; structural
properties entailed (and not entailed) by each model.

READING: Jackson Chapter 5.

**Problem Set 1 (due as hardcopy in our Oct 27 meeting --- NOTE CHANGE OF DATE AND ADDITION
OF PROBLEMS 4.5 and 6.11):**
Jackson problems 1.2, 1.3, 1.4, 4.5, 4.7, 5.1, 6.1, 6.5, 6.11.
Also, prove the
Erdos-Gallai theorem,
and then use it to prove that most sequences of integers in 0,...,n-1 whose sum is even are
in fact degree sequences of undirected graphs over n vertices.
Collaboration policy:
It is fine if you discuss the problem set with others, but I ask that everyone submit their own separate
write-up, and that you acknowledge your collaborators by name on your write-up.
See Oct 27 entry below for problem presentation volunteers.

Tue Oct 6

Still more stochastic network formation: clustering, Watts-Strogatz, and Kleinberg's model.
Discussion of Problem Set 1.

READING: Jackson Chapter 5. We will also be discussing the following papers:

Tue Oct 13

Strategic network formation models.

READING: Jackson Chapter 6. We will also discuss the following paper:

Tue Oct 20

**NO CLASS THIS WEEK.**

Tue Oct 27

Strategic network formation, continued;
class presentation of Problem Set 1 solutions.
Problem presentation volunteers:
1.2 (Ryan); 1.3 (Rene); 1.4 (Jenny); 4.5 (Varun); 4.7 (Sudeepa); 5.1 (Wendy); 6.1 (Andres);
6.5 (Anand); 6.11 (Jun); Erdos-Gallai problem (Michael Z.)

READING: We will discuss material in the following paper and slides:

Tue Nov 3

Continued class presentation of Problem Set 1 solutions.

Tue Nov 10

Diffusion in networks;
graphical games and networked markets.

READING: Jackson Chapter 7 (diffusion), Chapter 10 (networked markets); AGT book Chapter 7.

Diffusion demos:

In the remaining 4 meetings (Nov 17, Nov 24, Dec 1, Dec 8), I would like registered students to form groups to present the topics listed below; I can be flexible about which topics are presented on which dates, but obviously not everyone can go last. I would guesstimate that each topic should take about an hour of meeting time, including discussion. I will also still be jumping in with various topics as well.

Tue Nov 17

Graphical games continued; networked markets.

READING: AGT book Chapter 7 (graphical games); Jackson Chapter 10 (networked markets).

Tue Nov 24

Class presentations:

Routing Games (AGT book Chapter 18 and supplementary material);
Presenters:
Kook Jin Ahn,
Daniel Wagner

Incentives and Information Security (AGT book Chapter 25 and supplementary material);
Presenters: Adam Aviv,
Sushmita Gupta,
Vilhelm Sjoberg

Learning in Networks (Jackson Chapter 8 and supplementary material);
Presenters:
Arastoo Fazeli,
Pooya Molavi, and Ceyhun Eksin

Tue Dec 1

Class presentations:

Learning in Networks, continued (Jackson Chapter 8 and supplementary material);
Presenters:
Arastoo Fazeli,
Pooya Molavi, and Ceyhun Eksin

Distributed Algorithmic Mechanism Design (AGT book Chapter 14 and supplementary material);
Presenters: Kareem Amin, David Weiss

Tue Dec 8

Our final meeting! Class presentations:

Incentives and Pricing in Communications Networks (AGT book Chapter 22 and supplementary material);
Presenters:
Changbin Liu,
Qi Zhang,
and
Zhiyi Huang.

Incentives in Peer-to-Peer Systems (AGT book Chapter 23 and supplementary material);
Presenters:
Weiyu Zhang
and
Oleg Naroditsky

Local Algorithms for
Finding Interesting Individuals in Large Networks;
Presenter:
Mickey Brautbar
[paper]