Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering 75 EditorialBoard OzgurAkan MiddleEastTechnicalUniversity,Ankara,Turkey PaoloBellavista UniversityofBologna,Italy JiannongCao HongKongPolytechnicUniversity,HongKong FalkoDressler UniversityofErlangen,Germany DomenicoFerrari UniversitàCattolicaPiacenza,Italy MarioGerla UCLA,USA HisashiKobayashi PrincetonUniversity,USA SergioPalazzo UniversityofCatania,Italy SartajSahni UniversityofFlorida,USA Xuemin(Sherman)Shen UniversityofWaterloo,Canada MirceaStan UniversityofVirginia,USA JiaXiaohua CityUniversityofHongKong,HongKong AlbertZomaya UniversityofSydney,Australia GeoffreyCoulson LancasterUniversity,UK Rahul Jain Rajgopal Kannan (Eds.) Game Theory for Networks Second International ICST Conference GAMENETS 2011 Shanghai, China, April 16–18, 2011 Revised Selected Papers 1 3 VolumeEditors RahulJain UniversityofSouthernCalifornia LosAngeles,CA90089-2562,USA E-mail:[email protected] RajgopalKannan LouisianaStateUniversity BatonRouge,LA70803,USA E-mail:[email protected] ISSN1867-8211 e-ISSN1867-822X ISBN978-3-642-30372-2 e-ISBN978-3-642-30373-9 DOI10.1007/978-3-642-30373-9 SpringerHeidelbergDordrechtLondonNewYork LibraryofCongressControlNumber:2012937594 CRSubjectClassification(1998):C.2,H.4,D.2,H.3,I.2,K.6.5 ©ICSTInstituteforComputerScience,SocialInformaticsandTelecommunicationsEngineering2012 Thisworkissubjecttocopyright.Allrightsarereserved,whetherthewholeorpartofthematerialis concerned,specificallytherightsoftranslation,reprinting,re-useofillustrations,recitation,broadcasting, reproductiononmicrofilmsorinanyotherway,andstorageindatabanks.Duplicationofthispublication orpartsthereofispermittedonlyundertheprovisionsoftheGermanCopyrightLawofSeptember9,1965, initscurrentversion,andpermissionforusemustalwaysbeobtainedfromSpringer.Violationsareliable toprosecutionundertheGermanCopyrightLaw. Theuseofgeneraldescriptivenames,registerednames,trademarks,etc.inthispublicationdoesnotimply, evenintheabsenceofaspecificstatement,thatsuchnamesareexemptfromtherelevantprotectivelaws andregulationsandthereforefreeforgeneraluse. Typesetting:Camera-readybyauthor,dataconversionbyScientificPublishingServices,Chennai,India Printedonacid-freepaper SpringerispartofSpringerScience+BusinessMedia(www.springer.com) Preface The second edition of the International ICST Conference on Game Theory in Networks(GAMENETS2011)washeldduringApril16–18,2011,attheCrowne PlazaCenturyParkinShanghai,China,abeautifulvenueinternationallyrecog- nized for business, trading and rapidly becoming a conspolitan international city. This edition continued the scientific event previously held in Istanbul, Turkey(2009),withbotheventsbeingdedicatedtothelatestadvancesongame- theoreticmethodsandtechniquesforsolvingcommunicationandnetworksprob- lems. GAMENETS 2011 brought together researchers who apply game theory to analyze,design and assessthe performance of networks,including such prob- lems as cyber and network security, spectrum sharing, social network analysis, algorithmic game theory, etc. GAMENETS 2011 was organized as a 3-day 2-track event with 3 keynote speeches and 14 technical sessions. A total of 42 paper submissions were re- ceived from all over the world. All papers received rigorous peer reviews from the Technical ProgramCommittee (TPC). After carefully examining all the re- view reports, the TPC finally selected 24 regular papers for presentations at the conference with an acceptance rate of 57%. In addition, 23 papers were invited from well-known researchers in the area. The program included three outstanding keynote speakers from academia and industry: Nimrod Meggido (IBM Almaden Research), Sergiu Hart (Hebrew University of Jerusalem), and John Chuang (UC Berkeley). A social dinner was also scheduled on the second day of the conference. The conference had close to 60 participants from industry and academia from a wide range of countries such as the USA, Canada, France, Hong Kong, Singapore, China, India, Japan, UK, Italy, and Greece. We thank the invited keynote and other speakers for accepting our invitation, and taking out time to makeittotheconferenceinShanghai.WealsothankallmembersoftheTPCfor their valuable input in ensuring an excellent technical program. We also thank the GeneralCo-chairsThanosVasilakosandXinbingWang,andothermembers of the Organizing Committee for putting in so much hard work to make this event a great success. OurgratitudealsoextendstotherepresentativesofICST,EAI,andCREATE- NET for sponsoring this event and for their help in arranging all the logistics. A special acknowledgmentis due to Elena J. Fezzardifrom EAI for running the event smoothly. Last but not least, we the General Chairs would like to thank all the reviewers, whose effort reflects their commitment to the success of this yearly event. We eagerly look forward to another successful GAMENETS edition in 2012 and forthcoming years. Rahul Jain Rajgopal Kannan Organization Steering Committee Members Athanasios V. Vasilakos National Technical University of Athens, Greece Imrich Chlamtac Create-Net, Italy General Chair Athanasios V. Vasilakos National Technical University of Athens, Greece Xinbing Wang Shanghai Jiaotong University, China TPC Chairs Rajgopal Kannan LSU, USA Rahul Jain USC, USA Publication Chair Foad Dabiri UCLA, USA Workshops Chairs Hung-Yu Wei National Taiwan University Jang-Won Lee Yonsei University, Korea Hongyang Chen The University of Tokyo, Japan Web Chair Shen Gu Shanghai Jiaotong University, China Conference Coordinators Elena J. Fezzardi EAI, Italy Richard Heffernan EAI, Italy Table of Contents Session A1: Mechanism Design Mechanism Design with Limited Information: The Case of Nonlinear Pricing ......................................................... 1 Dirk Bergemann, Ji Shen, Yun Xu, and Edmund M. Yeh Hierarchical Auctions for Network Resource Allocation ............... 11 Wenyuan Tang and Rahul Jain Local Public Good Provision in Networks: A Nash Implementation Mechanism...................................................... 27 Shrutivandana Sharma and Demosthenis Teneketzis Session A2: Physical Layer Games Channel Assignment on Wireless Mesh Network Backbone with Potential Game Approach......................................... 43 Pedro B.F. Duarte, Zubair Md. Fadlullah, Athanasios V. Vasilakos, and Nei Kato Game Based Self-Organizing Scheme for Femtocell Networks .......... 57 Kwanghun Han, Seunghyun Choi, Du Ho Kang, and Sunghyun Choi Additively Coupled Sum Constrained Games ........................ 76 Yi Su and Mihaela van der Schaar Session B1: Network Neutrality and Regulation Technology Choices and Pricing Policies in Wireless Networks ......... 92 Yuanzhang Xiao, William R. Zame, and Mihaela van der Schaar Network Regulations and Market Entry............................. 108 Galina Schwartz, John Musacchio, Mark Felegyhazi, and Jean C. Walrand Bandwidth Exchange for Fair Secondary Coexistence in TV White Space .......................................................... 124 Dan Zhang and Narayan Mandayam Net Neutrality and Quality of Service .............................. 137 Eitan Altman, Julio Rojas, Sulan Wong, Manjesh Kumar Hanawal, and Yuedong Xu VIII Table of Contents Session B2: Network Mechanisms The Sharing-Mart System: Digital Content Sharing, Online Auctions, and Incentives ................................................... 153 Christopher Leberknight, Ranjan Pal, Mung Chiang, and Harold Vincent Poor Selfish Random Access: Equilibrium Conditions and Best-Response Learning........................................................ 169 Hazer Inaltekin, Mung Chiang, and Harold Vincent Poor Multi-portfolio Optimization: A Potential Game Approach ............ 182 Yang Yang, Francisco Rubio, Gesualdo Scutari, and Daniel Palomar Session C1: Stochastic and Dynamic Games Analyzing the Dynamics of Evolutionary Prisoner’s Dilemma on Structured Networks ............................................. 190 Ahmet Yasin Yazicioglu, Xiaoli Ma, and Yucel Altunbasak Spatio-temporal Control for Dynamic Routing Games ................ 205 Manjesh Kumar Hanawal, Eitan Altman, Rachid El-Azouzi, and Balakrishna J. Prabhu Designing Incentive Schemes Based on Intervention: The Case of Imperfect Monitoring............................................. 221 Jaeok Park and Mihaela van der Schaar Session C2: Security Games I How to Choose Communication Links in an Adversarial Environment? ................................................... 233 Assane Gueye, Jean C. Walrand, and Venkat Anantharam Adversary Games in Secure/Reliable Network Routing................ 249 Gruia Calinescu, Sanjiv Kapoor, Michael Quinn, and Junghwan Shin A Network Security Classification Game ............................ 265 Ning Bao, O. Patrick Kreidl, and John Musacchio Session D1: Algorithmic Game Theory and Learning Convergence Dynamics of Resource-HomogeneousCongestion Games ... 281 Richard Southwell and Jianwei Huang Bottleneck Routing Games on Grids................................ 294 Costas Busch, Rajgopal Kannan, and Alfred Samman Table of Contents IX Optimal Price of Anarchy of Polynomial and Super-Polynomial Bottleneck Congestion Games ..................................... 308 Rajgopal Kannan, Costas Busch, and Athanasios V. Vasilakos Performance and Convergence of Multi-user Online Learning .......... 321 Cem Tekin and Mingyan Liu Session D2: Game-Theoretic Network Models IncentivizingUploadCapacityinP2P-VoDSystems:AGameTheoretic Analysis ........................................................ 337 Weijie Wu, John C.S. Lui, and Richard T.B. Ma Service Routing in Multi-ISP Peer-to-Peer Content Distribution: Local or Remote? ................................................ 353 Parimal Parag, Srinivas Shakkottai, and Ishai Menache Bargaining and Peering between Network Content/Coverage Providers ....................................................... 369 Guosen Feng, Jianwei Huang, and Dah Ming Chiu Session E1: Cooperative Games in Networks Coalition Stability under QoS Based-MarketSegmentation ............ 383 Dominique Barth, Johanne Cohen, Loubna Echabbi, and H´el`ene Le Cadre On the Shapley-Like Payoff Mechanisms in Peer-Assisted Services with Multiple Content Providers........................................ 397 Jeong-woo Cho and Yung Yi Economic Viability of Femtocell Service Provision.................... 413 Lingjie Duan and Jianwei Huang Session E2: Security Games II Jamming Game in a Dynamic Slotted ALOHA Network .............. 429 Andrey Garnaev, Yezekael Hayel, Eitan Altman, and Konstantin Avrachenkov NashEquilibriaforWeakestTargetSecurityGameswithHeterogeneous Agents ......................................................... 444 Benjamin Johnson, Jens Grossklags, Nicolas Christin, and John Chuang Noisy Mean Field Game Model for Malware Propagation in Opportunistic Networks........................................... 459 Hamidou Tembine, Pedro Vilanova, and M´erouane Debbah X Table of Contents Session F1: Incentives for Relaying The Impact of Incomplete Information on Games in Parallel Relay Networks ....................................................... 475 Hongda Xiao and Edmund M. Yeh Hierarchical Coalition Formation Game of Relay Transmission in IEEE 802.16m ........................................................ 490 Dusit Niyato, Xiangyun Zhou, Are Hjørungnes, Ping Wang, and Yifan Li A Game-Theoretic Framework for Resource Allocation in IEEE 802.16j Transparent Relay Networks....................................... 506 Hui-Tang Lin and Ying-You Lin Session F2: Spectrum Sharing Games Dynamic Spectrum Negotiation with Asymmetric Information ......... 516 Yang Yan, Jianwei Huang, Xiaofeng Zhong, and Jing Wang Evolutionof Cooperation:A Case with Interference-AwareCooperative Spectrum Sensing in Cognitive Radio Networks ...................... 530 You-En Lin and Hung-Yun Hsieh A Game Theoretic Approach for Multi-hop Power Line Communications................................................. 546 Walid Saad, Zhu Han, and Harold Vincent Poor “To Sense” or “Not to Sense” in Energy-Efficient Power Control Games.......................................................... 562 Ma¨el Le Treust, Yezekael Hayel, Samson Lasaulce, and M´erouane Debbah Session G1: P2P and Social Networks DesigningSocialNormBasedIncentiveSchemestoSustainCooperation in a Large Community............................................ 578 Yu Zhang, Jaeok Park, and Mihaela van der Schaar Minimizing the Social Cost of an Epidemic.......................... 594 Elizabeth Bodine-Baron, Subhonmesh Bose, Babak Hassibi, and Adam Wierman “Two Is a Crowd” - Optimal Trend Adoption in Social Networks....... 608 Lilin Zhang and Peter Marbach Table of Contents XI Session G2: Economics of Network QoS Paris Metro Pricing for Internet Service Differentiation ............... 628 Dongmyung Lee, Taehyun Kim, Jeonghoon Mo, and Jinwoo Park Joint Price and QoS Market Share Game with Adversarial Service Providers and Migrating Customers ................................ 642 Mohamed Baslam, Loubna Echabbi, Rachid El-Azouzi, and Essaid Sabir Capacity Allocation Games for Network-Coded Multicast Streaming.... 658 Elliot Anshelevich, Bugra Caskurlu, Koushik Kar, and Hang Zhang Author Index.................................................. 675