A Simple Algorithm Breaking the 1/3 Barrier for Approximate Nash Equilibria in Bimatrix Games

概要

The PPAD-completeness of computing Nash equilibria in bimatrix games has driven extensive research into polynomial-time algorithms for $ε$-approximate Nash equilibria. Determining the strongest approximation guarantee achievable in polynomial time is a fundamental question in the complexity of approximate Nash equilibria. Despite sustained efforts, breaking the $1/3$ barrier has long been regarded as a difficult open problem. In this paper, we give an affirmative answer by proposing a simple, symmetric deterministic polynomial-time algorithm that has no tunable hyperparameters and achieves an approximation guarantee of approximately $0.30954+δ$. The main idea is to enrich the optimization framework of Tsaknakis and Spirakis with building blocks drawn from our work on strategy mixing and automated approximation analysis, yielding a new algorithmic structure that provides a conceptual explanation for the improved guarantee.

参考リンク

• Paper ↗

リンク先のライセンス・再現性・データ条件をご確認ください。自動分類や実装の目安は保証ではありません。

実装を始めるプロンプト

参考リンクを確認したうえで、次の内容をコピーして利用できます。

# 論文・記事
A Simple Algorithm Breaking the 1/3 Barrier for Approximate Nash Equilibria in Bimatrix Games

# 概要
The PPAD-completeness of computing Nash equilibria in bimatrix games has driven extensive research into polynomial-time algorithms for $ε$-approximate Nash equilibria. Determining the strongest…

# 原典
https://arxiv.org/abs/2610.05317

上記の手法を実装してください。実行前に依存関係とライセンスを確認してください。