Cover Image

Tight Inapproximability of Nash Equilibria in Public Goods Games

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Dinh, Jérémi Do, Hollender, Alexandros
Format:	Preprint
Published:	2024
Subjects:	Computer Science and Game Theory Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Pure-Circuit: Tight Inapproximability for PPAD
by: Deligkas, Argyrios, et al.
Published: (2022)

Constant Inapproximability for PPA
by: Deligkas, Argyrios, et al.
Published: (2022)

Constant Inapproximability for Fisher Markets
by: Deligkas, Argyrios, et al.
Published: (2026)

The Complexity of Symmetric Bimatrix Games with Common Payoffs
by: Ghosh, Abheek, et al.
Published: (2024)

On the Computation of Equilibria in Discrete First-Price Auctions
by: Filos-Ratsikas, Aris, et al.
Published: (2024)

Constant Inapproximability of Pacing Equilibria in Second-Price Auctions
by: Chen, Xi, et al.
Published: (2025)

Envy-Free Cake-Cutting for Four Agents
by: Hollender, Alexandros, et al.
Published: (2023)

Can Almost Everybody be Almost Happy? PCP for PPAD and the Inapproximability of Nash
by: Babichenko, Yakov, et al.
Published: (2015)

On the Complexity of Stationary Nash Equilibria in Discounted Perfect Information Stochastic Games
by: Hansen, Kristoffer Arnsfelt, et al.
Published: (2025)

On the Complexity of Learning Nash Equilibria
by: Biggar, Oliver, et al.
Published: (2026)

Fisher Markets with Approximately Optimal Bundles and the Need for a PCP Theorem for PPAD
by: Deligkas, Argyrios, et al.
Published: (2026)

Equilibrium Computation in First-Price Auctions with Correlated Priors
by: Filos-Ratsikas, Aris, et al.
Published: (2025)

Algorithms and Complexity for Computing Nash Equilibria in Adversarial Team Games
by: Anagnostides, Ioannis, et al.
Published: (2023)

Efficiently Computing Equilibria in Budget-Aggregation Games
by: Becker, Patrick, et al.
Published: (2025)

Tight Inapproximability for Welfare-Maximizing Autobidding Equilibria
by: Anagnostides, Ioannis, et al.
Published: (2026)

The Complexity of Symmetric Equilibria in Min-Max Optimization and Team Zero-Sum Games
by: Anagnostides, Ioannis, et al.
Published: (2025)

Computing Equilibrium Points of Electrostatic Potentials
by: Ghosh, Abheek, et al.
Published: (2025)

Efficient Equilibrium Computation in Symmetric First-Price Auctions
by: Filos-Ratsikas, Aris, et al.
Published: (2026)

Hardness of Approximate Hylland-Zeckhauser Equilibria
by: Braverman, Mark, et al.
Published: (2026)

A Smoothed FPTAS for Equilibria in Congestion Games
by: Giannakopoulos, Yiannis
Published: (2023)

Reducing the complexity of computing the values of a Nash equilibrium
by: Chatterjee, Debtoru, et al.
Published: (2025)

On the Complexity of the Optimal Correlated Equilibria in Extensive-Form Games
by: Cheval, Vincent, et al.
Published: (2025)

Robust Stackelberg Equilibria
by: Gan, Jiarui, et al.
Published: (2023)

Reforming an Unfair Allocation by Exchanging Goods
by: Yuen, Sheung Man, et al.
Published: (2024)

How to Resolve Envy by Adding Goods
by: Bentert, Matthias, et al.
Published: (2025)

Min-Max Optimization Requires Exponentially Many Queries
by: Bernasconi, Martino, et al.
Published: (2026)

The Complexity of Two-Team Polymatrix Games with Independent Adversaries
by: Hollender, Alexandros, et al.
Published: (2024)

On Binary Networked Public Goods Game with Altruism
by: Maiti, Arnab, et al.
Published: (2022)

Nash Equilibria in Reverse Temporal Voronoi Games
by: Pawlowski, Simeon, et al.
Published: (2024)

On the Uniqueness of Nash Equilibria in Multiagent Matrix Games
by: Bailey, James P.
Published: (2024)

The Complexity of Pure Strategy Relevant Equilibria in Concurrent Games
by: Bhaduri, Purandar
Published: (2025)

Modelling Network Resilience: The Complexity of Some Graph Division Games
by: Gutowski, Grzegorz, et al.
Published: (2026)

Near-Optimal Quantum Algorithms for Computing (Coarse) Correlated Equilibria of General-Sum Games
by: Li, Tongyang, et al.
Published: (2025)

Solving Four Open Problems about Core Stability in Altruistic Hedonic Games
by: Rothe, Jörg, et al.
Published: (2025)

Computing Nash Equilibria in Potential Games with Private Uncoupled Constraints
by: Patris, Nikolas, et al.
Published: (2024)

Arena-Independent Memory Bounds for Nash Equilibria in Reachability Games
by: Main, James C. A.
Published: (2023)

Control by Adding Players to Change or Maintain the Shapley-Shubik or the Penrose-Banzhaf Power Index in Weighted Voting Games Is Complete for NP^PP
by: Kaczmarek, Joanna, et al.
Published: (2024)

ε-Stationary Nash Equilibria in Multi-player Stochastic Graph Games
by: Asadi, Ali, et al.
Published: (2025)

Choosing What Game to Play without Selecting Equilibria: Inferring Safe (Pareto) Improvements in Binary Constraint Structures
by: Oesterheld, Caspar, et al.
Published: (2025)

Dynamic Allocation of Public Goods with Approximate Core Equilibria
by: Onyeze, Chido, et al.
Published: (2025)