Mechanism Design for Policy Routing

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 (i.e., 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 nexthop preferences.We present a strategyproof, polynomialtime 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,