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)

Utilitarianmaximization mechanismdesign problems (Definition 6)

VCG mechanisms (Definition 7)

LCP example (Subsection 3.2)

A BGPbased Mechanism for LowestCost Routing by J. Feigenbaum, C. Papadimitriou, R. Sami, and S. Shenker (FPSS) (paper, slides)

NR formulation of the LCPRouting mechanismdesign 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 GreenLaffont Theorem, application of the GreenLaffont Theorem to BGPbased LCPprice computation (Theorem 1), and noteworthy aspects of the price formula in Theorem 1 (Section 4)

Pricecomponent computation via dynamic programming (Section 6) and why it leads to a good BGPbased algorithm (Theorem 2)

Mechanism Design for Policy Routing by J. Feigenbaum, R. Sami, and S. Shenker (FSS) (paper, slides)

Statement of the General PolicyRouting mechanismdesign problem (Section 2) and its computational complexity (Section 3)

Statement of the NextHop PolicyRouting mechanismdesign problem and its computational complexity (Section 4)

Relevance of NPhardness results to BGPbased computation

SubjectiveCost Policy Routing by J. Feigenbaum, D. Karger, V. Mirrokni, and R. Sami (FKMS) (paper)

Statement of the general subjectivecost minimization problem (Sections 2 and 4) and its computational complexity (Theorem 2)

Statement of the forbiddenset routing problem (Section 2) and its computational complexity (Theorem 2)

Statement of the StablePaths Problem, its computational complexity, and bad triangles (Section 3)
How do the above variations on the incentivecompatible interdomainrouting 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 VickreyClarkeGroves Mechanisms by D. Parkes and J. Schneidman (PS) (paper, more detailed version)

Distributed mechanisms

Expost Nash Equilibrium

Incentive compatibility (IC), communication compatibility (CC), and algorithm compatibility (AC)

Faithful implementation

IncentiveCompatible Interdomain Routing by J. Feigenbaum, V. Ramachandran, and M. Schapira (FRS) ([paper distributed in class], slides)

The GaoRexford framework and its implications for BGP convergence (Subsection 3.1)

The BGPcompatible algorithm for route and price computation in networks in which ASes use nexthop policies and obey the GaoRexford 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: