On parameterized complexity of binary networked public goods game

DOI10.1007/S00453-023-01174-4arXiv2012.01880OpenAlexW3106803449MaRDI QIDQ6185945FDOQ6185945

Authors: Arnab Maiti, Palash Dey 

Publication date: 9 January 2024

Published in: Algorithmica (Search for Journal in Brave)

Abstract: In the Binary Networked Public Goods game, every player needs to decide if she participates in a public project whose utility is shared equally by the community. We study the problem of deciding if there exists a pure strategy Nash equilibrium (PSNE) in such games. The problem is already known to be NP-complete. We provide fine-grained analysis of this problem under the lens of parameterized complexity theory. We consider various natural graph parameters and show either W[1]-hardness or exhibit an FPT algorithm. We finally exhibit some special graph classes, for example path, cycle, bi-clique, complete graph, etc., which always have a PSNE if the utility function of the players are fully homogeneous.

Full work available at URL: https://arxiv.org/abs/2012.01880

zbMATH Keywords

parameterized complexitybinary networked public goods gamepure staretgy Nash equilibrium

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites Work

• Tractable cases of the extended global cardinality constraint
• Network games
• The complexity of computing a Nash equilibrium
• Parameterized algorithms
• Title not available (Why is that?)
• Public goods in networks
• Cascading behavior in networks: algorithmic and economic issues
• Graphical games
• Contagion
• Incentive-based search for efficient equilibria of the public goods game
• On the power of tree-depth for fully polynomial FPT algorithms

This page was built for publication: On parameterized complexity of binary networked public goods game

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6185945)