CMPS 290G Winter 2012

Time: TuTh 10-11: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 1-3pm (reserve a slot) or by appointment (email me).

Class Wiki.

The course is an introduction to reputation systems. Reputation systems are used to coordinate the interactions of people on-line:

• They provide incentives for users to collaborate, behave constructively, and provide quality contributions.
• They help separate great quality content, from low-quality 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 on-line analogous to the body of laws and norms that regulate the behavior of people in real-life. 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 open-class 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

Here are the news and updates for the class. Note that you can subscribe to the page, if you wish to receive email alerts.

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.
  • Brower (and Kakutani)
  • Banach (contractions)
  • Knaster-Tarski (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
  • Sock-puppet 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 (max-flow 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