Subgame Solving in Adversarial Team Games
Authors: Brian Hu Zhang
Luca Carminati
Federico Cacciamani
Gabriele Farina
Pierriccardo Olivieri
Nicola Gatti
Tuomas Sandholm
Venue: NeurIPS 2022 Accept (2022)

Abstract: In adversarial team games, a team of players sequentially faces a team of adversaries. These games are the simplest setting with multiple players where cooperation and competition coexist, and it is known that the information asymmetry among the team members makes equilibrium approximation computationally hard. Although much effort has been spent designing scalable algorithms, the problem of solving large game instances is open. In this paper, we extend the successful approach of solving huge two-*player* zero-sum games, where a blueprint strategy is computed offline by using an abstract version of the game and then it is refined online, that is, during a playthrough. In particular, to the best of our knowledge, our paper provides the first method for online strategy refinement via subgame solving in adversarial team games. Our method, based on the team belief DAG, generates a gadget game and then refine the blueprint strategy by using column-generation approaches in anytime fashion. If the blueprint is sparse, then our whole algorithm runs end-to-end in polynomial time given a best-response oracle; in particular, it avoids expanding the whole team belief DAG, which has exponential worst-case size. We apply our method to a standard test suite, and we empirically show the performance improvement of the strategies thanks to subgame solving.

Subgame Solving in Adversarial Team Games
Brian Hu Zhang*
Luca Carminati'
Computer Science Department Carnegie Mellon University bhzhang@cs. cmu edu
DEIB, Politecnico di Milano
luca. carminat@pol it
Federico Cacciamani
Gabriele Farina
DEIB, Politecnico di Milano federico. cacciaccccciaco @pol imi .it
Computer Science Department Carnegie Mellon University gf gfarina@cs. edu
Pierriccardo Olivieri DEIB, Politecnico di Milano
Nicola Gatti
DEIB, Politecnico di Milano nicola. gatti@polimi......mmm itt
pierriccardo. htt.:aaoo....i.....ooooo........
Tuomas Sandholm
Computer Science Department, CMU Strategic Machine, Inc. Strategy Robot, Inc.
Optimized Markets, Inc. sandholm@cs. cmu. edu
Abstract
In adversarial team games, team players sequentially faces a team of adver- saries. These games are the simplest setting with multiple players where coop- eration and competition coexist, and is known that the information asymmetry among the team members makes equilibrium approximation computationally hard. Although much effort has been spent designing scalable algorithms, the problem of solving large game instances is open. In this paper, extend the successful approach of solving huge two-player zero-sum games, where a blueprint strategy is computed offline by using abstract version of the game and then it is refined online, that is, during a playthrough. In particular, to the best our knowledge, our paper provides the first method for online strategy refinement via subgame solving in adversarial team games. Our method, based on the team belief DAG, generates gadget game and then refine the blueprint strategy by using colunn-generation approaches in anytime fashion. the blueprint is sparse, then our whole algorithm runs end-to-end in polynomial time given best-response oracle; in particular, it avoids expanding the whole team belief DAG, which has exponential worst-case size. We apply our method standard test suite, and empirically show the performance improvement of the strategies thanks to subgame solving.
Introduction
Sequential strategic games with multiple players where cooperation and competition coexist fascinating problems receiving increasing interest in the scientific literature. The simplest case
"cqual contribution; author order randomized
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

is represented by adversarial team games (ATGs) [19], where a team of players faces team of adversaries. This setting extends the basic zero-sum two-player setting, introducing the problem of coordinating team members with asymmetric and partial information. A common approach is that of ex ante coordination introduced in [7], in which the players can coordinate their strategies beforehand, but they have no means of communication during the gameplay. Many recreational and real- world scenarios can be modeled according to this framework, such as, e.g., contract bridge, collusion in Poker, and sequential security games. While ante coordination makes the optimization problem convex, the problem of finding an equilibrium is inapproximable in polynomial time [7], and many efforts have been spent to design algorithms scaling up to non-toy instances.
Related works. The mainstream literature on ATGs, e.g. [7, 8, 9, 23], focuses on n-vs.-/ scenarios and resorts to column-generatin generation (CG) algorithms to solve small/medium -ized instances exploiting the existence of equilibria with small support. These algorithms iterate between the problem of finding an equilibrium with a restricted set of strategies (the meta-problem) and the problem of enlarging such set by finding the players' best responses. A crucial issue concerns the design of practical representations for the team's strategy space, which in the worst case is exponential in the size of the instance. In particular, a junction-tree-base decomposition is proposed in [20], while the team is represented through an explicit coordinator prescribing actions to team members in [5. 6]. The team belief DAG (TB-DAG) representation proposed in [22] bridges the previous two representations [5, 6, 20]. TB-DAG consists of directed acyclic graph representation of the team strategy space, and it captures the players' beliefs over the game nodes given the joint strategy computed beforchand and the information observed publicly by the team players. A central concept in TB-DAG is team belief (or team-public state), which is a combination of the team players' information sets with the same public information. The size of TB-DAG is exponential in the number of information sets of each team-public state, and this number is called information complexity [22]. Counterfactual regret minimization (CFR) [24] and CG algorithms [14] applied to TB-DAG are the current state of the art to solve ATGs [21, 22]. Empirically, CFR outperforms CG when the information complexity is low, while CG outperforms CFR otherwise. However, despite the efforts to enhance representations and algorithms, solving medium big sized games is not currently affordable due to infeasible memory requirements for CFR and iterations requirements for CG [21].
The problem of scaling up to huge games in the two-player zero-sum setting has been successfully addressed by refining strategies online by subgame solving [1, 3, 4, 17]. This approach led to, e.g., superhuman performances in poker [2, 16]. However, these techniques cannot be directly applied to ATGs due to some open non-trivial technical questions, such as, e.g., how to generate the gadget game for the refinement, how to compute the counterfactual reach and best response value.
Original contributions. To the best of our knowledge, this paper provides the first method for refining strategies by subgame solving in ATGs. In particular, we generate a blueprint strategy by running a CG algorithm with time limit. This procedure results in blueprint whose support has size linear in the number of iterations of the CG algorithm. We conveniently represent the blueprint by TB-DAG, while we take inspiration from maxmargin to design our algorithm to refine the blueprint strategy during the gameplay [15]. In particular, the gadget game is generated from the subgame of the TB-DAG played by strictly positive probability in the blueprint rooted in the players' public state in which the players are playing. Then, the CG algorithm is applied to the gadget subgame to refine the blueprint strategy with a time limit depending on the application. Here, the CG algorithm iteratively expands the gadget game by adding a new best response at any iteration.
By using CG for both the blueprint and the subgame solving procedures, the strategy is guaranteed to remain sparse. More precisely, the size of the representation of the strategy will grow only linearly in the number of best-respons, oracle (BRO) calls and polynomially in the size of the game. Hence, our algorithm is time- and space-efficient modulo the BRO, and in particular it does not need to expand the whole TB-DAG, which has worst-case exponential size. We hope that, in the future, this property will allow scaling to huge games.
The experimental evaluation of our method with a standard test suit shows that they dramatically reduce the gap between the values provided by the equilibrium strategy and the blueprint. In particular, the average reduction is of about 39% when the time limit used for the strategy refinement after every single move in the game equals the time needed by the CG algorithm to complete even a single iteration at the root of the game, and allotting more iterations further improves performance. Such an
2

