NDLI: Locality-Based Network Creation Games

Please wait, while we are loading the content...

Locality-Based Network Creation Games

Content Provider	ACM Digital Library
Author	Leucci, Stefano Gualà, Luciano Bilò, Davide Proietti, Guido
Copyright Year	2016
Abstract	Network creation games have been extensively studied, both by economists and computer scientists, due to their versatility in modeling individual-based community formation processes. These processes, in turn, are the theoretical counterpart of several economics, social, and computational applications on the Internet. In their several variants, these games model the tension of a player between the player’s two antagonistic goals: to be as close as possible to the other players and to activate a cheapest possible set of links. However, the generally adopted assumption is that players have a common and complete information about the ongoing network, which is quite unrealistic in practice. In this article, we consider a more compelling scenario in which players have only limited information about the network in whicy they are embedded. More precisely, we explore the game-theoretic and computational implications of assuming that players have a complete knowledge of the network structure only up to a given radius $\textit{k},$ which is one of the most qualified local-knowledge models used in distributed computing. In this respect, we define a suitable equilibrium concept, and we provide a comprehensive set of upper and lower bounds to the price of anarchy for the entire range of values of $\textit{k}$ and for the two classic variants of the game, namely, those in which a player’s cost—besides the activation cost of the owned links—depends on the maximum/sum of all distances to the other nodes in the network, respectively. These bounds are assessed through an extensive set of experiments.
Starting Page	1
Ending Page	26
Page Count	26
File Format	PDF
ISSN	23294949
e-ISSN	23294957
DOI	10.1145/2938426
Volume Number	3
Issue Number	1
Journal	ACM Transactions on Parallel Computing (TOPC)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2016-07-18
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Game theory Local knowledge Network creation games Price of anarchy
Content Type	Text
Resource Type	Article
Subject	Hardware and Architecture Modeling and Simulation Computer Science Applications Software Computational Theory and Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Locality-based network creation games

Hedonic Clustering Games

Bounded-Distance Network Creation Games

A Bounded Budget Network Creation Game

A network pricing game for selfish traffic

Approximating Congestion + Dilation in Networks via "Quality of Routing” Games

The price of anarchy in network creation games

Well-Structured Futures and Cache Locality

Network Creation Games with Traceroute-Based Strategies

Locality-Based Network Creation Games

Similar Documents

Locality-based network creation games

Hedonic Clustering Games

Bounded-Distance Network Creation Games

A Bounded Budget Network Creation Game

A network pricing game for selfish traffic

Approximating Congestion + Dilation in Networks via "Quality of Routing&#x201D; Games

The price of anarchy in network creation games

Well-Structured Futures and Cache Locality

Network Creation Games with Traceroute-Based Strategies

Locality-Based Network Creation Games

Approximating Congestion + Dilation in Networks via "Quality of Routing” Games