Inapproximability Results for Approximate Nash Equilibria

详细信息    查看全文

• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：10123
• 期：1
• 页码：29-43
• 丛书名：Web and Internet Economics
• ISBN：978-3-662-54110-4
• 卷排序：10123

文摘

We study the problem of finding approximate Nash equilibria that satisfy certain conditions, such as providing good social welfare. In particular, we study the problem \(\epsilon \)-NE \(\delta \)-SW: find an \(\epsilon \)-approximate Nash equilibrium (\(\epsilon \)-NE) that is within \(\delta \) of the best social welfare achievable by an \(\epsilon \)-NE. Our main result is that, if the randomized exponential-time hypothesis (RETH) is true, then solving \(\left( \frac{1}{8} - \mathrm {O}(\delta )\right) \)-NE \(\mathrm {O}(\delta )\)-SW for an \(n\times n\) bimatrix game requires \(n^{\mathrm {\widetilde{\Omega }}(\delta ^{\varLambda } \log n)}\) time, where \(\varLambda \) is a constant.