---

empirical result shows that a local reoptimization can effectively lead to strategies whose value is close to the equilibrium value in ATGs.
2 Preliminaries
2.1 Adversarial team games
two-team extensive-form adversarial team game (ATG) I, between teams and v, consists of:
a directed tree of histories, or nodes, H. whose edges are labeled with actions. The set of actions available at node h E H is denoted with A(h), while the root of H is denoted with Ø. Leaves of the tree are called terminal nodes, and their set is denoted with Z. Given two nodes h, h' H. we write h 3 h there exists a path in the tree going from h to h', and h < 11' if < h and h + R';
a partition H. \ 2 = HN L H. U of the set of nonterminal nodes determining who plays at each node: nature (N)-also called chance-, the max-team (A), or the min-team (V). Given a team E ( }. the opponent denoted with -i, and we let H-; = H H.:
for each team E {A, }. partition Ij of Hi into information sets. In each information set I E Ii every node in must have the same action set, denoted as A(T);
a utility function u E IR where u[2] the utility for for reaching terminal node 2. Since the interaction between the teams is zero-sum, we let "s utility be -u[z];
for each nature node h E HN. a distribution p(-[h) over the children of h. We will use p[h] to denote the probability that nature plays all actions on the 2 h path.
Since each i E (A, } is a team of players with potentially asymmetric information, we will not demand that the meta players, each representing whole team, have perfect recall. However, for most of the paper, we will be interested in the special case where consists of just one player-that is, has perfect recall, but may not. In this paper, will have need whatsoever differentiate between the players on the same team-rathed we will take the perspective of the team as a whole. Equivalently, this whole paper can be formulated in terms of two-player games of imperfect recall.
We will assume timeability- is, no information set spans multiple levels of the tree [10]. Intu- itively, this means that there is a turn clock in the game that is common knowledge to all players.
pure strategy for team is selection of one action for each information / I,. The realization form x of a pure strategy is the vector x E _² where x|æ] = if and only if the team plays every action on the path z. A correlated strategy is a probability distribution over pure strategies, and its realization form is the appropriate convex combination. By taking arbitrary probability distributions over pure strategies, the individual players of a team can correlate their strategy with shared randomness hidden from the opposing team. The best response of a team i is one of its strategies maximizing its expected utility given a fixed strategy of the opponent team -i.
The central solution concept in ATGS is the -aaa-Maammnn Equilibrium with correlation (TMFcor), introduced in [7]. A TMEcor is a pair of correlated strategies, one per team, such that each team's correlated strategy is a best response to the opponent's.
2.2 Public information and the team belief DAG
We call piece of information public if it is common knowledge to all players. Formally, two nodes h, h in the same level of the tree are indistinguishable to team if there is some information set I E I, that connects descendant of l to descendant of h'. A public state is connected component of the graph induced by the indistinguishability relation of both teams. A team-public state for team i is a connected component of the graph given by the indistinguishabiiiy relation of that team alone.
Zhang al. [22] introduce the team belief DAG (TB-DAG), a representation of the decision problem faced by the team in a team game. For team i, the nodes S, of the TB-DAG are partitioned in a set of observation nodes O,, i.e., nodes which the team observes information concerning the state the game and a set of decision disambiguate the notation, the sets of beliefs for teams a and are denoted with B and C, respectively. Intuitively, both beliefs and observation nodes identify a subset of H. that is indistinguishable to
chins--called beliefs-i.e. nodes in which the team performs actions. To
3

---

