Listed as COMS 6995-1, Fall 2013, Computer Science, Columbia University
Instructors: Kevin Yang (TA), A. Chaintreau (instructor)
Hamilton 602, Wednesday 6:10-8pm

This website provides information and teaching material for a graduate research seminar on economic dynamics in social networks. The course is primarily targeted at students with a strong interest in theoretical analysis of social networks, and related research areas.

On this website, you will be able to:

Find (on this page) a brief statement about the contents and objective of the course. More information (including all teaching materials) is available on the detailed content section of this site.

Find (below) answers to questions about logistics of the class; learn about Rules enforced.

Find a list of references pointing to classes with overlapping contents.

Connect with the mobile-social-lab blog which contains links on relevant recent articles.

Objective of this course:

What is the goal of this class?

This class aims at making you a full-research-citizen on economic and theoretical aspects of social networks and their applications. At the end of this class, if you are successful, you will have earn:

a familiarity with important concepts in the area

a practice of fundamental proof techniques to analyze economic properties of social networks

an ability to quickly grasp top-notch theory works as published in ACM EC, ACM WWW, economic journal, etc.

The main benefit is for your research. This class teaches you a foundation and help you focus on recent topics that are hot as they are the most likely to be fertile ground for future research. It's a wonderful ways to beef up your experience and knowledge if you have a research project on a related topic. It's not, however, an introductory class that is made to be fully accessible to all. The benefits are long term (and to some degree uncertain, since the works we see are new), the
effort is significant, so in a benefit/ratio tradeoff if you just feel like you want

Who should take this class?

Graduate students and mature undergraduate students who have already developed an interest in this domain for future research. All are welcome, with a prerequisite of a strong mathematical training and a taste for theoretical proofs.

What is this class about?

The scope is, roughly speaking, any topics in which networks connecting individuals, and their topological properties, affects outcome of process related to collective decisions, markets and prices, labors and revenues of online applications. This scope is obviously way too large to be covered in class, but you will learn the most important concepts and proofs in this domain. Refer to a short overview below and the Detailed Content page to see more.

What is related but NOT covered in this class?

There are three families of topics that are deeply related to this issue, but are offered elsewhere and constitute entire class topic on their own:

Theory of auctions and mechanism designs

Bayesian learning and Prediction markets

Economics of networking infrastructure (communication and transportation networks)

We will NOT assume that these topics are know (prior knowledge about them is a plus) and occasionally will connect to the class when relevant, but if you need to become an expert in one of them take another class that focuses on these.

3 Reasons NOT to take this class?

If you do not mean the prerequisite requirement, especially in probability theory and linear algebra. This class is a theoretical class with proofs and you will be judge in your ability to come up with variants and apply theoretical arguments, so if this is not of your interest and part of your skillset, you should probably take it later or consider alternative.

If you are mostly looking for ideas on your next start-up. You'll get some ideas, that's true, but you will required to do a lot of extra work on the mathematical side that will likely not end up in your project. Theoretical depth is a long term investment, that sometimes require to temporally sacrifice some practical relevance. Hence, this class is not a good return on effort for that cause.

If you look for a mature class with extensive accompanying materials or/and you currently work towards maximizing your GPA. The class is by nature close to research, it will evolve to accompany what's being and will probably never mature. There is no textbook, for the same reason. The terminology in the literature is atrociously confusing as various research communities are calling the same effect by different names, and related work have been published in Economic theory, Econometrics and Marketing journals, in CS theory conference, in CS domain specific conferences as well.
If you have a multi-year research project in mind, it makes sense to invest time in getting all these things right, and see the latest works. Otherwise, it's just the wrong investment for your time.

Contents and Organization:

The course is organized in 3 parts, to cover important areas subject of intense research investigation as we speak

The first part "A - Opinion and Influence" is focusing on understanding natural process of interaction between agents and how to derive prediction on their economic consequence. It answers the following questions:

Under which conditions can a collective process come to agree in a decision when nodes influence each others? Under which conditions is this agreement good in an objective way?

What are other phenomena affecting how we form opinion, and how do they exhibit lack of consensus, polarization, and a propensity for manipulation? Can they be reproduced and analyzed mathematically?

How to model and leverage process of adoption in social networks to one's benefit?

The second part "B - Graphical Economies" centers on the effect of social network constraints on pricing and exchange economies. Related Questions of interest are:

How does the outcome of a market, pricing or bargaining process depends on the network defining opportunities of exchanges between individuals?

What are models of goods and consumptions in which players' choice affect each other differently in the network?

How does dynamics of groups in collective deals, crowdfunding affect revenue?

The third part "C - Leveraging your users" is an attempt to cover important recent trends on understanding theoretically the economies of the web.

How to make sense of a huge number of signals from heterogeneous users?

