Home

Key ideas to study for the exam on February 16, 2006

  1. Algorithmic Mechanism Design by N. Nisan and A. Ronen (NR) (paper)
  2. A BGP-based Mechanism for Lowest-Cost Routing by J. Feigenbaum, C. Papadimitriou, R. Sami, and S. Shenker (FPSS) (paper, slides)
  3. Mechanism Design for Policy Routing by J. Feigenbaum, R. Sami, and S. Shenker (FSS) (paper, slides)
  4. Subjective-Cost Policy Routing by J. Feigenbaum, D. Karger, V. Mirrokni, and R. Sami (FKMS) (paper)

How do the above variations on the incentive-compatible interdomain-routing problem relate to each other? For example, for which pairs is one a special case of the other? More generally, for which pairs is one reducible to the other?
  1. Distributed Implementation of Vickrey-Clarke-Groves Mechanisms by D. Parkes and J. Schneidman (PS) (paper, more detailed version)
  2. Incentive-Compatible Interdomain Routing by J. Feigenbaum, V. Ramachandran, and M. Schapira (FRS) ([paper distributed in class], slides)

When studying the positive results in FPSS and FRS, focus, in particular, on understanding the modified routing tables on: