CPSC455/555: Economics and Computation

Announcements

March 29, 2006: A list of key ideas for the second exam has been posted.

March 28, 2006: Read A Game-Theoretic Framework for Analyzing Trust-Inference Protocols, by R. Morselli, J. Katz, and B. Bhattacharjee.
The list of papers that will be covered in the second exam has been posted.

March 21, 2006: Read The Social Cost of Cheap Pseudonyms by E. Friedman and P. Resnick.
The second exam will be held in class on April 4, 2006.

February 28, 2006: Please read the following papers, which were covered in class today:

1. Modeling and Performance Analysis of BitTorrent-Like Peer-to-Peer Networks by D. Qiu and R. Srikant
2. Incentives in BitTorrent Induce Free Riding by S. Jun and M. Ahamad
3. Faithfulness in Internet Algorithms by J. Shneidman, D. Parkes and L. Massoulié

February 21, 2006: Read the following papers:

1. Incentives Build Robustness in BitTorrent by Bram Cohen
2. Regulating Technical Design by Pam Samuelson
3. Did MGM Really Win the Grokster Case by Pam Samuelson
4. Brief Amici Curiae by a group of computer science researchers (available on this page)

February 13, 2006: There is now a proposed presentation schedule. Presentations will last half of the class period each, so there are two scheduled per day. Please look over it and confirm your scheduled day by email with Aaron, the TA.

February 7, 2006: A list of key ideas for the first exam has been posted. A list of types of questions that may appear on the exam is also available.

February 1, 2006: The first of two in-class exams will be given on February 16, 2006. It will cover the interdomain-routing material covered in class January 11 - February 14. Details can be found here. In particular, note that you should read the paper Subjective-Cost Policy Routing by Feigenbaum, Karger, Mirrokni, and Sami, if you have not already done so.

The third assignment is to read Distributed Implementation of Vickrey-Clarke-Cloves Mechanisms by D. Parkes and J. Schneidman and Incentive-Compatible Interdomain Routing by J. Feigenbaum, V. Ramachandran, and M. Schapira.

January 26, 2006: A new final project topic, "Internet Service Market Structure", has been added. If you have chosen a topic for your oral presentation, please send it to the TA by Tuesday, 1/31/06. If none of the suggested topics appeals to you, please set up a meeting with Professor Feigenbaum to discuss alternatives.

January 24, 2006: The topics covered today appear in the paper Mechanism Design for Policy Routing by Feigenbaum, Sami and Shenker. The lecture slides are also available.

January 19, 2006: Students taking the course for credit will be required to give a Powerpoint presentation at the end of the semester. More details and suggested topics can be found here.

January 12, 2006: The second homework assignment is to read the paper A BGP-based Mechanism for Lowest-Cost Routing by Feigenbaum, Papadimitriou, Sami, and Shenker.

January 10, 2006: The first homework assignment is to read the paper Algorithmic Mechanism Design by Nisan and Ronen.

Course information

Instructor:	Joan Feigenbaum
Office:	AKW 512
Telephone:	203-432-6432
Office hours:	On Wednesday, by appointment

Note: Professor Feigenbaum suffers from Repetitive Strain Injury and cannot handle large amounts of email. Do NOT send her email about CPSC455/555; instead, please contact her by phone, through the TA, or through her assistant Judi Paige (Tel: 203-436-1267, email: Judi.Paige@yale.edu).

TA:	Aaron Johnson
Office:	AKW 406
Telephone:	651-398-3103
E-mail:	ajohnson@cs.yale.edu
Office hours:	MW 3:30-5 p.m. or by appointment

Course description

This course was given previously in Spring 2003 and Spring 2002.

Note on the prerequisite: It really is essential that students have a firm grounding in the basics of theoretical computer science before enrolling in CPSC455/555. If you are unsure about whether you have the necessary background, you should read Algorithmic Mechanism Design by Nisan and Ronen and Distributed Algorithmic Mechanism Design: Recent Results and Future Directions by Feigenbaum and Shenker. If you have trouble understanding either of these, then you should not enroll in CPSC455/555.

Homework

1. Read the paper Algorithmic Mechanism Design by Nisan and Ronen.
2. Read the paper A BGP-based Mechanism for Lowest-Cost Routing by Feigenbaum, Papadimitriou, Sami, and Shenker.
3. Read the papers Distributed Implementation of Vickrey-Clarke-Cloves Mechanisms by D. Parkes and J. Schneidman and Incentive-Compatible Interdomain Routing by J. Feigenbaum, V. Ramachandran, and M. Schapira.
4. Make sure that you have read the papers Mechanism Design for Policy Routing, by J. Feigenbaum, R. Sami, and S. Shenker, and Subjective-Cost Policy Routing, by J. Feigenbaum, D. Karger, V. Mirrokni, and R. Sami, for the exam.
5. Read the following papers:
   1. Incentives Build Robustness in BitTorrent by Bram Cohen
   2. Regulating Technical Design by Pam Samuelson
   3. Did MGM Really Win the Grokster Case by Pam Samuelson
   4. Brief Amici Curiae by a group of computer science researchers (available on this page)
6. Please read the following papers:
   1. Modeling and Performance Analysis of BitTorrent-Like Peer-to-Peer Networks by D. Qiu and R. Srikant
   2. Incentives in BitTorrent Induce Free Riding by S. Jun and M. Ahamad
   3. Faithfulness in Internet Algorithms by J. Shneidman, D. Parkes and L. Massoulié
7. Read The Social Cost of Cheap Pseudonyms by E. Friedman and P. Resnick.
8. Read A Game-Theoretic Framework for Analyzing Trust-Inference Protocols, by R. Morselli, J. Katz, and B. Bhattacharjee.

• Students taking the course for credit will be required to give a Powerpoint presentation at the end of the semester. More details and suggested topics can be found here.
• If you have chosen a topic for your oral presentation, please send it to the TA by Tuesday, 1/31/06. If none of the suggested topics appeals to you, please set up a meeting with Professor Feigenbaum to discuss alternatives.
• The proposed presentation schedule is:

  April 6	Saint-Jean
  April 11	Alimi / Ruberry
  April 18	Reyzin / Srivastava
  April 20	Wang / Xiao

• Presentations should include:
  • Clear statement of the main problem(s) addressed in the papers you are presenting.
  • Clear statement of the main results in these papers.
  • Technical details of one of the main results.
  • Your critique of these papers and your thoughts on the most interesting directions for future research in this area.

Exams

• To be held in class on February 16, 2006.
• Covers these papers.
• Focuses on these key ideas.
• Will contain questions such as those described here.
• A copy of exam 1 is available here.
• The solutions for exam 1 are available here.

• To be held in class on April 4, 2006.
• Covers these papers.
• Focuses on these key ideas.
• Will contain the same types of questions as appeared on Exam 1. There might be a "short-essay" question on the Samuelson papers as well.
• A copy of exam 2 is available here.
• The solutions for exam 2 are available here.