NDLI: Bounded budget connection (BBC) games or how to make friends and influence people, on a budget

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

Distributed computation of the mode

Anti-Ω: the weakest failure detector for set agreement

Collaborative enforcement of firewall policies in virtual private networks

On the complexity of asynchronous gossip

On a capacitated multivehicle routing problem

Flooding time in edge-Markovian dynamic graphs

Distributed algorithms for ultrasparse spanners and linear size skeletons

New combinatorial topology upper and lower bounds for renaming

Packet mode and QoS algorithms for buffered crossbar switches with FIFO queuing

Asynchronous exclusive selection

Forget him and keep on moving

BMobi_Causal: a causal broadcast protocol in mobile dynamic groups

A fast distributed slicing algorithm

A tradeoff analysis on message complexity and lifetime optimality for a distributed multicast algorithm in WSNs

Greedy distributed optimization of unsplittable multicommodity flows

Quantum distributed consensus

Optimizing consistency checking for memory-intensive transactions

The lotus-eater attack

Evolution of distributed computing theory: from concurrency to networks and beyond

Beyond nash equilibrium: solution concepts for the 21st century

Sublogarithmic distributed MIS algorithm for sparse graphs using nash-williams decomposition

Failure detectors in loosely named systems

Secure communication over radio channels

Brahms: byzantine resilient random membership sampling

Improved compact routing schemes for dynamic trees

On the effect of the deployment setting on broadcasting in Euclidean radio networks

Efficient distributed approximation algorithms via probabilistic tree embeddings

Timeliness-based wait-freedom: a gracefully degrading progress condition

The impact of randomization in smoothing networks

Fast self-stabilizing byzantine tolerant digital clock synchronization

Online and dynamic embeddings of approximate ultrametrics

Correctness criteria for replicated database systems with snapshot isolation replicas

A dynamic exchange game

Nearest-neighbor graphs on random point sets and their applications to sensor networks

Stateless distributed algorithms for near optimal maximum multicommodity flows

Looking for the optimal conditions for solving set agreement

Wait-free programming for general purpose computations on graphics processors

Extracting models from design documents with mapster

A world of (Im) possibilities

The internet is flat: a brief history of networking in the next ten years

A log-star distributed maximal independent set algorithm for growth-bounded graphs

Every problem has a weakest failure detector

On tradeoff between network connectivity, phase complexity and communication complexity of reliable communication tolerating mixed adversary

Efficient randomised broadcasting in random regular networks with applications in peer-to-peer systems

Tight bounds for delay-sensitive aggregation

Virtual infrastructure for collision-prone wireless networks

On the locality of distributed sparse spanner construction

Lower bounds for randomized consensus under a weak adversary

Optimizing data popularity conscious bloom filters

OCD: obsessive consensus disorder (or repetitive consensus)

Dynamic routing and location services in metrics of low doubling dimension

The asynchronous bounded-cycle model

Anonymous and censorship resistant content sharing in unstructured overlays

From anarchy to geometric structuring: the power of virtual coordinates

Distributed averaging in the presence of a sparse cut

Tight RMR lower bounds for mutual exclusion and other problems

Transactional memory retry mechanisms

Efficient single phase unconditionally secure message transmission with optimum communication complexity

The power of simulation relations

Accountability for distributed systems

A jamming-resistant MAC protocol for single-hop wireless networks

Sharing is harder than agreeing

CAR-STM: scheduling-based collision avoidance and resolution for software transactional memory

Bounded budget connection (BBC) games or how to make friends and influence people, on a budget

The forgiving tree: a self-healing distributed data structure

Sleeping on the job: energy-efficient and robust broadcast for radio networks

The stretched exponential distribution of internet media access patterns

Randomized consensus in expected O(n log n) individual work

Distributed order scheduling and its application to multi-core dram controllers

An almost-surely terminating polynomial protocol for asynchronous byzantine agreement with optimal resilience

On ad hoc routing with guaranteed delivery

Model checking transactional memory with spin

Our brothers' keepers

Balancing energy consumption for uniform data gathering wireless sensor networks

Gossip-based aggregate computation: computing faster with non address-oblivious schemes

Closing the complexity gap between mutual exclusion and FCFS mutual exclusion

Scheduling tasks with dependencies on asymmetric multiprocessors

Mobile proactive secret sharing

On fault tolerance and wireless networks

On the internet delay space dimensionality

On the robustness of (semi) fast quorum-based implementations of atomic shared memory

Distributed churn measurement in arbitrary networks

Scheduling sensors by tilinglattices

Snap-stabilization in message-passing systems

Fault-tolerant implementations of atomic registers by safe registers in networks

The future of distributed computing: renaissance or reformation?

Maximizing quorum availability in multi-clustered systems

Principles of untrusted storage: a new look at consistency conditions

Efficient pipeline configuration in distributed heterogeneous computing environments

Power management of devices: when should i switch off?

Dynamic service assignment in mobile networks: the magma approach

Optimal failure detection with low sporadic overhead and communication locality

Bounded budget connection (BBC) games or how to make friends and influence people, on a budget

Content Provider	ACM Digital Library
Author	Laoutaris, Nikolaos Poplawski, Laura J. Teng, Shang-Hua Rajaraman, Rajmohan Sundaram, Ravi
Abstract	Motivated by applications in social networks, peer-to-peer and overlay networks, we define and study the Bounded Budget Connection (BBC) game - we have a collection of n players or nodes each of whom has a budget for purchasing links; each link has a cost as well as a length and each node has a set of preference weights for each of the remaining nodes; the objective of each node is to use its budget to buy a set of outgoing links so as to minimize its sum of preference-weighted distances to the remaining nodes. We study the structural and complexity-theoretic properties of pure Nash equilibria in BBC games. We show that determining the existence of a pure Nash equilibrium in general BBC games is NP-hard. A major focus is the study of (n,k)-uniform BBC games - those in which all link costs, link lengths and preference weights are equal (to 1) and all budgets are equal (to k). We show that a pure Nash equilibrium or stable graph exists for all (n,k)-uniform BBC games and that all stable graphs are essentially fair (i.e. all nodes have similar costs). We provide an explicit construction of a family of stable graphs that spans the spectrum from minimum total social cost to maximum total social cost. To be precise we show that that the price of stability is Θ(1) and the price of anarchy is Ω(√n/k / $log_{k}$ n) and $O(√n/log_{k}$ n). We analyze best-response walks on the configuration space defined by the uniform game, and show that starting from any initial configuration, strong connectivity is reached within $n^{2}$ rounds. We demonstrate that convergence to a pure Nash equilibrium is not guaranteed by demonstrating the existence of an explicit loop which also proves that even uniform BBC games are not potential games. Lastly, we extend our results to the case where each node seeks to minimize its maximum distance to the other nodes.
Starting Page	165
Ending Page	174
Page Count	10
File Format	PDF
ISBN	9781595939890
DOI	10.1145/1400751.1400774
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2008-08-18
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Network construction Equilibria 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