the team, based on the common information they have. In what follows, we introduce the structure and basic notation of Ass TB-DAG representation. The representation of vs TB-DAG is defined identically. The DAG is constructed recursively, starting from a root decision node that contains only the root node Ø of the ATG and alternating decision and observation nodes along every possible path. More in detail, each edge leaving a belief B corresponds to a so-called prescription, i.e., tuple that assigns an action to each infoset that has a nonempty intersection with B. Formally, the set of possible prescriptions at a belief B is defined as A(B) {a a A(1j) ]. where, for any infoset I E I and belief B B, we write 1 ~ / + Ø. Following prescription a at a belief B E B, the TB-DAG transitions to the observation node are identified by
Ba =
U E a,Ea
(hay | h 1 BJ U {ha e BnH E A(h)) E EO..
A belief B E B is said to be terminal if it contains terminal nodes of the ATG. Finally, the set of possible observations that team can obtain from an observation node O E O₂ coincides with the set of A's public states with nonempty intersection with O. Following the observation of team public state P at observation node O, the DAG transitions to the decision node identified by O Dnz P. Let us remark that this construction ensures that each belief is subset of single nam-public state. We denote A 's public state associated with belief B E B as P(B), while the set of beliefs in public state denoted as B P) {B] B E B A E P]. Given public state P and a belief B, we say B 3 P if for any h E B there exists h' E P such that h N h'.
For TB-DAG, the strategy representation that we rely on is the TB-DAG form, that yields a strategy representation equivalent, yet more compact, to the set of correlated strategies. Given pure strategy
for team A, the associated TB-DAG form is vector æ E {0, 1 such that [B]] = 1 if and only if the pure strategy prescribes to play all the actions from 2 to all the nodes h E B and no B' 5 B satisfying such property exists. Furthermore, for each observation node Ba E O æ =[Ba] 1 if and only if x B and the pure strategy prescribes to play all the actions 0j E a with probability 1. The TB-DAG form of a correlated strategy obtained by taking the appropriate convex combination of pure strategies' TB-DAG forms. The polytopes of TB-DAG-form strategies for team A and are denoted as X' and Y respectively. Throughout this work, will be useful to consider the restriction of X' and y on the set of decision and observation nodes following a public state P. We denote such sets as X' and J/p. Formally, the set X'p is defined by the following linear constraints:
z
[B]
Σ
x: [Ba]
for non-terminal B z P
A(B)
x
B
Σ B
x BBa
for B' > P.
The set DiP is defined similarly. Note that in the definition of X'p and Yp the strategy values at initial beliefs P are unconstrained. Additional constraints can be introduced by the subgame solving algorithm used and will be discussed in Section 3.
The TB-DAG has worst-case exponential size, and therefore algorithms that build it fully cannot scale past a certain point. The crucial property we will need for this paper, though, is that pure strategics have sparse representations in the TB-DAG. In particular, every pure strategy plays to at most one belief in each team-pul ceam-public state.
3
Subgame solving for adversarial team games: Team-Maxmargin
3.1 Maxmargin
The maxmargin algorithm [15] is used in two-player zero-sum games in extensive form for online refinement of blueprint strategy² for the game. In particular, for every public state P reached by the players during the playthrough, maxmargin considers fixed the blueprint strategy in the trunk (i.e., the part of the game leading to P), optimizing the player's 's strategy exclusively in the subgame rooted at P. Its main objective, roughly speaking, is to compute the strategy giving the largest decrease in
AA blueprint strategy is a suboptimal strategy for the whole game being computed on an abstracted, smaller version of the game.

---

exploitability when merged with the trunk one. For the sake of presentation, from here on, we refer as the team player whose strategy is be refined, and as the opponent. Furthermore, in this section, team player is composed of single member.
The maxmargin algorithm works with auxiliary game called the gadget game. The gadget game is obtained by adding additional nodes to the top of the subgame starting at P. The root of the gadget game is a newly-added -node where the available moves-called deviations-allow him choose an infoset among those belonging to P. Therefore, V can adversarially decide from which of his own infosets the subgame will restart. Each of those actions leads to a chance node, where chance chooses specific history in the infoset chosen by the opponent, based on chance reach probabilities and on the trunk blueprint strategy for A. Once a history has been selected by chance, the following part of the gadget game is the same as the original subgame up to the terminal nodes. Furthermore, the payoff's associated to each terminal node following a specific initial choice of infoset by the opponent are decreased by the counterfactual best response value at that infoset. This value is the best response value of conditioned on the game reaching that specific infoset, assuming that blueprint. The change of the payoff's induces to restart the gadget game in the infoset in which the current strategy the refining player is most exploitable. Fully solving the gadget game guarantees safety: if maxmargin subgame sol solving is applied during playthrough, then the resulting strategy is at most as exploitable as the blueprint.
playing the
The crucial issue when applying the maxmargin algorithm to an ATG is that the TB-DAG allows the same history to be reached through multiple beliefs, phenomenon unique to team games. In particular, this issue will mean that it is difficult to formulate team subgame solving in terms of gadget game the same way as is done in the standard two-player case. While this issue could be trivially solved by unrolling the TB-DAG into an extensive-form game [5, 6], such an unrolling is inefficient as it would require an amount of extra space exponential in the original game size [5, 6, 22]. We will therefore formulate the gadget "game" directly in terms of a max-min optimization problem that does not immediately correspond to an EFG.
3.2 Team-maxmargin
We introduce the team- geam-maxmargin algorithm, which extends maxmargin subgame solving to ATGs. The algorithm that we present here can be applied to any ATG, without any constraint on the number of players in each team.
As aforementioned. in order to successfully apply subgame solving techniques to the TB-DAG representation of ATGs, there is the need to relate the TB-DAG-form polytopes of the two teams. To do so, we rebalance the reach of v's strategy depending on the fixed trunk strategy of and nature. The normalization factor that we use is denoted as counterfactual reach.
Definition 1 (Counterfactual reach). Let æ the strategy for team A. For each ''s belief C, the counterfactual reach plæ, C*) is the total nature and reach at C, defined as follows:
plax C| = Σ p(h] Σ x[B].
LEC
B3Λ
Counterfactual reach corresponds to the probability that A and nature play to reach a specific helief C In the definition above, the counterfactual reach
given that plays strategy y such that y|C] p|z, C] aggregates the realization probability of and p on the histories h E C so to effectively represent the behavior of nature and A in the polytope of the opponents.
The counterfactual reach allows us to determine which of v's beliefs are actually reachable given a's strategy. This set of nodes is denoted as the set of counterfactually reachable beliefs.
Definition 2 (Counterfactually reachable beliefs). The set of all counterfactually reachable belief' in a public state P is denoted with C|z, Pl. Formally:
Clr P] := (CICCCCCCCPPPPCC C|>
Another concept needed to extend maxmargin TB-DAGs is the one of counterfactual best response value at a v's n's belicf C', that is defined as the value of the best v prescription at C.
Definition 3 (Counterfactual best response value). Let xe the strategy for team A. For each decision node C, let u(æ CJ be the unnormalized counterfactual -best response value defined by
5

---

the recurrences as follows:
Σ x|2| [|]]
if C terminal
x., C7
ZEC
min aEA(C)
u(æ; Ca.
otherwise
ular, Cal
u(ar C*].
C'
whereas the normalized counterfactual v bbett response value at C against o can be defined as follows:
u|z, Ca] p x. C]
un ar, Ca)
Notice that, in the definition of the counterfactual best response value, the realization form induced by the TB-DAG form strategy and chance is taken into account. On the other hand, when considering the normalized counterfactual best response value, we condition to reaching a specific C. Hence, to remove the contribution to realizations due to actions that have been played in trunk, we divide by the counterfactual reach. Given the above definitions, we can now provide the optimization problem which the Team- Maxmargin algorithm needs to solve for the refinement of the strategy.
Definition (Team- maxamaagargiin linear program). The maxmargin optimization problem TB-DAG subgame rooted at P is formulated the following linear program:
max min
Σ
x
[2]
pl
u[2]
Σ
y|C] ufz C]
(1)
V.8
22P
CEC|a
s.t.
B' = x²
for all A-beliefs B E B|P)
(2)
yCC = g
for all -bblicfs E Clæ, P|
(3)
plae, C
x' Xp, y E Dp, y E C(
(4)
As in the original two-player formulation, can choose to deviate to any of the counterfactually reachable beliefs at the public state of the subgame by choosing y E C[,, Equation specifies the maximization of the margin, i.e., the difference between the expected value of the subgame and the value of the counterfactual best response to A's blueprint. This encodes the objective of a to find x maximize its value w.r.t. the blueprint for any adversarially chosen deviation of the opponent. Equation 2 fixes the trunk strategy of A. Equation rescales reach probabilities of the opponent according to the counterfactual reach p plax, C). This is equivalent to normalizing by the nature and A reach probabilities at C. Such a normalization is crucial because it accounts for the fixed reach probabilities in the trunk for chance and While it may seem more intuitive to normalize by the reach probabilities of A and chance directly on the terminal nodes, as is typically done in two-player zero-sum games, in team games it is actually necessary do so the beliefs in C(ar, P]. This a consequence of the fact that, when V is composed by more than one player, the reach of A and nature over terminal nodes depends directly on the deviation C' E Clæ P] chosen by v, and multiple such belief's C' can reach the same terminal node. This is a difficulty that only occurs in the ceam-vs-team setting. Note that only counterfactually reachable beliefs C(x,, P] of are considered in this constraint since they are the only potential deviations of the opponent in the gadget game. Equation encompasses all the TB-DAG constraints on the strategy spaces of and
One may expect that, in parallel to the two-player case, our maam-maxnargin optimization problem an ATG. However, the constraints that have introduced into the
may also be representable formulation go out of the scope of ATGs, so this is not directly possible. Despite this, the strategy spaces of both players in Definition 4 are DAGs, to which any technique for solving team games, such as CFR [24] or column generation, apply.
A complete construction procedure of the gadget DAG is provided in Appendix A. Furthermore, in Appendix B, we extend other subgame solving techniques (i.e., resolving [4] and reach [1]) to the team setting.
Safety of the refinement. The team maxmargin algorithm achieves the same safety guarantees as the maxmargin algorithm, for similar arguments to [15, 1]. Formally:

