Exam 1

Questions on the February 16th in-class exam will be drawn from:
  1. Algorithmic Mechanism Design by N. Nisan and A. Ronen (paper)
  2. A BGP-based Mechanism for Lowest-Cost Routing by J. Feigenbaum, C. Papadimitriou, R. Sami, and S. Shenker (paper, slides)
  3. Mechanism Design for Policy Routing by J. Feigenbaum, R. Sami, and S. Shenker (paper, slides)
  4. Subjective-Cost Policy Routing by J. Feigenbaum, D. Karger, V. Mirrokni, and R. Sami (paper)
  5. Distributed Implementation of Vickrey-Clarke-Groves Mechanisms by D. Parkes and J. Schneidman (paper)
    A more detailed paper about these ideas by the same authors can be found here.
  6. Incentive-Compatible Interdomain Routing by J. Feigenbaum, V. Ramachandran, and M. Schapira ([paper distributed in class], slides)
For background, you can also review the following papers, but no material from them will appear on the exam unless it also appears in one of the preceding six papers.
  1. Foundations of Interndomain Routing by V. Ramachandran (thesis, defense slides)
  2. Stable Internet Routing without Global Coordination by L. Gao and J. Rexford (paper, slides)
  3. An Analysis of BGP Convergence Properties by T. Griffin and G. Wilfong (paper)