Time: TuTh 1011:45
Location: Porter Acad 241. The class is also telecast using Google+ Hangouts to UCSC SV.
Instructor: Luca de Alfaro (luca@ucsc.edu)
Office hours: Tuesdays 13pm (reserve a slot) or by appointment (email me).
The course is an introduction to reputation systems. Reputation systems are used to coordinate the interactions of people online:
 They provide incentives for users to collaborate, behave constructively, and provide quality contributions.
 They help separate great quality content, from lowquality content or spam.
 They provide users with information on the quality of both content and other users, thus facilitating the trust that is necessary to establish many successful sites and marketplaces.
 They limit the damage from vandalism, spam, and fraud.
Essentially, reputation systems can be thought of as an online analogous to the body of laws and norms that regulate the behavior of people in reallife. It is the instructor's belief that most sites that interact with users need, or use, a reputation system of one form or another.
The course covers the mathematical, statistical, and social foundations of reputation systems. The course will be organized as a sequence of lectures, and possibly openclass discussions and paper presentations. There will be homeworks, which will consist of a mix of simple programming assignments to experiment with particular systems, homeworks based on data analysis and inference, and mathematical/analytical homeworks. The class grade will be determined from an attendance component, and from the homework grades; there will be no final exam.
News
Class Notes
Here are the class notes. Since the class notes include video recordings, for privacy reasons, they are accessible only by the students of this class. If you are a student, email me, and I will add you to the access list.
Syllabus
The following is a tentative syllabus. As the course will progress, this syllabus will be finalized and will reflect the actual course contents. Topics in square brakets are under consideration, but not certain yet to be included in the class.
 Lecture 1. Inference. How can we make guesses about facts, from observations?
 Bayesian inference
 Principle and methods
 Limitations: prior, independence
 Fixpoint theorems. Fixpoint theorems are used both as a foundation for game theory (Nash equilibrium), and to prove that various classes of algorithms over graphs converge.
 Banach (contractions)
 KnasterTarski (least, greatest fixpoints of monotone operators)
 Graph reputation systems / ranks (these are reputation systems based on graph computation):
 PageRank
 proof of stability
 connection with random walks
 [Bounds on rank according to graph shape]
 Logrank
 HITS
 Sockpuppet attacks, flow defenses
 Chronological reputation systems / ranks (these work chronologically)
 The “useful work” principle
 Robust ranking techniques
 Open problems: Democracy vs. Oligarchy, the “no hidden garbage” property.
 Consensus rankings
 Crowdsensus
 Rating systems (a la Yelp), Bayesian binomial distribution work.
 Social networks
 Analysis of friendship (friend suggest algorithms)
 Analysis of friendship (maxflow type algorithms for recommendation)
 Foundations of game theory
 Nash equilibria
 Dominating strategies
 Other notions of equilibria
 Mechanism design. Mechanism design studies how to set up games
 The revelation principle
 Revenue equivalence
 The VCG framework
 Auctions
 Ebay / timed auctions
 The failure of values (examples)
 Crowdsourcing a ranking
 Arrow’s impossibility theorem
 Glickman’s work
 Incentives for truthful rankings, and relations with horse betting
 Loss functions
Optional topics:
 Clustering
 Binomial distributions
Tutorials on:
 Machine learning
 Logistic
 Bayesian
 Tree classifiers
 NLP
 MapReduce
