{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T12:42:54Z","timestamp":1740141774689,"version":"3.37.3"},"reference-count":39,"publisher":"SAGE Publications","issue":"1","license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-0427202"],"award-info":[{"award-number":["CCF-0427202"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["International Journal of Distributed Sensor Networks"],"published-print":{"date-parts":[[2011,1,1]]},"abstract":"<jats:p> We study game-theoretic mechanisms for routing in wireless ad hoc networks. Our major results include a combination of theoretical bounds and extensive simulations, showing that VCG-based routing in wireless ad-hoc networks exhibits small frugality ratio with high probability. Game-theoretic mechanisms capture the noncooperative and selfish behavior of nodes in a resource-constrained environment. There have been some recent proposals to use these mechanisms (in particular VCG) for routing in wireless ad-hoc networks, and some frugality bounds are known when the connectivity graph is essentially complete. We are the first to show frugality bounds for random geometric graphs, a well-known model for ad-hoc wireless connectivity. In addition, we generalize the model of agent behavior by allowing sets of nodes to form communities to maximize total profit. We are the first to analyze the performance of VCG under such a community model. While some recent truthful protocols for the traditional (individual) agent model have improved upon the frugality of VCG by selecting paths to minimize not only the cost but the overpayment, we show that extending such protocols to the community model requires solving NP-complete problems which are provably hard to approximate. <\/jats:p>","DOI":"10.1155\/2011\/895398","type":"journal-article","created":{"date-parts":[[2011,6,27]],"date-time":"2011-06-27T21:41:31Z","timestamp":1309210891000},"page":"895398","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":0,"title":["VCG with Communities on Random Ad Hoc Networks"],"prefix":"10.1177","volume":"7","author":[{"given":"Gunes","family":"Ercal","sequence":"first","affiliation":[{"name":"University of Kansas, Lawrence, KS 66045, USA"}]},{"given":"Rafit","family":"Izhak-Ratzin","sequence":"additional","affiliation":[{"name":"Palo Alto Networks, Sunnyvale, CA 94089, USA"}]},{"given":"Rupak","family":"Majumdar","sequence":"additional","affiliation":[{"name":"Max Planck Institute, 66123 Saarbruecken, Germany"}]},{"given":"Adam","family":"Meyerson","sequence":"additional","affiliation":[{"name":"University of California, Los Angeles, CA 90095, USA"}]}],"member":"179","published-online":{"date-parts":[[2011,5,22]]},"reference":[{"first-page":"749","volume-title":"Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (STOC '01)","author":"Papadimitriou C. H.","key":"B1-2011-895398"},{"first-page":"245","volume-title":"Proceedings of the 9th Annual International Conference on Mobile Computing and Networking (MobiCom '03)","author":"Anderegg L.","key":"B2-2011-895398"},{"key":"B3-2011-895398","doi-asserted-by":"publisher","DOI":"10.1515\/9780691215747"},{"key":"B4-2011-895398","doi-asserted-by":"publisher","DOI":"10.1006\/game.1999.0790"},{"key":"B5-2011-895398","doi-asserted-by":"publisher","DOI":"10.1111\/j.1540-6261.1961.tb02789.x"},{"key":"B6-2011-895398","doi-asserted-by":"publisher","DOI":"10.1007\/BF01726210"},{"key":"B7-2011-895398","doi-asserted-by":"publisher","DOI":"10.2307\/1914085"},{"first-page":"991","volume-title":"Proceedings of the 13th Annual ACM\/SIAM Symposium on Discrete Algorithms (SODA '02)","author":"Archer A.","key":"B8-2011-895398"},{"key":"B9-2011-895398","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"608","DOI":"10.1007\/3-540-36494-3_53","volume-title":"Proceedings of the the 20th Annual Symposium on Theoretical Aspects of Computer Science (STACS '03)","volume":"2607","author":"Talwar K."},{"key":"B10-2011-895398","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.25"},{"first-page":"1593","volume-title":"Proceedings of the Canadian Conference on Electrical and Computer Engineering","author":"Sun H.","key":"B11-2011-895398"},{"first-page":"402","volume-title":"Proceedings of the 12th Annual International Conference on Mobile Computing and Networking (MobiCom '06)","author":"Wang W.","key":"B12-2011-895398"},{"first-page":"117","volume-title":"Proceedings of the 11th Annual International Conference on Mobile Computing and Networking (MobiCom '05)","author":"Zhong S.","key":"B13-2011-895398"},{"first-page":"31","volume-title":"Proceedings of the 2nd International Workshop on Multi-Hop Ad Hoc Networks: From Theory to Reality (REALMAN '06)","author":"Musolesi M.","key":"B14-2011-895398"},{"key":"B15-2011-895398","doi-asserted-by":"publisher","DOI":"10.1109\/MPRV.2003.1186728"},{"volume-title":"Proceedings of the AAAI Symposium on Agent-Mediated Knowledge Management","author":"Schulz S.","key":"B16-2011-895398"},{"first-page":"20","volume-title":"Proceedings of the 7th ACM International Symposium on Modeling, Analysis and Simulation of Wireless and Mobile Systems (MSWiM '04)","author":"Musolesi M.","key":"B17-2011-895398"},{"volume-title":"Proceedings of the 1st International Workshop on Wireless Information Systems in Conjunction with the 4th International Conference on Enterprise Information Systems","author":"Patrick A.","key":"B18-2011-895398"},{"key":"B19-2011-895398","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198506263.001.0001"},{"key":"B20-2011-895398","doi-asserted-by":"publisher","DOI":"10.1109\/18.825799"},{"key":"B21-2011-895398","doi-asserted-by":"publisher","DOI":"10.1214\/105051605000000575"},{"first-page":"989","volume-title":"Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '05)","author":"Muthukrishnan S.","key":"B22-2011-895398"},{"first-page":"677","volume-title":"Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP '05)","author":"Avin C.","key":"B23-2011-895398"},{"key":"B24-2011-895398","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626400000329"},{"key":"B25-2011-895398","doi-asserted-by":"publisher","DOI":"10.1007\/s11276-005-1767-y"},{"key":"B26-2011-895398","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814075"},{"first-page":"133","volume-title":"Proceedings of the 1st International Symposium on Algorithmic Game Theory (SAGT '08)","author":"Ercal G.","key":"B27-2011-895398"},{"key":"B29-2011-895398","doi-asserted-by":"publisher","DOI":"10.1145\/352871.352898"},{"first-page":"701","volume-title":"Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '04)","author":"Elkind E.","key":"B30-2011-895398"},{"volume-title":"Proceedings of the Workshop on the Economics of Networks, Systems and Computation (NetEcon '06)","author":"Du Y.","key":"B31-2011-895398"},{"first-page":"173","volume-title":"Proceedings of the 21st Annual ACM Symposium on Principles of Distributed Computing (PODC '02)","author":"Feigenbaum J.","key":"B32-2011-895398"},{"first-page":"28","volume-title":"Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS '03)","author":"Mihail M.","key":"B33-2011-895398"},{"volume-title":"Proceedings of the DIMACS Workshop on Computational Issues in Auction Design","author":"Karger D.","key":"B34-2011-895398"},{"key":"B35-2011-895398","doi-asserted-by":"publisher","DOI":"10.1145\/1064009.1064031"},{"key":"B37-2011-895398","doi-asserted-by":"publisher","DOI":"10.1016\/j.comnet.2004.10.013"},{"key":"B38-2011-895398","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2003.11.007"},{"first-page":"176","volume-title":"Proceedings of the 23rd International Symposium on Mathematical Foundations of Computer Science (MFCS '98)","author":"Alekhnovich M.","key":"B39-2011-895398"},{"first-page":"345","volume-title":"Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '00)","author":"Carr R. D.","key":"B40-2011-895398"},{"key":"B41-2011-895398","unstructured":"Wirth H. C.Multicriteria approximation of network design and network up-grade problems, Ph.D. thesis2001"}],"container-title":["International Journal of Distributed Sensor Networks"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/downloads.hindawi.com\/journals\/ijdsn\/2011\/895398.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/journals.sagepub.com\/doi\/full-xml\/10.1155\/2011\/895398","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/journals.sagepub.com\/doi\/full\/10.1155\/2011\/895398","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,28]],"date-time":"2021-05-28T14:53:12Z","timestamp":1622213592000},"score":1,"resource":{"primary":{"URL":"http:\/\/journals.sagepub.com\/doi\/10.1155\/2011\/895398"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,1,1]]},"references-count":39,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2011,1,1]]}},"alternative-id":["10.1155\/2011\/895398"],"URL":"https:\/\/doi.org\/10.1155\/2011\/895398","relation":{},"ISSN":["1550-1477","1550-1477"],"issn-type":[{"type":"print","value":"1550-1477"},{"type":"electronic","value":"1550-1477"}],"subject":[],"published":{"date-parts":[[2011,1,1]]}}}