Tight inapproximability of Nash equilibria in public goods games

DOI10.1016/J.IPL.2024.106486MaRDI QIDQ6551709zbMATH OpenFDO

Authors Jérémi Do Dinh, Alexandros Hollender

Publication date 7 June 2024

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.IPL.2024.106486

zbMATH Keywords

computational complexitygame theoryNash equilibriumPPADpublic good

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Applications of game theory (91A80) Public goods (91B18)

Recommendations

• Public goods games in directed networks
• Inapproximability of Nash equilibrium
• Inapproximability of Nash equilibrium
• Complexity of public goods games on graphs

Cites work

• Best-response dynamics in directed network games
• Complexity of public goods games on graphs
• Inapproximability of Nash equilibrium
• Network games
• On the Complexity of Nash Equilibria and Other Fixed Points
• On the private provision of public goods on networks
• Public goods games in directed networks
• Public goods in directed networks
• Public goods in networks
• Settling the complexity of computing two-player Nash equilibria

Cited in

(1)

• Clearing financial networks with derivatives: from intractability to algorithms

This page was built for publication: Tight inapproximability of Nash equilibria in public goods games

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