Home
Key ideas to study for the exam on February 16, 2006
-
Algorithmic Mechanism Design by N. Nisan and A. Ronen (NR) (paper)
-
Mechanisms (Definition 3)
-
Dominant strategies (Definition 3)
-
Truthful implementation (Definition 4)
-
Utilitarian-maximization mechanism-design problems (Definition 6)
-
VCG mechanisms (Definition 7)
-
LCP example (Subsection 3.2)
-
A BGP-based Mechanism for Lowest-Cost Routing by J. Feigenbaum, C. Papadimitriou, R. Sami, and S. Shenker (FPSS) (paper, slides)
-
NR formulation of the LCP-Routing mechanism-design problem vs. FPSS formulation of the same problem, why the latter represents progress over the former, and why the latter is still inadequate (Section 1)
-
The basics of how BGP works and the BGP computational model (Section 5)
-
Statement of the Green-Laffont Theorem, application of the Green-Laffont Theorem to BGP-based LCP-price computation (Theorem 1), and noteworthy aspects of the price formula in Theorem 1 (Section 4)
-
Price-component computation via dynamic programming (Section 6) and why it leads to a good BGP-based algorithm (Theorem 2)
-
Mechanism Design for Policy Routing by J. Feigenbaum, R. Sami, and S. Shenker (FSS) (paper, slides)
-
Statement of the General Policy-Routing mechanism-design problem (Section 2) and its computational complexity (Section 3)
-
Statement of the Next-Hop Policy-Routing mechanism-design problem and its computational complexity (Section 4)
-
Relevance of NP-hardness results to BGP-based computation
-
Subjective-Cost Policy Routing by J. Feigenbaum, D. Karger, V. Mirrokni, and R. Sami (FKMS) (paper)
-
Statement of the general subjective-cost minimization problem (Sections 2 and 4) and its computational complexity (Theorem 2)
-
Statement of the forbidden-set routing problem (Section 2) and its computational complexity (Theorem 2)
-
Statement of the Stable-Paths Problem, its computational complexity, and bad triangles (Section 3)
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?
-
Distributed Implementation of Vickrey-Clarke-Groves Mechanisms by D. Parkes and J. Schneidman (PS) (paper, more detailed version)
-
Distributed mechanisms
-
Ex-post Nash Equilibrium
-
Incentive compatibility (IC), communication compatibility (CC), and algorithm compatibility (AC)
-
Faithful implementation
-
Incentive-Compatible Interdomain Routing by J. Feigenbaum, V. Ramachandran, and M. Schapira (FRS) ([paper distributed in class], slides)
-
The Gao-Rexford framework and its implications for BGP convergence (Subsection 3.1)
-
The BGP-compatible algorithm for route and price computation in networks in which ASes use next-hop policies and obey the Gao-Rexford conditions (Subsection 3.2)
-
Main points of the proof that this algorithm is truthful and correct (Subsection 3.3)
When studying the positive results in FPSS and FRS, focus, in particular, on understanding the modified routing tables on: