Can almost everybody be almost happy?

DOI10.1145/2840728.2840731MaRDI QIDQ2800547zbMATH OpenOpenAlexFDO

Authors Yakov Babichenko, Aviad Rubinstein, Christos Papadimitriou

Publication date 15 April 2016

Published in Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2840728.2840731

zbMATH Keywords

Nash equilibriumhardness of approximationPCPPPAD

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Noncooperative games (91A10) 2-person games (91A05) Other game-theoretic models (91A40)

Recommendations

• Inapproximability of Nash equilibrium
• Inapproximability of Nash equilibrium
• scientific article; zbMATH DE number 6783488
• Settling the complexity of computing two-player Nash equilibria
• On the complexity of approximating a Nash equilibrium

Cited in

(7)

• Inapproximability of Nash equilibrium
• The strongish planted clique hypothesis and its consequences
• Inapproximability results for constrained approximate Nash equilibria
• Public Bayesian persuasion: being almost optimal and almost persuasive
• Detecting communities is hard (and counting them is even harder)
• On the complexity of computing sparse equilibria and lower bounds for no-regret learning in games
• scientific article; zbMATH DE number 5375166 (Why is no real title available?)

This page was built for publication: Can almost everybody be almost happy?

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