How to price labor in online labor marketplace and reward productive participation in large applications?

How to value and leverage users' personal information?

For more information about the content of the class, please visit the Detailed Content page.

Logistics:

Where and when are the lectures / office hours ?

Time: Wednesday 6:10-8:00pm
Room: Hamilton 602
Office-hours (at various time in the week, so you have multiple chance to come):
Kevin Yang (Monday: 2:30-3:15pm and Friday 3-3:45pm, CEPSR 6LW5)
A. Chaintreau (Thursday 8:00-9:00am, CEPSR 610, with extension made on request to 9:30am)

Who is in charge?

Kevin Yang as a Teaching Assistant, Augustin Chaintreau as instructor.
Please post any question or inquiry on our Online forum (unless it deals with a personal exception).

What do I need to know to take the class?

A prerequisite to this course is a taste and formal training in the various mathematical tools involved in this area.
The familiarity with the following mathematical notions is required, beyond calculus and easy convex optimization. Exercises will require you to manipulate those concepts and theorems in creative ways to train your mathematical skill in proving new results:

Probability theory: Knowledge of Markov Models including continuous time and Stochastic Process is required. In particular, Lyapunov functions, Foster's theorem and the proof of Martingale Convergence is assumed.
In other words, the contents of the following book will be assumed known
P. Bremaud, Markov chains: Gibbs fields, Monte Carlo simulation, and queues (2010) Springer.
with the exception of Chapter 6-7 and 9.

Linear Algebra: Familiarity with matrix, eigenvalues, eigenvectors, and their use to characterize linear transformation will be assume. This corresponds to the content of the following book
G. Strang Introduction to Linear Algebra, Wellesley Cambridge Press (2009)
with the exception of Chapter 9 and 10

Graph theory: Notions related to graph definitions, connectivity, flows, matching and coloring, are assumed known, as well as a general proficiency to understand the topological properties of subset of vertices. This corresponds to Chapter 1,2,3,5,6 in
R. Diestel, Graph Theory (2010), Springer.

Game theory: Elementary concepts of Nash Equilibrium, mixed strategy, correlated equilibrium are assumed known. This corresponds to Chapter 1,2,3 in
M. Osborne, A. Rubinstein, A Course in Game Theory, MIT Press (1994)

Economics: The class assumes no prior knowledge of economics theory.

How will I be graded?

The evaluation will be decided depending on the final enrollment, this is a graduate seminar, and it could involve

about 3 problem sets containing mathematical exercices

1 or 2 blog posts to write during the term

a mid-term exam

a final exam

presentation of articles in class

projects (individuals or group)

Exact percentage will be decided and announced on the third week (depending on the size and interest of the class)

Should I buy a textbook? Are there mandatory readings?

There is no mandatory books to buy for the class; unfortunately the topics covered in this course are not described in a textbook at the graduate level.

The course is more or less self-contained, references are given to allow you to review the material before or after class (all in the Detailed Content page)

You will find references, including links to similar classes, in our

How do I hand in late homework?

Please arrange with a TA or Prof. Chaintreau to hand in the hard copy of your homework. Programming portions of the homework should be turned in online, as normally done.

## Welcome to the "Social Networks Economics" class!

Listed as COMS 6995-1, Fall 2013, Computer Science, Columbia University

Instructors: Kevin Yang (TA), A. Chaintreau (instructor)

Hamilton 602, Wednesday 6:10-8pm

This website provides information and teaching material for a graduate research seminar on economic dynamics in social networks. The course is primarily targeted at students with a strong interest in theoretical analysis of social networks, and related research areas.

On this website, you will be able to:

## Objective of this course:

What is the goal of this class?This class aims at making you a full-research-citizen on economic and theoretical aspects of social networks and their applications. At the end of this class, if you are successful, you will have earn:

The main benefit is for your research. This class teaches you a foundation and help you focus on recent topics that are hot as they are the most likely to be fertile ground for future research. It's a wonderful ways to beef up your experience and knowledge if you have a research project on a related topic. It's not, however, an introductory class that is made to be fully accessible to all. The benefits are long term (and to some degree uncertain, since the works we see are new), the

effort is significant, so in a benefit/ratio tradeoff if you just feel like you want

Who should take this class?Graduate students and mature undergraduate students who have already developed an interest in this domain for future research. All are welcome, with a prerequisite of a strong mathematical training and a taste for theoretical proofs.

What is this class about?The scope is, roughly speaking, any topics in which networks connecting individuals, and their topological properties, affects outcome of process related to collective decisions, markets and prices, labors and revenues of online applications. This scope is obviously way too large to be covered in class, but you will learn the most important concepts and proofs in this domain. Refer to a short overview below and the Detailed Content page to see more.

What is related but NOT covered in this class?There are three families of topics that are deeply related to this issue, but are offered elsewhere and constitute entire class topic on their own:

- Theory of auctions and mechanism designs
- Bayesian learning and Prediction markets
- Economics of networking infrastructure (communication and transportation networks)

We will NOT assume that these topics are know (prior knowledge about them is a plus) and occasionally will connect to the class when relevant, but if you need to become an expert in one of them take another class that focuses on these.3 Reasons NOT to take this class?If you do not mean the prerequisite requirement, especially in probability theory and linear algebra.This class is a theoretical class with proofs and you will be judge in your ability to come up with variants and apply theoretical arguments, so if this is not of your interest and part of your skillset, you should probably take it later or consider alternative.If you are mostly looking for ideas on your next start-up.You'll get some ideas, that's true, but you will required to do a lot of extra work on the mathematical side that will likely not end up in your project. Theoretical depth is a long term investment, that sometimes require to temporally sacrifice some practical relevance. Hence, this class is not a good return on effort for that cause.If you look for a mature class with extensive accompanying materials or/and you currently work towards maximizing your GPA.The class is by nature close to research, it will evolve to accompany what's being and will probably never mature. There is no textbook, for the same reason. The terminology in the literature is atrociously confusing as various research communities are calling the same effect by different names, and related work have been published in Economic theory, Econometrics and Marketing journals, in CS theory conference, in CS domain specific conferences as well.If you have a multi-year research project in mind, it makes sense to invest time in getting all these things right, and see the latest works. Otherwise, it's just the wrong investment for your time.

## Contents and Organization:

The course is organized in 3 parts, to cover important areas subject of intense research investigation as we speak

The first part "A - Opinion and Influence" is focusing on understanding natural process of interaction between agents and how to derive prediction on their economic consequence. It answers the following questions:

The second part "B - Graphical Economies" centers on the effect of social network constraints on pricing and exchange economies. Related Questions of interest are:

The third part "C - Leveraging your users" is an attempt to cover important recent trends on understanding theoretically the economies of the web.

For more information about the content of the class, please visit the Detailed Content page.

## Logistics:

## Where and when are the lectures / office hours ?

Time: Wednesday 6:10-8:00pmRoom: Hamilton 602

Office-hours (at various time in the week, so you have multiple chance to come):

Kevin Yang (Monday: 2:30-3:15pm and Friday 3-3:45pm, CEPSR 6LW5)

A. Chaintreau (Thursday 8:00-9:00am, CEPSR 610, with extension made on request to 9:30am)

## Who is in charge?

Kevin Yang as a Teaching Assistant, Augustin Chaintreau as instructor.Please post any question or inquiry on our Online forum (unless it deals with a personal exception).

## What do I need to know to take the class?

A prerequisite to this course is a taste and formal training in the various mathematical tools involved in this area.The familiarity with the following mathematical notions is required, beyond calculus and easy convex optimization. Exercises will require you to manipulate those concepts and theorems in creative ways to train your mathematical skill in proving new results:

Probability theory: Knowledge of Markov Models including continuous time and Stochastic Process is required. In particular, Lyapunov functions, Foster's theorem and the proof of Martingale Convergence is assumed.In other words, the contents of the following book will be assumed known

P. Bremaud,

Markov chains: Gibbs fields, Monte Carlo simulation, and queues(2010) Springer.with the exception of Chapter 6-7 and 9.

Linear Algebra: Familiarity with matrix, eigenvalues, eigenvectors, and their use to characterize linear transformation will be assume. This corresponds to the content of the following bookG. Strang

Introduction to Linear Algebra,Wellesley Cambridge Press (2009)with the exception of Chapter 9 and 10

Graph theory: Notions related to graph definitions, connectivity, flows, matching and coloring, are assumed known, as well as a general proficiency to understand the topological properties of subset of vertices. This corresponds to Chapter 1,2,3,5,6 inR. Diestel,

Graph Theory(2010), Springer.Game theory: Elementary concepts of Nash Equilibrium, mixed strategy, correlated equilibrium are assumed known. This corresponds to Chapter 1,2,3 inM. Osborne, A. Rubinstein,

A Course in Game Theory, MIT Press (1994)Economics:The class assumes no prior knowledge of economics theory.## How will I be graded?

The evaluation will be decided depending on the final enrollment, this is a graduate seminar, and it could involve- about 3 problem sets containing mathematical exercices
- 1 or 2 blog posts to write during the term
- a mid-term exam
- a final exam
- presentation of articles in class
- projects (individuals or group)

Exact percentage will be decided and announced on the third week (depending on the size and interest of the class)## Should I buy a textbook? Are there mandatory readings?

## How do I hand in late homework?

Please arrange with a TA or Prof. Chaintreau to hand in the hard copy of your homework. Programming portions of the homework should be turned in online, as normally done.