---

Algorithm Maxmargin subgame solving with column generation, at public state
1: Input:
2: sparse DAG-form blueprint 2:
3: reach probabilities p|æ,, C] and alt values u(æ C/ for all reachable v --beliefs C' E Clx, Pl
4: let B be the set of A-beliefs in P with x(B] O.
5: F²H, f- (GGNNAATTAAAITTRRRSSSTTTTTVV
for each B B
b forr each time t and belief B E B, F'g,: is pure strategy defined on the sub-DAG rooted B. It represents strategy that may take following belief B.
6: for iteration t 1,,.... do
7: solve the veeta-game::
min Σ
E
viClulæe, Cl
-
Ag
20 9-9
P
CECIP
s.t.
x. +
Σ
x: [
AB,
BEB
15rst
y|C] 5. p/a, Cl
for all -bblliefss C Clx,
Σ AB - X
for all A A-bliiefs B E B
15rst
As 2 0, A 2 0, A Er,, E (((m))
8: for each belief B E do
9: solve for best response given belief B:
BBB,11 <- argmax
Σ c'(sju(<lp(zjju(]
w'e R
22
(5)
s.t.
x' [ha] xr [h'] x d'' 21'))>(nn [ha]
Vh, ETE
x' z'(h] =
Wh B
where Hp is the set of nodes h 2 B. 10: return æ' converted to sparse TB-DAG form
Theorem 5. Applying team maxmargin subgame solving (Definition 4) to every subgame reached during play, in nested fashion, results in playing strategy with exploitability no worse than that of the blueprint.
A proof of Theorem 5 can be found in Appendix D.
Team-maxmarge algorithm. The team-maxmargin algorithm is applied similarly the original maxmargin algorithm. If we want to locally refine a strategy x of A while playing, team-maxmargin proceeds follows: at each game turn, it considers the public state P reached and computes an approximate solution x' to the linear program in Definition (while respecting a timelimit). Then updated for the next turns: x [B x' [ vB Xp. The blueprint strategy is used the first strategy æ. We solve the linear program by means of a column generation procedure in which the current strategy æ is given an available choice. This guarantees that the solution found is not worse than the current strategy, even if a single iteration is performed.
Column generation for sparser solutions
this section, we argue that, if the opponent a single player (rather than a team) and blueprint is sparse, then, by using column generation (e.g., Farina et al. [8]) as the solver, we can arrive at an online game-playing algorithm that runs in polynomial time (in H. per iteration) with the exception of best-response oracle.
7

---

The key observation is that the maxmargin formulation of subgame solving (Definition 4) has an input of size |8] + +C] where B is the set of played beliefs for in the current public state, and C is the set of all beliefs for V in the current public state. Therefore, to have a hope of an efficient algorithm, we need both of these quantities to be small. Hence, for this section, let us assume that is a single player or a team whose DAG is small (so that [C] is small) and that the blueprint is sparse (so that [B] small at least on the first iteration).
The algorithm is given in Algorithm 1. At high level, for computing best responses, it splits the problem of solving a game starting at public state P into subproblems, one for each reachable A a-belief B. This allows "finer" mixing of strategies than would have been allowed otherwise, Given best-response oracle (i.e., solution method to the integer program (5)). the whole algorithm runs in time rl [3), [C[P]], E) where Hr is the set of nodes h t P and B is the set of A A-beliefs in P with positive reach. While NP-hard in the general case, integer programs are practically reasonably fast to solve. In particular, if a polynomial spacceel--eeeeeeeeeeeeee algorithm such as depth-first used to solve the integer program, then the whole algorithm runs in polynomial space. This is in stark contrast to any algorithm that would expand the whole TB-DAG, as the TB-DAG takes worst-case exponential space.
is
The creation of sparse blueprints. Throughout this section, we have been assuming that blueprints created are sparse, in particular, that in every public state there are at most polynomially many beliefs. There are two straightforward ways to guarantee this. The first is to use a natively sparse algorithm such column generation generate the blueprint in the first place. The second is to take an arbitrary blueprint in realization form, and express it as a sparse convex combination via Caratheodory's 's theorem Then, the blueprint will have support size most [Z]. On the other hand, the support size of the blueprint generated by a CG algorithm, scales linearly with the number of iterations, which, under reasonable time constraints, rarely exceeds the hundreds. Thus, the far smaller support size of the blueprint yielded by CG is point in favour of the adoption of the former family of algorithms for blueprint generation.
5
Experimental evaluation
5.1 Experimental setting
Game instances. In our evaluation, we resort to game instances whose exact solution can be computed in practice by standard algorithms available in the literature. This choice allows us to calculate the equilibrium value, which is necessary appropriately assess how our subgame solving method approximates the exact solution as the time spent for the strategy refinement increases. In particular, our test suite is composed of parametric versions of the ATG instances customarily adopted in the literature where the adversary team is composed of a single player: Kuhn [11] and I Ledue [18] poker with team collusion, team Liar's Dice [13] and Tricks [21] (a simplified Bridge endgame.)
For space reasons, we omit the rules of these games, pointing an interested reader to the aforemen- tioned articles. We use the following labels:
Knr: n-player Kuhn poker with r ranks;
Lnbrs: n-player Leduc poker with b bets in each betting round, ranks and s suits;
Dnd: n-player Liar's Dice with one d-sided dice per player;
Td: three-player Trick-taking game with three ranks, four suits, and a limited amount of possible deals fixed to
We also use a binary string of length n to denote the assignment of teams, where the ith character is 1 if and only if the ith player is on team
Blueprint and strategy refinement time limits. As usual with subgame solving methods, the performance depends on the quality of the blueprint and the time spent for its refinement after every single move in the game. To provide coherent results over multiple, different game instances, we set
'Caratheodory's 's theorem asserts that any convex combination of points in Ra can be expressed as a convex combination of at most d + 1 of them.
8

