Incentive-Compatible Distributed Routing: Mechanism Design Without Payments

interdomain routing in today's Internet. In this model the strategic agents are source-nodes located on a network, who aim to send traffic to a unique destination node. The model enables complex dynamic interactions between the agents (asynchronous, sequential, and based on partial-information).

We study the consequences of greedy myopic behaviour in this setting. We provide realistic conditions that guarantee that greedy myopic behaviour is in the best interest of each of the players. In other words, not only does myopic and greedy behaviour of all players converge to a "stable" routing outcome, but no single player has motivation to deviate. Moreover, we show that even coalitions of players of any size cannot improve their routing outcomes by jointly deviating from the myopic greedy behaviour.
The only protocol currently used for interdomain routing, namely the Border gateway Protocol (BGP), is based on myopic greedy interaction. Hence, from a practical perspective, our results show that for the central and important interdomain routing setting, the protocol currently in use can be shown to possess extremely strong game-theoretic properties .

From a theoretical perspective, the strengths of our results lie in the following facts: Firstly, unlike the vast majority of works in mechanism design, these results do not require any monetary transfers (to or by the agents). Secondly, unlike most previous works on selfish routing our results do not restrict the preferences of players over routes to such that always prefer shorter routes to longer ones. We allow significantly more complex preferences. Finally, our results are the first step in the systematic exploration of incentive-compatible myopic convergence in Algorithmic Mechanism Design.

Based on joint work with Hagay Levin and Aviv Zohar
(see http://www.cs.huji.ac.il/~mikesch/bgp.pdf)