NDLI: Brief Announcement: Efficient Best Response Computation for Strategic Network Formation under Attack

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

Beyond P vs. NP: Quadratic-Time Hardness for Big Data Problems

Randomized Composable Coresets for Matching and Vertex Cover

Asymptotically Optimal Approximation Algorithms for Coflow Scheduling

Bounding Laconic Proof Systems by Solving CSPs in Parallel

Some Sequential Algorithms are Almost Always Parallel

Distributed Partial Clustering

Is Our Model for Contention Resolution Wrong?: Confronting the Cost of Collisions

Concurrent Data Structures for Near-Memory Computing

Near Optimal Parallel Algorithms for Dynamic DFS in Undirected Graphs

Online Tree Caching

Almost Optimal Streaming Algorithms for Coverage Problems

Online Flexible Job Scheduling for Minimum Span

Matrix Multiplication, a Little Faster

Distributed Detection of Cycles

Optimal Reissue Policies for Reducing Tail Latency

Lower Bounds in the Asymmetric External Memory Model

Julienne: A Framework for Parallel Graph Algorithms using Work-efficient Bucketing

Provably Efficient Scheduling of Cache-oblivious Wavefront Algorithms

Bicriteria Distributed Submodular Maximization in a Few Rounds

Minimizing Total Weighted Flow Time with Calibrations

A Communication-Avoiding Parallel Algorithm for the Symmetric Eigenvalue Problem

Distributed Graph Clustering by Load Balancing

Impact of Knowledge on Election Time in Anonymous Networks

Hand-Over-Hand Transactions with Precise Memory Reclamation

Improved Cover Time Bounds for the Coalescing-Branching Random Walk on Graphs

Bounding Cache Miss Costs of Multithreaded Computations Under General Schedulers: Extended Abstract

On Energy Conservation in Data Centers

Tight Bounds for Clairvoyant Dynamic Bin Packing

Sharing is Caring: Multiprocessor Scheduling with a Sharable Resource

Fast Scheduling in Distributed Transactional Memory

Swarm-based Incast Congestion Control in Datacenters Serving Web Applications

Optimal Local Buffer Management for Information Gathering with Adversarial Traffic

The Mobile Server Problem

Brief Announcement: Meeting the Challenges of Parallelizing Sequential Programs

Brief Announcement: Scheduling Parallelizable Jobs Online to Maximize Throughput

Brief Announcement: Graph Matching in Massive Datasets

Brief Announcement: Approximation Algorithms for Unsplittable Resource Allocation Problems with Diseconomies of Scale

Brief Announcement: Parallel Dynamic Tree Contraction via Self-Adjusting Computation

Brief Announcement: Efficient Best Response Computation for Strategic Network Formation under Attack

Brief Announcement: Hazard Eras - Non-Blocking Memory Reclamation

Brief Announcement: A New Improved Bound for Coflow Scheduling

Brief Announcement: Using Multi-Level Parallelism and 2-3 Cuckoo Filters for Set Intersection Queries and Sparse Boolean Matrix Multiplication

Brief Announcement: Towards Fault-Tolerant Bin Packing for Online Cloud Resource Allocation

Brief Announcement: STAR (Space-Time Adaptive and Reductive) Algorithms for Dynamic Programming Recurrences with more than O(1) Dependency

Brief Announcement: Complete Visibility for Oblivious Robots in Linear Time

Brief Announcement: Extending Transactional Memory with Atomic Deferral

Brief Announcement: Hardware Transactional Storage Class Memory

Brief Announcement: Efficient Best Response Computation for Strategic Network Formation under Attack

Content Provider	ACM Digital Library
Author	Neubert, Stefan Friedrich, Tobias Schumann, David Lenzner, Pascal Keßler, Christoph Ihde, Sven
Abstract	Inspired by real world examples, e.g. the Internet, researchers have introduced an abundance of strategic games to study natural phenomena in networks. Unfortunately, almost all of these games have the conceptual drawback of being computationally intractable, i.e. computing a best response strategy or checking if an equilibrium is reached is NP-hard. Thus, a main challenge in the field is to find tractable realistic network formation models. We address this challenge by establishing that the recently introduced model by Goyal et al.[WINE'16], which focuses on robust networks in the presence of a strong adversary, is a rare exception which is both realistic and computationally tractable. In particular, we sketch an efficient algorithm for computing a best response strategy, which implies that deciding whether the game has reached a Nash equilibrium can be done efficiently as well. Our algorithm essentially solves the problem of computing a minimal connection to a network which maximizes the reachability while hedging against severe attacks on the network infrastructure.
Starting Page	321
Ending Page	323
Page Count	3
File Format	PDF
ISBN	9781450345934
DOI	10.1145/3087556.3087594
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2017-07-24
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Network robustness Strategic network formation Network reachability Best response computation
Content Type	Text
Resource Type	Article

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

Efficient Best-Response Computation for Strategic Network Formation under Attack

Brief Announcement: The Small World of Curious Beings

Brief Announcement: Distributed Single-Source Reachability

An Interactive Attack Graph Cascade and Reachability Display (2007)

Brief announcement: improving social-network-based sybil-resilient node admission control

Brief announcement: an early-stopping protocol for computing aggregate functions in sensor networks ⋆.

Brief Announcement: Improving Social-Network-based Sybil-resilient Node Admission Control

Brief announcement: (more) efficient pruning of ad-hoc wireless networks.

Brief Announcement: Efficient Private Distributed Computation on Unbounded Input Streams?

Brief Announcement: Efficient Best Response Computation for Strategic Network Formation under Attack

Similar Documents

Efficient Best-Response Computation for Strategic Network Formation under Attack

Brief Announcement: The Small World of Curious Beings

Brief Announcement: Distributed Single-Source Reachability

An Interactive Attack Graph Cascade and Reachability Display (2007)

Brief announcement: improving social-network-based sybil-resilient node admission control

Brief announcement: an early-stopping protocol for computing aggregate functions in sensor networks ⋆.

Brief Announcement: Improving Social-Network-based Sybil-resilient Node Admission Control

Brief announcement: (more) efficient pruning of ad-hoc wireless networks.

Brief Announcement: Efficient Private Distributed Computation on Unbounded Input Streams?

Brief Announcement: Efficient Best Response Computation for Strategic Network Formation under Attack