Ad hoc-VCG: a truthful and cost-efficient routing protocol for mobile ad hoc networks with selfish agents. Anderegg, L. & Eidenbenz, S. 2003.
Ad hoc-VCG: a truthful and cost-efficient routing protocol for mobile ad hoc networks with selfish agents [link]Paper  doi  abstract   bibtex   
We introduce a game-theoretic setting for routing in a mobile ad hoc network that consists of greedy, selfish agents who accept payments for forwarding data for other agents if the payments cover their individual costs incurred by forwarding data. In this setting, we propose Ad hoc-VCG, a reactive routing protocol that achieves the design objectives of truthfulness (i.e., it is in the agents\textquoteright best interest to reveal their true costs for forwarding data) and cost-efficiency (i.e., it guarantees that routing is done along the most cost-efficient path) in a game-theoretic sense by paying to the intermediate nodes a premium over their actual costs for forwarding data packets. We show that the total overpayment (i.e., the sum of all premiums paid) is relatively small by giving a theoretical upper bound and by providing experimental evidence. Our routing protocol implements a variation of the well-known mechanism by Vickrey, Clarke, and Groves in a mobile network setting. Finally, we analyze a very natural routing protocol that is an adaptation of the Packet Purse Model [8] with auctions in our setting and show that, unfortunately, it does not achieve cost-efficiency or truthfulness.
@conference {939011,
	title = {Ad hoc-VCG: a truthful and cost-efficient routing protocol for mobile ad hoc networks with selfish agents},
	booktitle = {MobiCom {\textquoteright}03: Proceedings of the 9th annual international conference on Mobile computing and networking},
	year = {2003},
	pages = {245{\textendash}259},
	publisher = {ACM},
	organization = {ACM},
	address = {New York, NY, USA},
	abstract = {We introduce a game-theoretic setting for routing in a mobile ad hoc network that consists of greedy, selfish agents who accept payments for forwarding data for other agents if the payments cover their individual costs incurred by forwarding data. In this setting, we propose Ad hoc-VCG, a reactive routing protocol that achieves the design objectives of truthfulness (i.e., it is in the agents{\textquoteright} best interest to reveal their true costs for forwarding data) and cost-efficiency (i.e., it guarantees that routing is done along the most cost-efficient path) in a game-theoretic sense by paying to the intermediate nodes a premium over their actual costs for forwarding data packets. We show that the total overpayment (i.e., the sum of all premiums paid) is relatively small by giving a theoretical upper bound and by providing experimental evidence. Our routing protocol implements a variation of the well-known mechanism by Vickrey, Clarke, and Groves in a mobile network setting. Finally, we analyze a very natural routing protocol that is an adaptation of the Packet Purse Model [8] with auctions in our setting and show that, unfortunately, it does not achieve cost-efficiency or truthfulness.},
	keywords = {ad-hoc networks, energy efficiency, game theory, mechanism design, routing, selfish agents, VCG mechanism},
	isbn = {1-58113-753-2},
	doi = {10.1145/938985.939011},
	url = {http://portal.acm.org/citation.cfm?id=939011$\#$},
	author = {Anderegg, Luzi and Eidenbenz, Stephan}
}

Downloads: 0