Beyond Bayesian Nash Learning Minimax-Regret Equilibria for Adversarial Team Games under Asymmetric Information

Jul 16, 2026

Upload by Noah

Adversarial team games with asymmetric information require strategies robust to hidden opponent types and to deception. Strategic distribution shifts model deception as changes in the type distribution so an omniscient opponent can collude with Nature and condition actions on the observed type. Risk-neutral Bayesian Nash equilibrium can fail under such shifts, while distributionally robust methods offer limited guarantees. Probabilistically Robust Minimax-Regret Equilibrium (PR-MRE) minimizes worst-case regret on a high-confidence subset, combining robustness with nominal probabilistic information. For normal-form Bayesian games, PR-MRE becomes a robust bilinear program with a tractable semidefinite relaxation, enabling PRMRE-PSRO meta-solving and deep RL population learning. Experiments on graph-structured adversarial team games show improved worst-case performance across hidden types under strategic shifts.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages29

Reading Time1 h 13 min

Introduction

Adversarial team games and asymmetric information

Bayesian Nash equilibrium and robustness limits

Strategic distribution shifts and deception

Motivating example: graph capture-the-flag

Proposed approach: PR-MRE

arXiv :2607 .09993v 1 [ cs .GT] 10 Jul 2026 Beyond Bayesian Nash: Learning Minimax-Regret Equilibria for Adversarial Team Games under Asymmetric Information Naman Aggarwal [namanagg@mit. edu](namanagg@mit. edu) Aerospace Control Laboratory Laboratory of Information and Decision Systems Massachusetts Institute of Technology Jonathan P. How [jhow@mit. edu](jhow@mit. edu) Aerospace Control Laboratory Laboratory of Information and Decision Systems Massachusetts Institute of Technology Abstract Adversarial team games (ATGs) with asymmetric information, such as adversarial pathfinding, goal search, and reachability games on graphs, require strategies that are robust to hidden opponent types, such as a hidden goal flag, and to deception. Under asymmetric information, deception is seen as strategic shifts in the type distribution such that the omniscient opponent can collude with Nature and condition its play on the observed type. Existing risk-neutral solution concepts, such as Bayesian Nash equilibrium (BNE), are sensitive to distribution shifts, while distributionally robust approaches provide guarantees only within a prescribed ambiguity set. To address these limitations, we introduce Probabilistically Robust Minimax-Regret Equilibrium (PR-MRE), a novel equilibrium concept that combines the distribution-free robustness of minimax-regret reasoning with probabilistic information from a nominal type distribution. PR-MRE minimizes worst-case regret over a high-confidence subset of the type space, providing protection against strategic redistribution of probability mass while avoiding the conservatism of fully distribution-free approaches. We show that, for normal-form Bayesian games, PR-MRE can be formulated as a robust bilinear program and derive a tractable semidefinite relaxation. We then adapt this relaxation into a novel meta-solver within a robust double-oracle framework, PRMRE-PSRO, enabling population-based learning of approximate PR-MRE strategies via deep reinforcement learning best responses. Experiments on graph-structured adversarial team games demonstrate that PR-MRE discovers strategies with substantially improved worst-case performance across hidden types compared to risk-neutral equilibrium solutions, resulting in more robust behavior under strategic distribution shifts. 1 Introduction Computation of equilibria in large imperfect-information games has been a central driver of recent advancesin artificial intelligence. A key challenge in such settings is determining how strategic agents should reason about uncertainty. Existing equilibrium concepts differ fundamentally in their treatment of risk and robustness, ranging from risk-neutral formulations that optimize expected performance to risk-averse approaches that guard against uncertainty through worst-case reasoning. These differing notions of rationality lead to markedly different behaviors and robustness guarantees. Consequently, the literature on equilibria and equilibrium refinements for imperfect-information games is extensive (see Table 1 for an overview) . In Bayesian games, a Nature player moves before play begins and assigns each player a type drawn from a joint type distribution. Harsanyi’s seminal framework Harsanyi (1967; 1968) models strategic interactions withincomplete information by introducing the Bayesian Nash Equilibrium (BNE), in which each player maximizes expected utility under the common prior distribution over types. While BNE provides a principled Figure 1: Graph-Structured Capture-the-Flag (Graph CtF) with Blue Team’s Imperfect Information about the Red Flag Location: 2v2 CtF on a graph topology with Flag Uncertainty for Blue Team seen as two potential Red Flag locations. Limited Knowledge: Graph assumed known, but limited flag visibility (orange (yellow) indicates nodes on Left (Right) Flag are visible) . Asymmetric: Blue agents cannot distinguish between Red flag locations at other nodes, whereas Red agents have

FAQs

What problem does PR-MRE address compared with Bayesian Nash equilibrium in asymmetric-information adversarial team games?

PR-MRE addresses the sensitivity of Bayesian Nash equilibrium to strategic distribution shifts in hidden opponent types. It targets improved protection by minimizing worst-case regret over a high-confidence subset instead of optimizing expected utility under a fixed common prior.

How is deception modeled as strategic distribution shifts in the paper?

Deception is modeled as strategic changes to the type distribution, allowing an omniscient opponent to collude with Nature and condition its actions on the realized observed type. This can invalidate assumptions behind risk-neutral solution concepts.

How do PRMRE-PSRO and deep reinforcement learning contribute to learning PR-MRE strategies?

The paper derives a tractable semidefinite relaxation for PR-MRE and integrates it into a robust double-oracle meta-solver called PRMRE-PSRO. It then uses population-based learning with deep reinforcement learning best responses to compute approximate PR-MRE strategies.

Jul 16, 2026

Upload by Noah