NDLI: On a bounded budget network creation game

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

Graph expansion and communication costs of fast matrix multiplication: regular submission

A study of transactional memory vs. locks in practice

Filtering: a method for solving graph problems in MapReduce

Brief announcement: full reversal routing as a linear dynamical system

A tight runtime bound for synchronous gathering of autonomous robots with limited visibility

Approximation algorithms for secondary spectrum auctions

Online packet-routing in grids with bounded buffers

Brief announcement: distributed shared memory based on computation migration

On a local protocol for concurrent file transfers

Brief announcement: a partitioned ticket lock

Tight bounds for anonymous adopt-commit objects

Scheduling irregular parallel computations on hierarchical caches

Near linear-work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs

Optimizing hybrid transactional memory: the importance of nonspeculative operations

Parallelism and data movement characterization of contemporary application classes

Brief announcement: better speedups for parallel max-flow

Stabilizing consensus with the power of two choices

Maximising lifetime for fault-tolerant target coverage in sensor networks

Sparse spanners vs. compact routing

Brief announcement: communication bounds for heterogeneous architectures

On multi-processor speed scaling with migration: extended abstract

Brief announcement: transaction polymorphism

A highly-efficient wait-free universal construction

Sharing-aware algorithms for virtual machine colocation

Linear-work greedy parallel approximate set cover and variants

Flat-combining NUMA locks

Work-stealing for mixed-mode parallelism by deterministic team-building

Brief announcement: reclaiming the energy of a schedule, models and algorithms

Convergence of local communication chain strategies via linear transformations: or how to trade locality for speed

Convergence to equilibrium of logit dynamics for strategic games

Re-Chord: a self-stabilizing chord overlay network

Brief announcement: large-scale multimaps

On scheduling in map-reduce and flow-shops

Brief announcement: multilane - a concurrent blocking multiset

A lock-free algorithm for concurrent bags

Data-oblivious external-memory algorithms for the compaction, selection, and sorting of outsourced data

Parallelism in dynamic well-spaced point sets

Location-based memory fences

The pochoir stencil compiler

Brief announcement: paging for multicore processors

The car sharing problem

On a bounded budget network creation game

Recommender systems with non-binary grades

Brief announcement: processor allocation for optimistic parallelization of irregular programs

Finding heavy distinct hitters in data streams

Brief announcement: read invisibility, virtual world consistency and permissiveness are compatible

Understanding bloom filter intersection for lazy address-set disambiguation

Brief announcement: locality-enhancing loop transformations for tree traversal algorithms

Brief announcement: program regularization in verifying memory consistency

Brief announcement: RedRem: a parallel redundancy remover

On a bounded budget network creation game

Content Provider	ACM Digital Library
Author	Sadeghian Sadeghabad, Sina Ehsani, Shayan Fazli, MohammadAmin Mehrabian, Abbas Saghafian, Morteza Safari, MohammadAli ShokatFadaee, Saber
Abstract	We consider a network creation game in which, each player (vertex) has a limited budget to establish links to other players. In our model, each link has a unit cost and each agent tries to minimize its cost which is its local diameter or its total distance to other players in the (undirected) underlying graph of the created network. Two variants of the game are studied: in the MAX version, the cost incurred to a vertex is the maximum distance between that vertex and other vertices, and in the SUM version, the cost incurred to a vertex is the sum of distances between that vertex and other vertices. We prove that in both versions pure Nash equilibria exist, but the problem of finding the best response of a vertex is NP-hard. Next, we study the maximum possible diameter of an equilibrium graph with n vertices in various cases. For infinite numbers of n, we construct an equilibrium tree with diameter Θ(n) in the MAX version. Also, we prove that the diameter of any equilibrium tree is O(log n) in the SUM version and this bound is tight. When all vertices have unit budgets (i.e.~can establish link to just one vertex), the diameter in both versions is O(1). We give an example of equilibrium graph in MAX version, such that all vertices have positive budgets and yet the diameter is as large as Ω(√log n). This interesting result shows that the diameter does not decrease necessarily and may increase as the budgets are increased. For the SUM version, we prove that every equilibrium graph has diameter 2O(√log n) when all vertices have positive budgets. Moreover, if the budget of every players is at least k, then every equilibrium graph with diameter more than 3 is k-connected.
Starting Page	207
Ending Page	214
Page Count	8
File Format	PDF
ISBN	9781450307437
DOI	10.1145/1989493.1989523
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2011-06-04
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Network design Nash equilibrium Game theory
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

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