---

Table I: Team's values against a best-responding opponent when playing the equilibrium strategy. blueprint, or refinement strategy with a 5, and corresponding algorithms running times. When the equilibrium computation requires more than 2 hours, we use the equilibrium values provided in [21]. The table summarizes the experiments for different game instances (see Section 5.1) and team structures (the i-th element of the vector equal to 1 means that player i is in team A), with a = 5. Equilibrium time, refinement time (per move) and blueprint time denote, respectively, the time needed to find an exact equilibrium via CG, the time allocated to a single iteration of subgame solving and the time allotted to blueprint computation. Equilibrium value indicates the expected utility of the team the equilibrium, while refinement value and blueprint value represent the team expected utility when they play against a best-responding opponent team and adopt, respectively, the blueprint strategy and the refined strategy. The gap reduction column quantifies the improvement of the refined strategy over the blueprint strategy (see Section 5.2 for a formal definition of gap).
Game instance
Team
Equilibrium
Refinement
Blucprint time
Equilibrium value
Refinement
Blueprint
Gap
structure
time
time (per move)
value
value
reduction
K34
110
0.05s
0.02s
0,02s
-0,042
-0.050
-0.061
58.0%
K36
110
0.55s
0.07s
0.03s
-0.024
-0.055
-0.098
58.3%
K38
110
2.58s
0.20s
0.04s
-0.019
-0.031
-0.152
91.2%
K312
110
10.73s
0.74s
0.29s
-0.014
-0.024
-0.064
78.9%
K45
1110
6.92s
0,54s
0,22s
-0.030
-0,046
-0.354
95. 2%
L3133
110
6m 39s
0.57s
1.59s
0.215
0.038
-0.616
7%
L3143
110
2-
2.59s
6.21s
0.107
-0.133
-0.673
69.2%
L3151
110
2m 46s
1.27s
2.80s
-0,019
-0.399
-0.624
37.3%
L3153
110
>-2h
4.91s
8.84s
0,024
-0.177
-0.681
71.5%
L3223
110
7m 44s
1.02s
12.28s
0,516
-0.320
-1.299
54.0%
L3523
110
2-2h
3m 21s
10m 46s
0.953
-1.151
-6.671
72.4%
D33
110
3m 55s
1.06s
9.15s
0,284
0.279
0.238
90.2%
D34
110
>2h
33.21s
10m 11s
0.284
0.241
0.139
70.0%
D62
111110
>2h
40.22s
10m 11s
0.333
0.167
-0.000
50.0%
T350
101
2-
0.49s
1.09s
0,600
0.509
0.352
63.3%
T3100
101
>-2h
1.16s
1.85s
0.710
0.514
0.495
8.5%
both of these time limits dependent on the complexity of the game. More precisely, the blueprint computation is stopped once 10 minutes have elapsed or column generation has achieved a Nash gap of A 10. where A is the difference between maximum and minimum team's 's payoffs, whichever comes first. We remark that the main goal of our experimental evaluation is to show that, no matter the suboptimality of the blueprint strategy and the amount of computation allocated to the subgame solving routine, the local re-optimization performed under our subgame solving framework allows us to improve the starting strategy. The choice of focusing on cases in which the blueprint strategy is suboptimal, and in which the computational budget available for subgame solve is (even severely) limited, goes precisely in that direction.
To create the strategy that would be played by Algorithm 1, we perform refinement every public state, in a top-down order. We use range of time limits for the strategy refinement, defined as the average time needed by single iteration of the CG algorithm at the root of the whole game multiplied by a number a E {0, I, .... 10}. Notice that the value obtained with = 0 is the value provided by the blueprint, while using a 2 ensures that at least one iteration of strategy refinement is done after every move in the game. Each experiment was allocated 32 CPU cores and 256 GB RAM on a cluster machine. Integer and linear programs were solved with Gurobi 9.5.
5.2 Discussion of the results
For every game instance, we computed the best-response values for the opponent against the following strategies: the equilibrium strategy, the blueprint strategy, and the strategy returned by our refinement method for different values of a. We will use gap to refer to the difference between a value and the equilibrium value. Intuitively, shows the relative quality of the blueprint when compared with the equilibrium. We use a performance index based on the concept of gap showing the capability of our refinement method to reduce the gap. We call it gap reduction. It is defined as (F- (F-R))(FF B), where E, R. and B are the values of the equilibrium, refined strategies, and blueprint respectively.

