English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

Since the seminal PPAD-completeness result for computing a Nash equilibriumeven in two-player games, an important line of research has focused onrelaxations achievable in polynomial time. In this paper, we consider thenotion of $\varepsilon$-well-supported Nash equilibrium, where $\varepsilon \in[0,1]$ corresponds to the approximation guarantee. Put simply, in an$\varepsilon$-well-supported equilibrium, every player chooses with positiveprobability actions that are within $\varepsilon$ of the maximum achievablepayoff, against the other player's strategy. Ever since the initialapproximation guarantee of 2/3 for well-supported equilibria, which wasestablished more than a decade ago, the progress on this problem has beenextremely slow and incremental. Notably, the small improvements to 0.6608, andfinally to 0.6528, were achieved by algorithms of growing complexity. Our mainresult is a simple and intuitive algorithm, that improves the approximationguarantee to 1/2. Our algorithm is based on linear programming and inparticular on exploiting suitably defined zero-sum games that arise from thepayoff matrices of the two players. As a byproduct, we show how to achieve thesame approximation guarantee in a query-efficient way.

A Polynomial-Time Algorithm for 1/2-Well-Supported Nash Equilibria in Bimatrix Games