Social Choice and Networks:

 

Fall 2010: CS 294 (063) / Econ 207 A / Math C223A / Stat C206A/


Time: TTh 5-6:30pm, Cory 241
Office hours: After class, Cory 241

Instructor: Elchanan Mossel

 

Syllabus:

 

The course will look at various models and theoretical results

relating to collective decision making starting from Condorcet's jury

theorem and reaching current research on social networks. Special

interest will be given to modern approaches for quantitative analysis

and to computational efficiency. The basic questions relate to the

aggregation power of groups, to the power of individuals in

determining the outcome of a decision, understanding disagreements,

gossip and marketing.

 

Prerequisites:

 

The course is aimed at graduate students in Statistics, EECS, Mathematics, Economics etc.

It assumes working knowledge of probability, discrete mathematics and computer science at a graduate level. In particular, the following will be assumed:

1. Probability: conditional expectations, martingales and multi-variate Gaussian variables.

2. Linear algebra including eigenvalues etc.

3. Understanding of algorithms and computational complexity analysis.

4. Basic graph theory.


 

Lectures - All Rights Reserved


Intro Lecture (Aug 26)


Aggregation of Binary Biased Signals (Aug 31, Sep 2)


Aggregation of General Biased Signals and Permutations (Sep 7)


Agreeing to disagree and other Bayesian martingale learning models (Sep 14, Sep 16)


Some non-martingle learning models (Sep 21, Sep 23)


Consensus models, bribe and marketing  (Sep 30)


Errors in binary voting  (Oct 5)


Arrow Theorem (Oct 7, Oct 14)


The GS Theorem (Oct 21, Oct 26)


Scribe Notes


Aggregation of Biased Binary Signals 1 (Aug 31)


Aggregation of Biased Binary Signals 2 (Sep 2)

Aggregation of general Biased Signals (Sep 7)

Martingale Learning Models (Sep 14, Sep 16)


Some Non Martingle Learning Models (Sep 21, 23)


Consensus models, bribe and marketing  (Sep 30)


Errors in Binary Voting (Oct 5)


Combinatorial Arrow Theorem (Oct 7)


Missing: Oct 14?


The GS Theorem (Oct 21)


Quantitative GS Theorem (Oct 26)


Fair and Envy Free Allocations (Nov 2)



Guest Lectures


Oct 12: Prof. Shachar Kariv: Monotone Games in Networks.
Reading:
Sequential Equilibrium in Monotone Games: A Theory-Based Analysis of Experimental Data (Choi, Gale & Kariv)
Network Architecture,Salience and Coordination (Choi, Gale, Kariv & Palfrey)
Talk: 

Monotone Games, Network Architecture, Salience and Coordination  (Oct 12)


Oct 19 (5:30-7:00pm): Prof. Tom Griffiths
Reading:
Optimal Predictions in Everyday Cognition (Griffiths & Tenenbaum)
Theoretical and empirical evidence for the impact of inductive biases on cultural evolution (Griffiths, Kalish & Lewandowsky)

Talk:
Bayesian Models of Cultural Evolution  (Oct 19)


Oct 28: Prof. Jure Leskovec: Meme-tracking and the Flow of Information in Networks
Abstract

Links to papers covered: paper1 paper2 paper3 paper4 paper5


Nov 4: Dr. Ariel Procaccia: The computational war on manipulation

Abstract: I will give an overview of a line of work that attempts to circumvent the Gibbard-Satterthwaite Theorem via computational complexity. I will describe some worst-case complexity results as well as an average-case critique of these results. 

Related papers: paper1 paper2 paper3 


Nov 23: Title: Modelling Social Contagion in Networks
Prof. Russell Lyons (Indiana University, visiting Microsoft Research)

Abstract: A series of recent highly touted papers by Christakis and Fowler
claim to have demonstrated the existence of transmission via social
networks of various personal characteristics, including obesity, smoking
cessation, happiness, and loneliness.  Those papers also assert that such
influence extends to three degrees of separation in social networks.
However, their statistical methodology is seriously flawed at many levels,
as we explain.


Nov 30: Potential Networks, Contagious Communities, and Understanding Social Network Structure
Dr. Grant Schonnebeck
Abstract


Students Presentations


Suggested book chapters:


1. D. Easley and J. Kleinberg - Networks Crowds and Markets:  chapters 15 (taken by Steve),18 (John) or 20 (Alex) .


2. M. Jackson - Social and Economic Networks: chapters 9 (taken by Are) or 10


Suggested papers:


1. C. Mathieu and W. Schudy: How to rank with a few errors
2. Bala and Goyal: Learning from Neighbors
3. L. Smith and P. Sorensen: Informational Herding and Optimal Experimentation
4. Berger, Borgs, Chayes & Saberi: Spread of viruses on the Internet
5. Kempe, Kleinberg & Tardos: Maximizing the Spread of Influence in a Social Network 
6. Mossel & Tamuz: Complete Characterization of the functions satisfying Arrow's theorem

7. Braverman, Etesami and Mossel: Mafia -

8. Kalai and Mossel: Sharp Thresholds for Monotone Non Boolean Functions and Social Choice Theory.


The presentations will be held in the following dates. In general  books chapters will be presented earlier and research projects later.


Nov 9:   Non Linear Invariance, Jackson (Chapter 9), Combinatorial Public Project Problem
Nov 16: Gaussian Partitions and Social Choice, Easley Kleinberg: chapters 15 & 20
Nov 18: Easley Kleinberg: 18, KKT: Influence Maximization , BBCS: Spread of viruses on the Internet,  Transitive and fair Pluralities and Majorities  
Nov 23: Guest lecture: Russell Lyons

Nov 30: Guest lecture: Grant Schonnebeck + Mafia
Dec 2:   Qauntitative GS


(Note - the classes during the projects presentations will run until approximately 7pm)