---

The values provided by the strategies when 5 are provided in Table 1, together with the algorithms' runtimes. We imitially observe that our experimental evaluation confirms the maxmargin theoretical results as the team's exploitability never increases. Most importantly, with the majority of the game instances, the gap reduction dramatic (on the average, about 65%). These results are coherent with the results achieved in the literature for two-player zero-sum games [1, 15]. We also investigate how the performance of our strategy refinement method varies as a varies. In Figure 1, report the results related to the two most representative instances together with their blueprint and equilibrium values. The plots and the tables related to the entire test suite are Appendix
Interestingly, we observe that, with the vast majority of the game instances, the curve describing the improvement provides the maximum increase by the first iteration of strategy refinement (correspond- ing to a 1). In particular the average gap reduction is about 39% when a 1, showing that time limit equal the time needed for single CG iteration at the root of the tree is sufficient to get a value very close to the equilibrium value. We also observe that the equilibrium value is never completely recovered in the test suite. This not surprising as strategy refinement methods perform local reoptimization. The improvement is sometimes not monotonically increasing in the number of the iterations. This is due to the nature CG algorithms.
Conclusions
In this paper, we propose subgame solving algorithms for adversarial team games based on the team belief DAG. team-vs.-player games, when applied with column generation as both the blueprint generator and subgame solving algorithm, oracle, which in practice can be implemented via an integer program solver. In general team-vs.-tean games, method addresses several technical difficulties that do not arise in the two-player setting, most notably the normalization of reach probabilities required by maxmarrin. In the experimental activity, we find that applying any amount of subgame solving at all to a blueprint, even a single iteration of column generation, is significantly superior to not applying it. More precisely, with standard test suite, our method reduces the the gap between the equilibrium value and the value provided by the blueprint by 39% on average even when a 1, and to 65% when = 5.
techniques run efficiently modulo best-response
In the future, believe that contributions allow the scaling of subgame solving techniques to very large team games, where ceuummn-generationiike methods such as PSRO [12] will likely be the fundamental building block for practical solutions.
Acknowledgements
This material is based on work supported by the National Science Foundation under grants IIS- 1901403 and CCF- 173355, and the ARO under award W91 INF2010081.
K36
L3523
0.00
-0.04
team value
team value
00.06
4.00
0..08
-6.00
Figure I: Value of the team's refined strategy as varying the refinement time limit. The blue dashed line in the bottom the blueprint value, while the black dotted line in the top the equilibrium value.
10

---

References
[1] N. Brown and T. Sandholm. Safe and nested subgame solving for imperfect-informationn games. In NIPS, 2017.
[2] N. Brown and T. Sandholm. Superhuman ai for heads-up no-limit poker: Libratus beats top professionals. Science, 359:418 424, 2018.
[3] N. Brown, T. Sandholm, and B. Amos. Depth-limited solving for imperfect-infooration games. In NeurIPS, 2018.
[4] N. Burch, M. B. Johanson, and M. Bowling. Solving imperfect information games using decomposition. In AAAI, 2014.
[5] L. Carminati, F. Cacciamani, M. Ciccone, and N. Gatti. A marriage between adversarial team games and 2-player games: Enabling abstractions, no-regret learning, and subgame solving. In ICML, 2022.
[6] L. Carminati, F. Caceiamani, M. Ciccone, and N. Gatti. Public information representation for adversarial team games. ArXiv, Abss2201.10377/ 2022.
[7] A. Celli and N. Gatti. Computational results for extensive-form adversarial team games. In AAAI, 2018.
[8] G. Farina, A. Celli, N. Gatti, and T. Sandholm. Ex ante coordination and collusion in zero-sum multi-player extensive-fom games. In NeurlPS, 2018.
[9] G. Farina, A. Celli, N. Gatti, and T. Sandholm. Comnecting optimal ex-ante collusion in teams to extensive-form correlation: Faster algorithms and positive complexity results. In JCML., 2021.
[10] S. K. Jakobsen, T. B. Sørensen, and V. Conitzer. Timeability of extensive-form games. In ITCS, page 191-199, 2016.
[11] H. Kuhn, A simplified two-person poker. Contributions to the Theory of Games, 1:97-103. 1951.
[12] M. Lanctot, V. Zambaldi, A. Gruslys, A. Lazaridou, K. Tuyls, J. Pérolat, D. Silver, and Graepel. A unified game-thor theoretic approach to multiagent reinforcement learning. In NeurlPS, pages 4190-4203, 2017.
[13] V. Lisý, M. Lanctot, and M. Bowling. Online monte carlo counterfactual regret minimization for scarch in imperfect information games. In AAMAS, 2015.
[14] H. B. McMahan, G. J. Gordon, and A. Blum. Planning in the presence of cost functions controlled by adversary. In ICML, 2003.
[15] M. Moraveík, M. Schmid, K. Ha, M. Hladík, and S. J. Gaukrodger. Refining subgames in large imperfect information games. In AAAI, 2016.
[16] M. Moraveík, M. Schmid, N. Burch, Lisy, D. Morrill, N. Bard, T. Davis, K. Waugh, M. B. Johanson, and M. H. Bowling. Deepstack: Expert-level artificial intelligence in heads-up no-limit poker. Science, 356:508 513, 2017.
[17] T. Sandholm. Abstraction for solving large mncompete-informmttie games. In AAAI, 2015.
[18] Southey, M. Bowling, B. Larson, C. Piccione, N. Burch, D. Billings, and D. Rayner. Bayes bluff: Opponent modelling in poker. In UAI, 2005.
[19] B. von Stengel and Koller. Team-maxmin equilibria. Games and Economic Behavior, 21: 309-321, 1997.
[20] B. H. Zhang and T. Sandholm, Team correlated equilibria in zero-sum extensive-form games via tree decompositions. In AAAI, 2021.

