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/

Global: Zendy Tools annual

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

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We study the problem of finding optimal correlated equilibria of varioussorts: normal-form coarse correlated equilibrium (NFCCE), extensive-form coarsecorrelated equilibrium (EFCCE), and extensive-form correlated equilibrium(EFCE). This is NP-hard in the general case and has been studied in specialcases, most notably triangle-free games, which include all two-player gameswith public chance moves. However, the general case is not well understood, andalgorithms usually scale poorly. First, we introduce the correlation DAG, arepresentation of the space of correlated strategies whose size is dependent onthe specific solution concept. It extends the team belief DAG of Zhang et al.to general-sum games. For each of the three solution concepts, its size dependsexponentially only on a parameter related to the game's information structure.We also prove a fundamental complexity gap: while our size bounds for NFCCE aresimilar to those achieved in the case of team games by Zhang et al., this isimpossible to achieve for the other two concepts under standard complexityassumptions. Second, we propose a two-sided column generation approach tocompute optimal correlated strategies. Our algorithm improves upon theone-sided approach of Farina et al. by means of a new decomposition ofcorrelated strategies which allows players to re-optimize their sequence-formstrategies with respect to correlation plans which were previously added to thesupport. Our techniques outperform the prior state of the art for computingoptimal general-sum correlated equilibria. For team games, the two-sided columngeneration approach vastly outperforms standard column generation approaches,making it the state of the art algorithm when the parameter is large. Along theway we also introduce two new benchmark games: a trick-taking game thatemulates the endgame phase of the card game bridge, and a ride-sharing game.

Optimal Correlated Equilibria in General-Sum Extensive-Form Games: Fixed-Parameter Algorithms, Hardness, and Two-Sided Column-Generation