On parameterized complexity of binary networked public goods game

DOI10.1007/S00453-023-01174-4MaRDI QIDQ6185945zbMATH OpenOpenAlexFDO

Authors Arnab Maiti, Palash Dey

Publication date 9 January 2024

Published in Algorithmica (Search for Journal in Brave)

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)

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.

Cites work

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

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)