---

[21] B. H. Zhang, G. Farina, A. Celli, and T. Sandholm. Optimal correlated equilibria in general-sum extensive-form games: Fixed- parammter algorithms, hardness, and two-sided column- -uunnngeeraatinn Proceedings of the 23rd ACM Conference Economics and Computation, 2022.
[22] B. H. Zhang, G. Farina, and T. Sandholm. Team belief dag form: A concise representation for cerm-correlated game-theoretic decision making. ArXiv, abs/2202.00789, 2022.
[23] Y. Zhang and B. An. Computing ex ante coordinated team-maxmin equilibria in zero-sum multiplayer extensive-form games. In AAAI, 2021.
[24] M. A. Zinkevich, M. B. Johanson, M. Bowling, and C. Piccione. Regret minimization in games with incomplete information. In NeurlPS, 2007.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [N/A]
(b) Did you include complete proof's of all theoretical results? [N/A]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material URL)? [Yes]
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g.. type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you using existing assets (e.g., code, data, models) curating/releusing assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
12


Reviews:
[{"review_id": "trF8R_YArjV", "reviewer": "Reviewer_iqNg", "summary": "This paper focuses on solving large adversarial team games, which include both cooperation and competition. They extend the subgame solving technique of solving huge two-player zero-sum games, which computes a blueprint strategy offline and refines it online. The proposed approach is based on team-belief DAG for the gadget game and column generation algorithm for refining the blueprint strategy. They empirically evaluate the proposed approach to see if the blue strategy is improved.", "questions": "No", "limitations": "Yes", "rating": 3, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Existing algorithms are hard to solve large games, e.g., the performance of (column generation) CG is constrained by the requirement of memory and iterations. To overcome this challenge, this paper extends the subgame-solving technique to AGT by handling its unique property in AGT.\nHowever, this proposed subgame-solving technique still uses CG for both the blueprint and the subgame-solving procedure. Then this proposed algorithm may still suffer the limitation of existing algorithms.\n\nThis work aims to solve large games, but games used in experiments are very small, and all of them can be solved efficiently by existing algorithms, e.g., algorithms in [20]. Even in these small games, e.g., Leduc poker games, the gap between the equilibrium value and the refinement value is still very large. If this proposed solving algorithm cannot perform well in these small games, it is hard to imply that it can perform well in larger games.\n\nIt is interesting to see the performance of the algorithms in [20] or [21] using the same time as the subgame solving algorithm\n\nThe following multiagent learning-based algorithm for TMECor that is not limited by memory should be a baseline.\\\nCacciamani F, Celli A, Ciccone M, Gatti N. Multi-Agent Coordination in Adversarial Environments through Signal Mediated Strategies. In Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems 2021 May 3 (pp. 269-278).\n\nLine 3 of Algorithm 1: ‘alt’ ->’all’", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "tV1yGqDAgFt", "reviewer": "Reviewer_a16J", "summary": "The paper proposes a modification of subgame refinement for adversarial team games. An abstract strategy is refined for the public states encountered in the game with additional iterations using a modification of the max-margin gadget. The empirical evaluation on multiple games that can completely fit into memory shows that most of the gap from the optimal solution can be removed by this method.", "questions": "Are the results transferable to general imperfect recall games?", "limitations": "Limitations were addressed IMO adequately and I do not see negative societal impact of the work.", "rating": 6, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Decomposition on solving large imperfect information games in a relevant problem and this paper makes an incremental, but solid step in generality of this approach. I am not aware of any other work on subgame refining in team games, or even imperfect recall games in general. The paper is well written, reasonably easy to follow, and I did not find any serious technical mistakes.\n\nThe experiments are sufficiently thorough for a conference paper. They show a clear merit of the approach. On the other hand, they fail to explore more widely the practical applicability tradeoffs. How much larger games are now solvable with this approach? One of the key complications of the presented approach is the use of DAG strategy representation, which is certainly important if the game is supposed to fit into the memory. Subgame solving is likely to push the boundary a little, but combining it with depth-limited solving would most likely be much more impactful. With a value funcion the difference between DAG and tree representation would become much less relevant.\n\nTeam games are becoming an established line of work. However, as the authors admit themselves, it is a special case of imperfect recall games and it is not clear to me why to study them separately. Is the subgame solving in this paper applicable also in general imperfect recall games or are there some assumptions given by the special case that are necessary?\n\nMinor issues:\n\n Line 53: It seems to claim that [15] was using an offline computed blueprint strategy, which is incorrect.\n\nLine 277: A little more details on which Caratheodory’s theorem you mean and how to use it would be appreciated.\n\nI assume that the refinement is run from each decision node in the experiments, but I did not find it explicitly stated anywhere.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "_fET9wI2oZs", "reviewer": "Reviewer_3Trb", "summary": "This paper presents a subgame solving method that extends the existing approach to solving huge two-player zero-sum games. The main improvement of this paper is to solve the online optimization strategy through subgame solving. The subgame solving method is to generate the gadget game based on the team belief DAG (TB-DAG). The blueprint strategy is refined by iterative expansion using the column-generation (CG) algorithm, and its size increases linearly with the number of best-response oracle calls. That avoids the exponential size of the whole TB-DAG when expanding in the worst case. The blueprint generated by the CG algorithm is sparse. On this basis, the max-margin optimization problem in the subgame is converted into a linear program problem, which can be solved by the state-of-the-art integer program solver. Given the best-response oracle, the solving algorithm can be found to run end-to-end in polynomial time. Finally, they experimentally evaluated their method using a standard test suite and showed that this refinement of subgame solving is effective in reducing the difference between the value provided by the equilibrium strategy and the blueprint.", "questions": "1. How does the blueprint strategy generate? How to ensure that the blueprint strategy is a suboptimal strategy? Is it possible to generate sparse blueprint strategies if the game instances are relatively huge?\n2. In Section 5.2, this paper mentions how the performance of this strategy refinement method varies as \\alpha varies. Due to the nature of the CG algorithms, the improvement is sometimes not monotonically increasing in the number of iterations. What is the relationship between the performance of this method and \\alpha? How about the performance when \\alpha is greater than 5?\n3. How does the equilibrium values calculate in the experiment?\n4. The format of the conference names in the references is not uniform, some are abbreviations, some are full names, and the abbreviations of the names of the same conference are not consistent.\n5. Figure 5.2, mentioned in Section 5.2, does not appear in the paper, there is only Figure 1.\n", "limitations": "The premise of the subgame solving approach proposed in the paper is that the blueprint strategies are assumed to be sparse, and the paper generates sparse blueprints by the CG algorithm. However, if the blueprint strategy generated by the CG algorithm is not sparse, the solution by the approach proposed in the paper may not be achieved in polynomial time.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "1. Originality\nCompared with other adversarial team game approaches, the subgame solving approach proposed in this paper extends the maxmargin subgame solving to adversarial team games (ATGs), generates a gadget game from its TB-DAG subgame, uses the CG algorithm to generate a sparse blueprint and expand the blueprint strategy iteratively, given the best-response oracle, and enables the refinement of the blueprint strategy to approximate an exact solution.\n\n2. Quality\nThe authors implement an online refinement strategy that approximates an exact solution without expanding the whole TB-DAG exponentially. However, there are the following problems in this paper.\n(1) This paper lacks detailed theorems and proofs of the properties of approximation to the exact solution.\n(2) There are two ways to generate sparse blueprints, but the experimental evaluation only considers the sparse blueprints generated by the CG algorithm, and not on the sparse blueprints obtained by the other method, i.e., taking an arbitrary blueprint in realization form and expressing it as a sparse convex combination by Caratheodory’s theorem. The experimental evaluation is not complete and sufficient.\n\n3. Clarity\nThe paper is somehow well-structured and the language is fluent. \n(1) The paper links to the literature giving relevant game examples, but the overall process of specific solving using the approach proposed in this paper is not intuitive and clear enough. \n(2) In the experimental results, the meaning of each index in Table 1 is not explained one by one.\n\n4. Significance\nThe subgame solving technique proposed in this paper is effective for reducing the difference between blueprint strategy and equilibrium strategy and extends the successful approach of solving huge two-player zero-sum games, in which the CG algorithm is a very important component of subgame solving technology. Methods similar to column generation may also be used as fundamental building blocks in solving team games. However, in the experimental results, the team structure size of the game instances given is small.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Xo4qzY8VL5A", "reviewer": "Reviewer_DBNN", "summary": "The paper addresses approximating equilibrium strategies in adversarial team games (ATGs).  The paper claims the following contributions: (1) It is “the first method for refining strategies by subgame solving in ATGs,” which it does by generating a “blueprint strategy” using a column-generation algorithm (with a time limit).  (2) it develops the Team-maxmargin algorithm, which is motivated by the existing maxmargin algorithm.  This algorithm in experimental evaluations “reduces the gap between the values provided by the equilibrium strategy and the blueprint.”\n", "questions": "I'd be happy for the authors to correct anything in my review that is incorrect or denotes a misunderstanding of the paper's contributions.", "limitations": "Please see the previous sections", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Up-front comment so that my review can be taken in proper context: This paper is in the rather niche area of solving zero-sum games, an area that has been developed extensively over the last decade or two primarily by a handful of research groups.  While being familiar with that area, I am not immersed in it, nor have I followed the notation, terminology, and advancements extremely closely.  Typically, however, I can follow papers in this area.  But I had difficulty following the details of the paper and its high-level message.   I followed the terminology and notation well for a while as I read into the paper, but then the overwhelming number of terms, etc. caused me to begin to lose context (and hence interest).  That said, during my efforts, I noted that the paper is written cleanly and carefully, and appears to be technically sound.  The paper exhibits a high amount of technical knowledge, I just couldn’t follow it the whole paper through.  On the downside, I also failed to grasp the key technical messages of the paper (what makes it tick? What knowledge generalizes?) within the time-limits that I had (being an emergency reviewer for this paper).\n\nWith that context in mind, here is my evaluation of the contributions of the paper:\n\n(1) Is the claim that the paper is the first to present “a method for refining strategies by subgame solving in ATGs” substantiated in the paper?  No.  I recommend that this claim be removed from the paper.  First, it would be impossible to substantiate.  Second, the contribution of the paper likely wouldn’t be reduced even if the claim was proven to be false.  Third, the claim hurts the paper in that it focuses the reader on whether it really is the first rather than the actual content of the paper.  Thus, I think the paper would be better if the claim were removed.\n\n(2) While I found the team-maxmargin algorithm difficult to follow, the empirical results across four different zero-sum games do appear to indicate that it does reduce the gap between the values provided by the equilibrium strategy and the blue print.  I find it nice that the paper considers the four games.\n\nIs the algorithm novel?  I believe it is.  The knowledge development is somewhat incremental in that the approach builds well upon existing work in the well-developed area.\n\nIs the contributed knowledge important?  It depends on how much one values game playing.  It certainly is a fun topic, though one could argue that such game-playing is unlikely to lead to useful applications in the near future.  Even still, it is possible that knowledge generated in this domain could become useful outside of the niche area.  And this paper represents an impressive effort that can expand knowledge for those in the area.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept