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
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)
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?
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.
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)