Social Choice and Networks:
Fall 2010: CS 294 (063) / Econ 207 A / Math C223A / Stat C206A/
Office hours: After class, Cory 241
Instructor: Elchanan Mossel
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.
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.
Missing: Oct 14?
Kariv: Monotone Games in Networks.
Sequential Equilibrium in Monotone Games: A Theory-Based Analysis of Experimental Data (Choi, Gale & Kariv)
Network Architecture,Salience and Coordination (Choi, Gale, Kariv & Palfrey)
Oct 19 (5:30-7:00pm): Prof. Tom Griffiths
Optimal Predictions in Everyday Cognition (Griffiths & Tenenbaum)
Theoretical and empirical evidence for the impact of inductive biases on cultural evolution (Griffiths, Kalish & Lewandowsky)
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.
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.
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
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
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
(Note - the classes during the projects presentations will run until approximately 7pm)