Fast, Optimal AI Techniques for Game-Theoretic Team Coordination and Extensive-Form Correlation
Abstract
Most of the computational game theory literature has focused on independent agents that seek to maximize their own utility. Yet many realistic interactions require studying correlated strategies. As examples, consider a team of military actors (units) in a communications-denied environment, or players playing bridge or colluding at a poker table. The optimal strategy for the team is to coordinate their moves, and as a result the colluding players will not play according to independent strategies. The study of properties of correlated strategies in tree-form imperfect-information strategic interactions (that is, games with sequential and potentially also simultaneous moves) is a fundamental problem that has far-reaching implications but is yet to be well understood. In 2008, von Stengel and Forges showed that the set of correlated strategies in two-player games without chance moves can be characterized with a polynomial-sized system of linear consistency constraints, leading to polynomial-time solvability. We extended their results by proving the same property for a broader game classÑtriangle-free gamesÑwhich includes all two-player games with public chance moves. Positive results and progress around the representation of correlation benefit all applications that model a strategic interaction in the presence of correlated strategies, including the problem of finding provably optimal team coordination and optimal (e.g., social-welfare-maximizing) correlated plans for agents for all three game-theoretic solution concepts for correlated plans in tree-form games: normal-form coarse correlated equilibrium, extensive-form coarse correlated equilibrium, and extensive-form correlated equilibrium. I propose research on characterizing correlation in extensive-form, imperfect-information games and on significantly increasing the scalability of algorithms for making such plans. The proposed work will have the following four main prongs. 1. I propose developing generalizations of triangle freeness that expand the class of games for which optimal team coordination and the optimal correlated solutions can be found in worst-case polynomial time. I also propose to study conditions under which multi-player coordination can be described with a polynomial number of constraints. 2. For games where a polynomial-sized constraint system is not enough to capture all correlated strategies, we recently developed a more general representation that uses an exponential number of constraints, where the exponent is a parameter that measures the amount of asymmetric information the correlating players observe. Our approach generates a new kind of tree decomposition of the distribution of moves of the correlating agents into interdependent coordination subproblems according to different scenarios that the agents might encounter. I propose to generalize this beyond teams to optimal correlated equilibria. We will also cross-fertilize this with triangle-freeness, and the generalizations thereof proposed above, to develop better ordering techniques for tree decomposition that achieve the best of both worlds. 3. To further increase scalability of our techniques, we will develop an incremental algorithms for the decomposition approach. 4. I will leverage a new representation of game tree, strategically equivalent to the original, though exponentially larger, but to which techniques from zero-sum games apply. I propose applying to a compact representation of the new tree the highly scalable techniques from non-correlated solution concepts: regret minimization, offline first-order methods, warm starting, dynamic pruning, abstraction algorithms, subgame solving, and certificate finding. The work will involve algorithm design, proving properties of representations and algorithms, algorithm implementation, and extensive computational experiments on standard benchmark games as well as larger variants thereof as the algorithms become increasingly scalable.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Oct 12, 2022
- Source ID
- W911NF2210266
Entities
People
- Tuomas Sandholm
Organizations
- Army Contracting Command
- Carnegie Mellon University
- United States Army