Reproduce “Computational Results for Extensive-Form Adversarial Team Games” on OpenResearch

Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.

Universal app for Apple silicon and Intel. Requires macOS 11 or later.

About this paper

Andrea Celli, Nicola Gatti

This research provides the first computational study of extensive-form adversarial team games, analyzing how different levels of communication within a team affect strategic outcomes and computational complexity. The authors present algorithms for finding optimal strategies under various communication scenarios, demonstrating that full communication enables polynomial-time solutions while limited communication leads to FNP-hard problems, though empirical results suggest practical inefficiency from limited communication is often small.

Key insights

  • Full team communication (TMECom) allows for polynomial-time computation of optimal strategies, making it the most tractable scenario.
  • Limited or no team communication (TMECor, TME) leads to FNP-hard computational problems, with TME being inapproximable in an additive sense.
  • While theoretical bounds show inefficiency from limited communication can be arbitrarily large, empirical results on random games indicate this inefficiency is often very small in practice.

Summary by alphaXiv.

Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.