@Article{feigenbaum06a,
  author =	 {Joan Feigenbaum and Rahul Sami and Scott Shenker},
  title =	 {Mechanism design for policy routing},
  journal =	 {Distributed Computing},
  year =	 2006,
  volume =	 18,
  number =	 4,
  pages =	 {293--305},
  month =	 {March},
  abstract =	 {The Border Gateway Protocol (BGP) for interdomain
                  routing is designed to allow autonomous systems
                  (ASes) to express policy preferences over
                  alternative routes. We model these preferences as
                  arising from an AS's underlying utility for each
                  route and study the problem of finding a set of
                  routes that maximizes the overall welfare (ie, the
                  sum of all ASes' utilities for their selected
                  routes). We show that, if the utility functions are
                  unrestricted, this problem is NP-hard even to
                  approximate closely. We then study a natural class
                  of restricted utilities that we call next-hop
                  preferences. We present a strategyproof,
                  polynomial-time computable mechanism for
                  welfare-maximizing routing over this restricted
                  domain. However, we show that, in contrast to
                  earlier work on lowest-cost routing mechanism
                  design, this mechanism appears to be incompatible
                  with BGP and hence difficult to implement in the
                  context of the current Internet. Our contributions
                  include a new complexity measure for Internet
                  algorithms, dynamic stability, which may be useful
                  in other problem domains.},
  url = 	 {http://jmvidal.cse.sc.edu/library/feigenbaum06a.pdf},
  doi = 	 {10.1007/s00446-005-0134-7},
  cluster = 	 {3446771975692535651},
  keywords = 	 {mechanism-design networks}
}