Generalized Second Price Auction in Multi-Path Routing With Selfish Nodes

The authors model the multi-path routing with selfish nodes as an auction and provide a novel solution from the game theoretical perspective. By adapting the idea of Generalized Second Price (GSP) payment originating from Internet advertising business and developing pertinent policies for multi-hop networks, they design a mechanism that results in Nash equilibria rather than the traditional strategyproofness, which alleviates the over-payment problem of the widely used Vickrey-Clark-Groves (VCG) payment mechanism. They first provide rigorous theoretical analysis of the proposed mechanism, showing the equilibrium behavior and bounds of the over-payment alleviation, and then evaluate the effectiveness of this protocol through extensive simulations.