# Integrating Dynamic Weighted Approach with Fictitious Play and
Pure Counterfactual Regret Minimization for Equilibrium Finding

Qi Ju  Falin Hei  Zhemei Fang  YunFeng Luo

###### Abstract

Developing efficient algorithms to converge to Nash Equilibrium is a key focus
in game theory. The use of dynamic weighting has been especially advantageous
in normal-form games, enhancing the rate of convergence. For instance, the
Greedy Regret Minimization (RM) algorithm has markedly outperformed earlier
techniques. Nonetheless, its dependency on mixed strategies throughout the
iterative process introduces complexity to dynamic weighting, which in turn
restricts its use in extensive-form games.

In this study, we introduce two novel dynamic weighting algorithms: Dynamic
Weighted Fictitious Play (DW-FP) and Dynamic Weighted Pure Counterfactual
Regret Minimization (DW-PCFR). These algorithms, utilizing pure strategies in
each iteration, offer key benefits: (i) Addressing the complexity of dynamic
weight computation in Greedy RM, thereby facilitating application in
extensive-form games; (ii) Incorporating the low-memory usage and ease-of-use
features of FP and CFR; (iii) They guarantee a convergence lower bound of
$\mathcal{O}\left(T^{-\frac{1}{2}}\right)$, with a tendency to achieve a
convergence rate of $\mathcal{O}(T^{-1})$ as runtime increases. This research
not only theoretically affirms the convergence capabilities of these
algorithms but also empirically demonstrates their superiority over existing
leading algorithms across all our tests.

##  1 Introduction

The core issue in game theory is solving Nash Equilibrium (NE). Many games
involve extensive actions or high costs for analyzing payoff matrices, making
traditional linear programming methods inadequate. Recently, self-play methods
for approximating equilibrium have become mainstream. Notably, the
Counterfactual Regret Minimization (CFR) algorithm based on Regret
Minimization (RM), its variants, and algorithms developed from Fictitious
Play, like Fictitious Self Play, have achieved significant success in games
like poker (Bowling et al., 2015; Brown & Sandholm, 2017, 2019b) and Starcraft
(Vinyals et al., 2019).

Variants of RM primarily fall into two categories: those extending CFR’s
applicability, such as Monte Carlo-CFR (Lanctot et al., 2009), CFR pruning
(Brown & Sandholm, 2015), CFR abstraction (Kroer & Sandholm, 2018), and Pure-
CFR (PCFR) (Qi et al., 2023); and those enhancing RM’s rate of convergence,
like CFR+ (Tammelin, 2014), discount CFR (Brown & Sandholm, 2019a), and Greedy
Regret Minimization (Greedy RM) (Zhang et al., 2022). These methods, when
combined, form powerful algorithms that have proven successful in practice.
Greedy RM innovatively uses dynamic weight to accelerate convergence,
dynamically adjusting strategy weights based on real-time training, unlike
vanilla CFR’s preset weights timetable. While Greedy RM can significantly
speed up convergence in normal-form games, its iterative use of mixed
strategies complicates dynamic weight calculations, especially in extensive-
form games.

Fictitious Play (FP) is an alternate approach to solving NE, traceable back to
Brown’s article from 1951 (Brown, 1951). A key distinction between FP and
Regret Matching (RM) is FP’s use of pure strategies in each iteration, leading
to macro-level convergence rates similar to RM. In The Theory of Learning in
Games (Fudenberg & Levine, 1998), Fudenberg effectively summarized and
formally defined FP. Qi’s application of FP to extensive-form games developed
the PCFR algorithm (Qi et al., 2023), showing potential to surpass MCCFR in
certain scenarios. Abernathy overcame the problem of slow convergence of FP in
previous research and revealed the phenomenon of repeated strategy profiles in
the FP algorithm (Abernethy et al., 2021).

We contend that FP’s use of pure strategies in each iteration can
significantly simplify dynamic weight computation. Inspired by Greedy RM and
Abernethy’s findings, we integrated dynamic weighting into FP/PCFR. This
merger significantly improved both algorithms, preserving their plug-and-play
and parameter-free advantage. And the convergence rate is also much faster. In
our experiments, the convergence rate is close to $\mathcal{O}(T^{-1})$. Our
code can be found in Github.

##  2 Notation and Preliminaries

###  2.1 Game Theory

####  2.1.1 Normal-Form Games

In normal-form games, the set of players is denoted by
$\mathcal{N}=\\{1,2,\dots\\}$. Each player $i$ has a finite set of legal
actions $\mathcal{A}^{i}=\\{a_{1},a_{2},\dots\\}$. The mixed strategy set
$\Sigma^{i}\in\mathbb{R}^{|\mathcal{A}|}$ (where $|\cdot|$ represents the
number of elements in the set) is a probability distribution over
$\mathcal{A}^{i}$ (a simplex in $|\mathcal{A}|$ dimensions). A strategy is
termed pure if it assigns probability 1 to a single action and 0 to others, we
directly use $a$ to represent the corresponding pure strategy. A strategy
profile $\sigma=\times_{i\in\mathcal{N}}\sigma^{i}$ is formed by the
strategies of all players, and $\sigma^{-i}$ represents the strategy profile
of all players except $i$. The payoff function
$u^{i}:\Sigma\rightarrow\mathbb{R}$ is finite, and $u^{i}(a,\sigma^{-i})$
denotes the payoff for player $i$ when taking action $a$ while other players
follow the strategy profile $\sigma^{-i}$.
$L=\max_{i\in\mathcal{N},\sigma\in\Sigma}u^{i}(\sigma)-\min_{i\in\mathcal{N},\sigma\in\Sigma}u^{i}(\sigma)$
represents the payoff range of the game.

####  2.1.2 Extensive-Form Games

In extensive-form games, typically represented as game trees, the player set
is denoted by $\mathcal{N}=\\{1,2,\dots\\}$. Nodes $s$ in the game tree
represent potential states, forming the state set $s\in\mathcal{S}$, with leaf
nodes $z\in\mathcal{Z}$ as terminal states. For each state $s\in\mathcal{S}$,
successor edges define the action set $\mathcal{A}(s)$ available to a player
or chance. The player function
$P:\mathcal{S}\rightarrow\mathcal{N}\cup\\{c\\}$ determines who acts in a
given state, with $c$ indicating chance. Information sets
$I\in\mathcal{I}^{i}$ represent sets of states indistinguishable to player
$i$. The payoff function $R:\mathcal{Z}\rightarrow\mathbb{R}^{|\mathcal{N}|}$
maps terminal states to a payoff vector for the players. The behavioral
strategy $\sigma^{i}(I)\in\mathbb{R}^{|\mathcal{A}(I)|}$ for all
$I\in\mathcal{I}^{i}$ is a probability distribution defined on each
information set $I$. Define $\pi_{\sigma}(I)$ is the probability of
information set $I$ occurring if all players choose actions according to
$\sigma$.

####  2.1.3 NE and $\epsilon$-NE

The best response (BR) set for player $i$ against the strategy profile
$\sigma^{-i}$ of the opponents is defined as:

$b^{i}(\sigma^{-i})={\arg\max}_{a^{*}\in\mathcal{A}^{i}}u^{i}(a^{*},\sigma^{-i})$
(1)

BR strategy proper can be a pure strategy or a mixed strategy, but finding
pure BR strategy is simpler. In our subsequent analysis, we assume $b(\sigma)$
to be a pure strategy. Here, $\arg\max$ refers to identifying the elements in
a set that yield the maximum value. If multiple elements in this maximum
value, the first strategy in lexicographic order well be chosen.

Player $i^{\prime}$s exploitability $\epsilon^{i}$ for a strategy profile
$\sigma$ is defined as:

$\epsilon^{i}=u^{i}(b^{i}(\sigma^{-i}),\sigma^{-i})-u^{i}(\sigma)$ (2)

And the overall exploitability $\epsilon$ of all players is defined as:

$\epsilon=\frac{1}{|\mathcal{N}|}{\sum}_{i\in\mathcal{N}}\epsilon^{i}$ (3)

When $\epsilon=0$, the strategy profile $\sigma$ constitutes a NE, otherwise
it is a $\epsilon$-NE.

####  2.1.4 Self Play and Convergence Rate

Directly solve an exact NE in games is a PPAD problem (Papadimitriou, 1994),
an unresolved challenge in theory of computation. In practice, for large-scale
games, the approach typically involves self-play (SP) methods to iteratively
find an approximate NE. There are various forms of SP (Heinrich et al., 2015;
Leslie & Collins, 2006; Hernandez et al., 2019), but here we focus on the most
basic SP format. An elementary SP process can be abstracted into four steps:
(i) Initialize. (ii) Observe Utility. (iii) Get Next Strategy. (iv) Update
Average Strategy.

During iterations, if the strategy’s exploitability satisfies $\epsilon\propto
T^{-\frac{1}{2}}$, the convergence rate of the algorithm is
$\mathcal{O}\left(T^{-\frac{1}{2}}\right)$. Additionally, the time complexity
within one iteration is a critical factor affecting the convergence rate. We
use $\mathscr{O}(\cdot)$ to describe the time complexity needed for one
iteration.

###  2.2 Regret and Greedy Regret Minimization

For any strategy sequence $\sigma_{1}\ldots\sigma_{T}$ in the game, the
external regret of player $i$ for not choosing action $a^{i\prime}\in A^{i}$
is defined as:

$R^{i}\left(a^{i\prime}\right)=\sum_{t=1}^{T}w_{t}\left(u^{i}\left(a^{i\prime},\sigma^{-i}_{t}\right)-u^{i}\left(\sigma_{t}\right)\right)$
(4)

Consequently, the overall average external regret for player $i$ can be
defined as:

$\bar{R}^{i}=\max_{a^{i\prime}\in
A^{i}}\frac{R^{i}\left(a^{i\prime}\right)}{\sum_{t=1}^{T}w_{t}}$ (5)

Here, $w_{t}$ represents the weight of each strategy. While there’s also the
concept of internal regret (Blum & Mansour, 2007), all instances of regret
mentioned in this paper pertain to external regret. If both player’s average
regret is less than $\epsilon$, then, $\sigma_{t}$ is a
2$\epsilon$-equilibrium (Cesa-Bianchi & Lugosi, 2006). We directly present the
algorithm for Greedy RM 1.

Algorithm 1 Greedy RM

1: Initialization:

2: Random initialization $\sigma_{t=1}$. Set
$\bar{\sigma}_{t=1}^{i}=\boldsymbol{0}$, $\bar{R}_{t=0}^{i}=\boldsymbol{0}$,
$W^{i}_{t=0}=0$ for all $i\in\mathcal{N}$.

3: for $t=1,2,\dots$ do

4: Observe Utility:

5:
$R^{i}_{t}(a)=u^{i}\left(a,\sigma^{-i}_{t-1}\right)-u^{i}\left(\sigma_{t-1}\right)$

6:
$w^{i}_{t}=\min_{w^{\prime}}\Phi\left(\frac{W^{i}_{t-1}}{W^{i}_{t-1}+w^{\prime}}\bar{R}_{t-1}^{i}+\frac{w^{\prime}}{W^{i}_{t-1}+w^{\prime}}R^{i}_{t}\right)$

7: $\alpha_{t}^{i}=\frac{w^{i}_{t}}{W^{i}_{t-1}+w^{i}_{t}}$

8:
$\bar{R}_{t}^{i}=(1-\alpha_{t}^{i})\bar{R}_{t-1}^{i}+\alpha_{t}^{i}R^{i}_{t}$

9: Next Strategy:

10: $\bar{R}_{t}^{i,+}(a)=\max\left(\bar{R}_{t}^{i}(a),0\right)$

11: if $\sum_{a\in\mathcal{A}^{i}}\bar{R}_{t}^{i,+}(a)>0$ then

12:
$\sigma_{t+1}^{i}(a)=\frac{\bar{R}_{t}^{i,+}(a)}{\sum_{a\in\mathcal{A}^{i}}\bar{R}_{t}^{i,+}(a)}$

13: else

14: $\sigma_{t+1}^{i}(a)=\frac{1}{|\mathcal{A}^{i}|}$

15: end if

16: Update Average Strategy:

17:
$\bar{\sigma}_{t}=(1-\alpha_{t}^{i})\bar{\sigma}_{t-1}+\alpha_{t}^{i}\sigma_{t}$

18: $W^{i}_{t}=W^{i}_{t-1}+w^{i}_{t}$

19: end for

Where $\Phi$ is the potential function, defined as the sum of the squared
positive regrets. The convergence rate of Greedy RM is guaranteed
$\mathcal{O}\left(T^{-\frac{1}{2}}\right)$. The time complexity of one
iteration of the RM algorithm is $\mathscr{O}\left(|\mathcal{A}|^{2}\right)$.
In Greedy RM, the weight assigned to a particular action in the next strategy
is directly proportional to the regret value. Therefore, this strategy is
often referred as the regret matching strategy.

In Greedy RM, the core distinction lies in its approach to dynamic weights
$w_{t}^{i}$. Unlike vanilla RM, where weights are either constant or adhere to
a predefined schedule, Greedy RM dynamically generates these weights in real
time during each iteration. Although the potential function for dynamic
weights $w_{t}^{i}$ in Greedy RM is convex and can be approximated through
bisection, the necessity of solving this optimization problem in every
iteration of the algorithm presents a significant challenge. Considering that
self-play algorithms often involve millions of iterations, repeatedly solving
for $w_{t}^{i}$ becomes a time-consuming and cumbersome task.

Furthermore, Greedy RM is not a plug-and-play algorithm. In its vanilla form,
Greedy RM often does not significantly hasten convergence, leading to the
necessity of integrating action sampling ($a_{t}\sim\sigma_{t}$) to enhance
its effectiveness. However, this integration tends to introduce instability
into the algorithm’s performance. To mitigate this, a floor parameter is often
required, where $w_{t}^{i}$ is set as
$\max\left(w_{t}^{i},\frac{W_{t}^{i}}{2t}\right)$. This necessary adjustment
for stability, coupled with the inherent complexity of calculating dynamic
weights $w_{t}^{i}$, poses substantial challenges in applying Greedy RM
effectively, particularly in large-scale games.

###  2.3 Fictitious Play and Its Variants

####  2.3.1 Fictitious Play

Algorithm 2 Q-Value Based FP

1: Initialization:

2: Random initialization $\sigma_{t=1}$. Set
$\bar{\sigma}_{t=1}^{i}=\boldsymbol{0}$ $\bar{Q}_{t=0}^{i}=\boldsymbol{0}$ for
all $i\in\mathcal{N}$.

3: for $t=1,2,\dots$ do

4: Observe Utility:

5: $Q^{i}_{t}(a)=u(a,\sigma_{t}^{-i})$

6: $\bar{Q}_{t}^{i}(a)=\frac{t-1}{t}\bar{Q}^{i}_{t-1}+\frac{1}{t}Q^{i}_{t}$

7: Next Strategy:

8: $\sigma^{i}_{t+1}=\arg\max_{a\in\mathcal{A}^{i}}\bar{Q}^{i}_{t}(a)$

9: Update Average Strategy:

10: $\bar{\sigma}_{t}=\frac{t-1}{t}\bar{\sigma}_{t-1}+\frac{1}{t}\sigma_{t}$

11: end for

The described Q-value based FP process 2 is only applicable to two-player
games. The vanilla FP process omits the Observe Utility step. Instead, it
directly solves for the next strategy,
$\sigma_{t}=b\left(\bar{\sigma}_{t-1}\right)$ in the Next Strategy step.

It’s noted that the convergence rate of FP is
$\mathcal{O}\left(LT^{-\frac{1}{2|\mathcal{A}|-2}}\right)$ (Robinson, 1951),
which is slower than RM’s convergence rate. The time complexity of one
iteration of the FP algorithm is $\mathscr{O}\left(|\mathcal{A}|^{2}\right)$,
which is less than RM, results in comparable macroscopic convergence rates
between RM and FP.

####  2.3.2 Fast FP in Diagonal-Form Payoff Matrices

Karlin make a conjecture on the FP.

######  Conjecture 2.1 (Karlin’s conjecture (Karlin, 2003)).

The limit convergence rate of FP could be
$\mathcal{O}\left(LT^{-\frac{1}{2}}\right)$.

However, this conjecture has been debated due to its lack of practical
realization (Daskalakis & Pan, 2014). Recently, Abernethy proposed a new
perspective on FP, demonstrating the validity of the Karlin conjecture in
games with diagonal payoff matrices.

In two-player games with diagonal payoff matrices, the action sequences in FP
alternate consistently between sync and split phases. As shown in Figure 1,
during a sync phase, both players choose strategies with the same order, such
as $\left(a^{1}_{x},a^{2}_{x}\right)$. This is followed by a split phase,
where their choices differ, like $\left(a^{1}_{x},a^{2}_{y}\right)$. The
sequence then continues to alternate, as seen in
$\left(a^{1}_{y},a^{2}_{y}\right)$ and $\left(a^{1}_{y},a^{2}_{z}\right)$.

Figure 1:  Sync-Split Phase in Diagonal Payoff Matrix Games

Abernethy’s research reveals that during FP iterations, the strategy profiles
chosen by players tend to exhibit a regular pattern and often repeat across
multiple iterations. Understanding and harnessing this repetitive nature of
strategy profiles in FP can be pivotal in accelerating the convergence
process. By effectively predicting and calculating the repetition frequency of
these strategy profiles, the overall convergence rate of the FP method can be
significantly improved.

####  2.3.3 Pure CFR

PCFR adopts a simple yet effective method by utilizing BR strategies, in
contrast to the typical regret matching strategies for next strategy
selection. The convergence of PCFR is easy to prove. Firstly, FP’s convergence
to NE categorizes it as a regret minimizer (Abernethy et al., 2011). It also
means FP satisfied Blackwell approachability (Blackwell, 1956). The CFR
framework clarifies that if an algorithm is Blackwell approachable, its regret
values will converge to zero (Zinkevich et al., 2007).

Algorithm 3 PCFR

1: Initialization:

2: Random initialization $\sigma_{t=1}(I)$. Set
$\bar{\sigma}_{t=1}^{i}(I)=\boldsymbol{0}$, $W_{t=0}^{i}(I)=0$,
$\bar{Q}_{t=0}^{i}(I)=\boldsymbol{0}$ for all $i\in\mathcal{N}$,
$I\in\mathcal{I}$.

3: for $t=1,2,\dots$ do

4: for $\forall I\in\mathcal{I}$ do

5: Observe Utility:

6: $Q^{i}_{t}(I,a)=\pi_{\sigma_{t}}^{-i}(I)u^{i}(I,\sigma_{t}|_{I\rightarrow
a})$

7:
$\bar{Q}^{i}_{t}(I)=\frac{t-1}{t}\bar{Q}^{i}_{t-1}(I)+\frac{1}{t}Q^{i}_{t}(I)$

8: Next Strategy:

9: $\sigma^{i}_{t+1}(I)={\arg\max}_{a\in\mathcal{A}(I)}\bar{Q}_{t}^{i}(I,a)$

10: Update Average Strategy:

11:
$\alpha_{t}=\frac{\pi_{\sigma_{t}}^{i}(I)}{W_{t-1}(I)+\pi_{\sigma_{t}}^{i}(I)}$

12:
$\bar{\sigma}_{t}^{i}(I)=(1-\alpha_{t})\bar{\sigma}_{t-1}^{i}(I)+\alpha_{t}\sigma_{t}^{i}(I)$

13: $W_{t}^{i}(I)=W_{t-1}^{i}(I)+\pi_{\sigma_{t}}^{i}(I)$

14: end for

15: end for

Algorithm 3 is termed Pure CFR because each iteration yields a pure strategy.
PCFR leads to a significant computational advantage, with each iteration
requiring only
$\mathscr{O}\left(|\mathcal{A}||\mathcal{I}|^{-\frac{1}{2}}\right)$ in time
complexity, compared to CFR’s $\mathscr{O}(|\mathcal{A}||\mathcal{I}|)$.

##  3 Method

Our approach integrates ideas from the works of Abernethy and Qi. Drawing from
Abernethy’s insights, we developed a novel FP implementation named DW-FP. This
method significantly enhances the convergence rate of equilibrium in normal-
form games. Inspired by Qi’s research, we extended DW-FP to extensive-form
games, resulting in the DW-PCFR.

###  3.1 DW-FP

In FP algorithms, the same strategy profiles often repeat for multiple
iterations. For instance, as shown in Table 1, in Rock-Paper-Scissors (RPS)
starting with the strategy profile (R,R), the iteration process reveals
repeated strategy profiles in iterations 1$-$3, 4$-$8, 9$-$15, $\ldots$ By
calculating the number of repetitions (dynamic weights), we can accelerate
FP’s convergence.

Table 1: The Process of Solving RPS Using Q-Value Based FP Algorithm
No. DW-FP Iteration |  No. FP Iteration |  Player 1$\&$2 (with initial strategy profile (R,R))
---|---|---
$Q_{t}$ (r,p,s) |  $t\bar{Q}_{t}$ (r,p,s) |  Next BR strategy |  $t\bar{\sigma_{t}}$ (r,p,s)
| $1$ | $0$ | $1$ | -$1$ | $0$ | $1$ | -$1$ | P | $1,~{}0,~{}0$
$1$ | $2$ | -$1$ | $0$ | $1$ | -$1$ | $1$ | $0$ | P | $1,~{}1,~{}0$
| $3$ | -$1$ | $0$ | $1$ | -$2$ | $1$ | $1$ | P | $1,~{}2,~{}0$
| $4$ | -$1$ | $0$ | $1$ | -$3$ | $1$ | $2$ | S | $1,~{}3,~{}0$
| $5$ | $1$ | -$1$ | $0$ | -$2$ | -$0$ | $2$ | S | $1,~{}3,~{}1$
$2$ | $6$ | $1$ | -$1$ | $0$ | -$1$ | -$1$ | $2$ | S | $1,~{}3,~{}2$
| $7$ | $1$ | -$1$ | $0$ | $0$ | -$2$ | $2$ | S | $1,~{}3,~{}3$
| $8$ | $1$ | -$1$ | $0$ | $1$ | -$3$ | $2$ | S | $1,~{}3,~{}4$
| $9$ | $1$ | -$1$ | $0$ | $2$ | -$4$ | $2$ | R | $1,~{}3,~{}5$
| $10$ | $0$ | $1$ | -$1$ | $2$ | -$3$ | $1$ | R | $2,~{}3,~{}5$
| $11$ | $0$ | $1$ | -$1$ | $2$ | -$2$ | $0$ | R | $3,~{}3,~{}5$
$3$ | $12$ | $0$ | $1$ | -$1$ | $2$ | -$1$ | -$1$ | R | $4,~{}3,~{}5$
| $13$ | $0$ | $1$ | -$1$ | $2$ | $0$ | -$2$ | R | $5,~{}3,~{}5$
| $14$ | $0$ | $1$ | -$1$ | $2$ | $1$ | -$3$ | R | $6,~{}3,~{}5$
| $15$ | $0$ | $1$ | -$1$ | $2$ | $2$ | -$4$ | R | $7,~{}3,~{}5$
4 | $16$ | $0$ | $1$ | -$1$ | $2$ | $3$ | -$5$ | P | $8,~{}3,~{}5$

The key to calculating dynamic weights in FP is conceptualizing it as a
pursuit problem. This approach is apt because the next strategy in FP is
determined by the action with the maximum Q-value. A strategy change occurs at
the point where there’s a shift in the maximum of $t\bar{Q}_{t}$. Our task is
to determine how many iterations are required for this shift in the maximum
Q-value. Since $t\bar{Q}_{t}$ is the integral of $Q_{t}$, if strategy
$a^{\prime}$ has a higher Q-value than the current strategy $a$, the
difference $Q^{gap}=t\bar{Q}_{t}(a)-t\bar{Q}_{t}(a^{\prime})$ represents the
distance for the pursuit. The change rate $S=Q_{t}(a^{\prime})-Q_{t}(a)$ is
the speed of pursuit, and the required pursuit time is $w=Q^{gap}/S$ (dynamic
weights in DW-FP). It directly leads to the next BR strategy, streamlining the
overall process and significantly speeding up convergence. The specific
implementation of DW-FP is shown in Algorithm 4.

Algorithm 4 DW-FP(Ours)

1: Initialization:

2: Random initialization $\sigma_{t=1}$. Set
$\bar{\sigma}_{t=1}^{i}=\boldsymbol{0}$, $\bar{Q}_{t=0}^{i}=\boldsymbol{0}$,
$W^{i}_{t=0}=0$ for all $i\in\mathcal{N}$.

3: for $t=1,2,\dots$ do

4: Observe Utility:

5:
$Q_{t}^{gap,i}(a)=W_{t-1}\max_{a^{*}\in\mathcal{A}^{i}}\left(\bar{Q}^{i}_{t-1}(a^{*})-\bar{Q}^{i}_{t-1}(a)\right)$

6: $Q^{i}_{t}(a)=u^{i}(a,\sigma_{t}^{-i})$

7: $S^{i}(a)=Q^{i}_{t}(a)-u^{i}\left(\sigma\right)$

8: if $S^{i}(a)>0$ then

9: $w^{i}_{t}(a)=Q_{t}^{gap,i}(a)/S^{i}(a)$

10: else

11: $w^{i}_{t}(a)=\inf$

12: end if

13: $w_{t}=\min_{i\in\mathcal{N}}\min_{a\in\mathcal{A}}w^{i}_{t}(a)$

14: $\alpha_{t}^{i}=\frac{w_{t}}{W_{t-1}+w_{t}}$

15:
$\bar{Q}_{t}^{i}=(1-\alpha_{t}^{i})\bar{Q}^{i}_{t-1}+\alpha_{t}^{i}Q^{i}_{t}$

16: Next Strategy:

17: $\sigma^{i}_{t+1}={\arg\max}_{a\in\mathcal{A}^{i}}\bar{Q}^{i}_{t}$

18: Update Average Strategy:

19:
$\bar{\sigma}_{t}^{i}(I)=(1-\alpha_{t}^{i})\bar{\sigma}_{t-1}^{i}(I)+\alpha_{t}^{i}\sigma_{t}^{i}(I)$

20: $W_{t}^{i}=W_{t-1}^{i}+w_{t}^{i}$

21: end for

In contrast to the complex calculations required in Greedy RM, the computation
of $w_{t}$ in DW-FP is simpler. It eliminates the need for intricate
optimization methods, greatly enhancing the practicality of algorithm
implementation. This simplicity is particularly advantageous considering that
DW-FP operates with an iteration complexity of only
$\mathscr{O}(|\mathcal{A}|)$, a significant improvement over RM’s
$\mathscr{O}(|\mathcal{A}|^{2})$. This efficiency highlights DW-FP’s
superiority, especially in large-scale applications where computational
resources and time are critical factors.

###  3.2 DW-PCFR

In the CFR algorithm, the strategy used in each iteration is a mixed strategy,
precluding the repetition of identical strategy profiles over multiple
iterations. In contrast, PCFR in extensive-form games utilizes pure strategies
in every iteration, allowing for the repetition of the same strategy profile
across multiple iterations. This distinct feature makes it feasible to apply
the DW-FP concept to PCFR in extensive-form games, potentially enhancing its
efficiency and effectiveness.

Algorithm 5 DW-PCFR(Ours)

1: Initialization:

2: Random initialization $\sigma_{t=1}(I)$. Set
$\bar{\sigma}_{t=1}^{i}(I)=\boldsymbol{0}$
$\bar{Q}_{t=0}^{i}(I)=\boldsymbol{0}$, $W^{i}_{t=0}(I)=0$ for all
$i\in\mathcal{N}$, $I\in\mathcal{I}$.

3: for $t=1,2,\dots$ do

4: for $\forall I\in\mathcal{I}$ do

5: Observe Utility:

6:
$\bar{Q}^{*i}_{t-1}(I)=\max_{a^{*}\in\mathcal{A}(I)}\bar{Q}_{t}^{i}(I,a^{*})$

7:
$Q_{t}^{gap,i}(I,a)=W^{i}_{t-1}(I)\left(\bar{Q}^{*i}_{t-1}(I)-\bar{Q}_{t}^{i}(I,a)\right)$

8:
$Q^{i}_{t}(I,a)=\pi_{\sigma_{t}}^{-i}(I)u^{i}\left(I,\sigma_{t}|_{I\rightarrow
a}\right)$

9:
$S^{i}(I,a)=\pi_{\sigma_{t}}^{-i}(I)\left(Q^{i}_{t}(I,\sigma_{t-1}^{i})-Q^{i}_{t}(I,a)\right)$

10: if $S^{i}(I,a)>0$ and $Q^{i}_{t}(I,a)>0$ then

11: $w^{i}_{t}(I,a)=Q_{t}^{gap,i}(I,a)/S^{i}(I,a)$

12: else

13: $w^{i}_{t}(I,a)=\inf$

14: end if

15:
$w_{t}=\min_{i\in\mathcal{N}}\min_{I\in\mathcal{I}^{i}}\min_{a\in\mathcal{A}(I)}w^{i}_{t}(I,a)$

16:
$\alpha_{t}^{i}(I)=\frac{\pi_{\sigma_{t}}^{i}(I)w_{t}}{W^{i}_{t-1}(I)+\pi_{\sigma_{t}}^{i}(I)w_{t}}$

17:
$\bar{Q}_{t}^{i}(I)=(1-\alpha_{t}^{i}(I))\bar{Q}^{i}_{t-1}(I)+\alpha_{t}^{i}(I)Q^{i}_{t}(I)$

18: Next Strategy:

19: $\sigma^{i}_{t+1}(I)={\arg\max}_{a\in\mathcal{A}^{i}}\bar{Q}^{i}_{t}(I,a)$

20: Update Average Strategy:

21:
$\bar{\sigma}_{t}^{i}(I)=(1-\alpha_{t})\bar{\sigma}_{t-1}^{i}(I)+\alpha_{t}\sigma_{t}^{i}(I)$

22: $W^{i}_{t}(I)=W^{i}_{t-1}(I)+\pi_{\sigma_{t}}^{i}(I)w^{i}_{t}$

23: end for

24: end for

In DW-PCFR 5, calculating the dynamic weights $w^{i}_{t}$ for each information
set adds little to the overall computational complexity. This approach
integrating iterations where PCFR’s strategy profiles repeat, without
affecting the convergence. A significant advantage of DW-PCFR is its ability
to process only $\mathscr{O}\left(|I|^{-\frac{1}{2}}\right)$ information sets
per iteration, compared to CFR+ which requires touching all
$\mathscr{O}\left(|I|\right)$ information sets. This efficiency makes DW-PCFR
suitable for larger-scale games, surpassing the adaptability of CFR+.

###  3.3 The Convergence Analysis of DW-FP/PCFR

The iterative process of DW-FP/PCFR is identical to that of FP/PCFR, clearly
establishing their convergence properties. The lower bound of their
convergence rate is the same as FP/PCFR’s, which is
$\mathcal{O}\left(T^{-\frac{1}{2}}\right)$. The crux of understanding DW-
PCFR’s efficiency lies in determining how many PCFR iterations equate to a
single DW-PCFR iteration. However, we lack a theoretical proof for this
equivalence. If Abernethy’s results can be generalized to extensive-form games
(Abernethy et al., 2021), then DW-FP/PCFR could potentially achieve a more
rapid lower bound convergence rate of $\mathcal{O}\left(T^{-1}\right)$, thus
significantly exceeding the performance of existing algorithms.

In extensive-form games, DW-PCFR distinguishes itself as a comprehensive full-
traversal algorithm, comparable to CFR+, while also embodying the
computational ease of Monte Carlo methods, such as MCCFR. Its fusion of pure
strategy execution and exhaustive traversal grants DW-PCFR the dual benefits
of hastened convergence and controlled computational complexity. In essence,
DW-PCFR combines the rapid convergence characteristic of full traversal
algorithms with the resource efficiency inherent in Monte Carlo methods.

###  3.4 Advantages of DW-FP/PCFR over Greedy RM

Greedy RM and DW-FP are both dynamic weight algorithms. We believe that there
are two reasons why Greedy RM is difficult to use in extensive-form games.

Firstly, in contrast to Greedy RM, which requires solving intricate
optimization problems to calculate dynamic weights, DW-FP’s use of pure
strategies considerably simplifies the computation of dynamic weights.

Secondly, To ensure convergence in extensive-form games, uniform dynamic
weights across all information sets are necessary (Zhang et al., 2022). Greedy
RM faces challenges in optimizing potential functions and must traverse all
information sets in a single iteration. We envision two methods for
calculating Greedy RM’s dynamic weights in extensive-form games.

Method 1 directly optimizing all information sets together:

$w_{t}^{i}=\min_{w^{\prime}}\sum_{I\in\mathcal{I}}\Phi\left(\left(1-\alpha^{i}_{t}(I)\right)\bar{R}_{t-1}^{i}(I)+\alpha^{i}_{t}(I)R_{t}^{i}(I)\right)$
(6)

where $\alpha^{i}_{t}(I)=\frac{w^{\prime}}{W_{t-1}^{i}(I)+w^{\prime}}$. This
is obviously unrealistic, even for some very simple games (such as Leduc with
288 information sets). This will make the potential function extremely complex
and impossible to optimize.

Method 2 calculates the dynamic weight of each information set separately as
Eq 7, and then obtain a final dynamic weight as Eq 8, which is similar to DW-
PCFR.

$w^{i}_{t}(I)=\min_{w^{\prime}}\Phi\left(\left(1-\alpha^{i}_{t}(I)\right)\bar{R}_{t-1}^{i}(I)+\alpha^{i}_{t}(I)R^{i}_{t}(I)\right)$
(7) $w_{t}^{i}=\min_{I\in\mathcal{I}}w^{i}_{t}(I)$ (8)

This method will traverse all $\mathscr{O}({|\mathcal{I}|})$ information sets
per iteration. In contrast, DW-PCFR only touched
$\mathscr{O}\left(|\mathcal{I}|^{-\frac{1}{2}}\right)$ information sets per
iteration. As a result, an iteration of DW-PCFR in practical applications is
significantly simpler than one of Greedy RM.

##  4 Experimental Results

Figure 2:  The figure illustrates the performance of various algorithms on 30
randomly generated two-player zero-sum games, with matrix payoff entries drawn
from a standard normal Gaussian distribution $N(0,1)$. Both axes of the plots
are on a logarithmic scale, where the time coordinate is expressed in
milliseconds. The shaded regions around each line represent the 95% confidence
interval. This setting will also be used in subsequent experiments.

Figure 3:  The figure illustrates the performance of various algorithms on
extensive-form two-player zero-sum games. The top row of the experiment’s
horizontal axis represents the number of iterations, while the bottom row
indicates the training time in milliseconds..

###  4.1 Game Description and Experimental Settings

Our experiments involved matrix games, variants of Kuhn poker (X card Y Pot
Kuhn poker) (Kuhn, 1950) and Leduc poker (X card Y Pot Leduc Poker) (Shi &
Littman, 2001), which are widely used for convergence rate testing.

For our analysis in normal-form games, we utilized algorithms such as FP, RM,
RM+, and Greedy RM to compare with the proposed DW-FP. In extensive-form
games, our comparisons included PCFR, CFR, and CFR+ to compare with the
proposed DW-PCFR. Each algorithm was evaluated across 30 runs to ensure
statistical reliability, using a single CPU core to standardize the computing
environment. Notably, Greedy RM and CFR+ have been recognized as particularly
powerful in their respective game categories. The selection of experiment
parameters was guided by established best practices (Brown, 2020; Zhang et
al., 2022). For more experimental results, please see Appendix A.

###  4.2 Two-Player Zero-Sum Normal-Form Games

In the experiment of two-player zero-sum random matrix games, the
computational complexity of FP algorithms per iteration is
$\mathscr{O}(|\mathcal{A}|)$. Conversely, RM algorithms exhibit a higher
complexity of $\mathscr{O}(|\mathcal{A}|^{2})$. As a result, relying solely on
iteration number as the metric for assessing FP algorithms does not offer an
equitable evaluation framework. Therefore, we chose to evaluate our algorithms
based on both the number of iterations and the computational time, aiming to
ensure a comprehensive and fair comparison.

Figure 2 shows that DW-FP has the fastest convergence rate, surpassing RM+
significantly in both iteration counts and time efficiency. RM+, together with
CFR+ in extensive-form games, is recognized for its enhanced convergence rate
and plug-and-play capability, frequently considered among the most effective
strategies in game theory learning. Nonetheless, DW-FP not only converges more
rapidly than RM+ but is also simpler to implement, making it a more
advantageous method. Furthermore, DW-FP achieves a convergence rate that is
more than an order of magnitude faster than that of Greedy RM. Given that the
convergence rates of Greedy RM and DW-FP appear similar when assessed by the
number of iterations, this implies that a single DW-FP iteration requires only
one-tenth the time of a Greedy RM iteration. This effectively highlights DW-
FP’s advantages for engineering implementations.

###  4.3 Two-Player Zero-Sum Extensive-Form Games

As shown in Figure 3, within the environments of Kuhn Poker (55 nodes and 12
information sets) and Leduc Poker (1945 nodes and 288 information sets), DW-
PCFR swiftly surpasses alternative algorithms, consistently achieving a
convergence rate of $\mathcal{O}(T^{-1})$.

In the case of 3 Card 5 Pots Leduc Poker, which encompasses 49,384 nodes and
6,399 information sets, DW-PCFR initially demonstrated a slower convergence
rate compared to CFR+. Yet, as time progressed, its convergence rate improved,
approaching $\mathcal{O}(T^{-1})$. Furthermore, allowing it to achieve faster
convergence when evaluated in terms of time.

###  4.4 The Convergence Rate of DW-FP/PCFR

If Karlin’s conjecture is valid (for which there are currently no known
counterexamples), the convergence rate of FP would be
$\mathcal{O}\left(T^{-\frac{1}{2}}\right)$. Given that DW-FP/PCFR and Vanilla
FP/PCFR are fundamentally the same in nature, the primary distinction lies in
the fact that DW-FP/PCFR omits several computational steps through the use of
dynamic weights. This raises a crucial question: How many Vanilla FP/PCFR
iterations are equivalent to a single iteration of DW-FP/PCFR?

Figure 4:  The figure depicts the correlation between the number of iterations
for DW-FP and FP

Figure 5:  The figure depicts the correlation between the number of iterations
for DW-PCFR and PCFR

As illustrated in Figure 4, 5, our analysis indicates that for simpler games,
such as the 10-action matrix game and Kuhn Poker, the iteration count for DW-
FP/PCFR is roughly the square of the iteration count for Vanilla FP/PCFR. In
more complex games, like the 1000-action matrix game and 5 Card Leduc Poker,
the correlation between the iterations of DW-FP/PCFR and Vanilla FP/PCFR
progressively mirrors a quadratic relationship. Our experimental data showing
that as training time increases, DW-FP/PCFR is likely to achieve a convergence
rate of $\mathcal{O}(T^{-1})$.

##  5 Conclusions and Future Work

We introduce two innovative approaches for solving two-player zero-sum games,
DW-FP and DW-PCFR. DW-FP is tailored for normal-form games, while DW-PCFR is
specifically designed for extensive-form games. Both methods stand out for
their use of dynamic weighting, a concept inspired by the Greedy RM algorithm.
Yet, they surpass Greedy RM with their simplicity, plug-and-play, faster
convergence rates, and tailored suitability for both normal and extensive form
games.

Our research confirms that DW-FP and DW-PCFR ensure a convergence rate of
$\mathcal{O}\left(T^{-\frac{1}{2}}\right)$. More notably, in the vast majority
of cases, these strategies exhibit convergence rates approaching
$\mathcal{O}(T^{-1})$, underlining their potent efficacy and efficiency in
solving NE.

Our future work will span both theoretical insights and practical
applications. On the theoretical front, it is essential to dissect the
conditions and underlying reasons that enable the convergence rate to approach
$\mathcal{O}(T^{-1})$. Additionally, investigating the connection between our
newly introduced DW-FP/PCFR methods and established algorithms such as Follow
the Regularized Leader (FTRL)(Shalev-Shwartz & Singer, 2007) and Online Mirror
Descent (OMD)(Farina et al., 2021) will be pivotal.

On the practical side, our goal is to integrate sampling with DW-PCFR to
expand its capabilities. Although DW-PCFR reduces the number of information
sets processed in each iteration, sampling remains indispensable for
addressing large-scale problems like Texas Hold’em poker. Our next step
involves combining sampling with DW-PCFR to tackle these more extensive
challenges effectively.

## References

  * Abernethy et al. (2011) Abernethy, J., Bartlett, P. L., and Hazan, E.  Blackwell approachability and no-regret learning are equivalent.  In _Proceedings of the 24th Annual Conference on Learning Theory_ , pp. 27–46. JMLR Workshop and Conference Proceedings, 2011.
  * Abernethy et al. (2021) Abernethy, J., Lai, K. A., and Wibisono, A.  Fast convergence of fictitious play for diagonal payoff matrices.  In _Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA)_ , pp. 1387–1404. SIAM, 2021.
  * Blackwell (1956) Blackwell, D.  An analog of the minimax theorem for vector payoffs.  1956\.
  * Blum & Mansour (2007) Blum, A. and Mansour, Y.  From external to internal regret.  _Journal of Machine Learning Research_ , 8(6), 2007.
  * Bowling et al. (2015) Bowling, M., Burch, N., Johanson, M., and Tammelin, O.  Heads-up limit hold’em poker is solved.  _Science_ , 347(6218):145–149, 2015.
  * Brown (1951) Brown, G. W.  Iterative solution of games by fictitious play.  _Act. Anal. Prod Allocation_ , 13(1):374, 1951\.
  * Brown (2020) Brown, N.  Equilibrium finding for large adversarial imperfect-information games.  _PhD thesis_ , 2020.
  * Brown & Sandholm (2015) Brown, N. and Sandholm, T.  Regret-based pruning in extensive-form games.  _Advances in neural information processing systems_ , 28, 2015.
  * Brown & Sandholm (2017) Brown, N. and Sandholm, T.  Safe and nested subgame solving for imperfect-information games.  _Advances in neural information processing systems_ , 30, 2017.
  * Brown & Sandholm (2019a) Brown, N. and Sandholm, T.  Solving imperfect-information games via discounted regret minimization.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 33, pp. 1829–1836, 2019a.
  * Brown & Sandholm (2019b) Brown, N. and Sandholm, T.  Superhuman ai for multiplayer poker.  _Science_ , 365(6456):885–890, 2019b.
  * Cesa-Bianchi & Lugosi (2006) Cesa-Bianchi, N. and Lugosi, G.  _Prediction, learning, and games_.  Cambridge university press, 2006.
  * Daskalakis & Pan (2014) Daskalakis, C. and Pan, Q.  A counter-example to karlin’s strong conjecture for fictitious play.  In _2014 IEEE 55th Annual Symposium on Foundations of Computer Science_ , pp. 11–20. IEEE, 2014.
  * Farina et al. (2021) Farina, G., Kroer, C., and Sandholm, T.  Faster game solving via predictive blackwell approachability: Connecting regret matching and mirror descent.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 35, pp. 5363–5371, 2021.
  * Fudenberg & Levine (1998) Fudenberg, D. and Levine, D. K.  _The theory of learning in games_ , volume 2.  MIT press, 1998.
  * Heinrich et al. (2015) Heinrich, J., Lanctot, M., and Silver, D.  Fictitious self-play in extensive-form games.  In _International conference on machine learning_ , pp. 805–813. PMLR, 2015.
  * Hernandez et al. (2019) Hernandez, D., Denamganaï, K., Gao, Y., York, P., Devlin, S., Samothrakis, S., and Walker, J. A.  A generalized framework for self-play training.  In _2019 IEEE Conference on Games (CoG)_ , pp. 1–8. IEEE, 2019\.
  * Karlin (2003) Karlin, S.  _Mathematical methods and theory in games, programming, and economics_ , volume 2.  Courier Corporation, 2003.
  * Kroer & Sandholm (2018) Kroer, C. and Sandholm, T.  A unified framework for extensive-form game abstraction with bounds.  _Advances in Neural Information Processing Systems_ , 31, 2018.
  * Kuhn (1950) Kuhn, H. W.  A simplified two-person poker.  _Contributions to the Theory of Games_ , 1:97–103, 1950\.
  * Lanctot et al. (2009) Lanctot, M., Waugh, K., Zinkevich, M., and Bowling, M.  Monte carlo sampling for regret minimization in extensive games.  _Advances in neural information processing systems_ , 22, 2009.
  * Leslie & Collins (2006) Leslie, D. S. and Collins, E. J.  Generalised weakened fictitious play.  _Games and Economic Behavior_ , 56(2):285–298, 2006.
  * Papadimitriou (1994) Papadimitriou, C. H.  On the complexity of the parity argument and other inefficient proofs of existence.  _Journal of Computer and system Sciences_ , 48(3):498–532, 1994.
  * Qi et al. (2023) Qi, J., Feng, T., Hei, F., Fang, Z., and Luo, Y.  Pure monte carlo counterfactual regret minimization.  _arXiv preprint arXiv:2309.03084_ , 2023.
  * Robinson (1951) Robinson, J.  An iterative method of solving a game.  _Annals of mathematics_ , pp. 296–301, 1951.
  * Shalev-Shwartz & Singer (2007) Shalev-Shwartz, S. and Singer, Y.  A primal-dual perspective of online learning algorithms.  _Machine Learning_ , 69(2-3):115–142, 2007.
  * Shi & Littman (2001) Shi, J. and Littman, M. L.  Abstraction methods for game theoretic poker.  In _Computers and Games: Second International Conference, CG 2000 Hamamatsu, Japan, October 26–28, 2000 Revised Papers 2_ , pp. 333–345. Springer, 2001.
  * Tammelin (2014) Tammelin, O.  Solving large imperfect information games using cfr+.  _arXiv preprint arXiv:1407.5042_ , 2014.
  * Vinyals et al. (2019) Vinyals, O., Babuschkin, I., Czarnecki, W. M., Mathieu, M., Dudzik, A., Chung, J., Choi, D. H., Powell, R., Ewalds, T., Georgiev, P., et al.  Grandmaster level in starcraft ii using multi-agent reinforcement learning.  _Nature_ , 575(7782):350–354, 2019.
  * Zhang et al. (2022) Zhang, H., Lerer, A., and Brown, N.  Equilibrium finding in normal-form games via greedy regret minimization.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 36, pp. 9484–9492, 2022.
  * Zinkevich et al. (2007) Zinkevich, M., Johanson, M., Bowling, M., and Piccione, C.  Regret minimization in games with incomplete information.  _Advances in neural information processing systems_ , 20, 2007.

##  Appendix A Supplementary Experimental Results

###  A.1 Kuhn-extension/Leduc-extension poker

We have made improvements to Kuhn and Leduc Poker:

  1. 1.

The original Leduc and Kuhn poker types are 3 cards, and in the improved game
the types are $x\geq 3$ cards;

  2. 2.

The original Leduc and Kuhn can only raise one fixed chip, but in the improved
game it is allowed to raise $y\geq 1$ chips of various sizes. The Bet Action
raise size here adopts an equal proportional sequence in multiples of 2. For
example, when the blind bet is 1 and $y=4$, the allowed raise action is [1, 2,
4, 8];

###  A.2 Additional Experimental Results

Figure 6:

Figure 7:

Figure 8:


#  “Two Many Cooks”: Understanding Dynamic Human - Agent Team Communication
and Perception Using Overcooked 2

Andres Rosero, Faustina Dinh, Ewart J. de Visser, Tyler Shaw, Elizabeth
Phillips

###### Abstract

This paper describes a research study that aims to investigate changes in
effective communication during human-AI collaboration with special attention
to the perception of competence among team members and varying levels of task
load placed on the team. We will also investigate differences between human-
human teamwork and human-agent teamwork. Our project will measure differences
in the communication quality, team perception and performance of a human actor
playing a Commercial Off - The Shelf game (COTS) with either a human teammate
or a simulated AI teammate under varying task load. We argue that the
increased cognitive workload associated with increases task load will be
negatively associated with team performance and have a negative impact on
communication quality. In addition, we argue that positive team perceptions
will have a positive impact on the communication quality between a user and
teammate in both the human and AI teammate conditions. This project will offer
more refined insights on Human - AI relationship dynamics in collaborative
tasks by considering communication quality, team perception, and performance
under increasing cognitive workload.

## Introduction

As a result of decades of innovation in the field of artificial intelligence,
collaborative efforts between human and AI ‘agents’ have emerged across
several fields. These human-agent teams (HATs) have been utilized to great
success in fields like healthcare, military operations and education. Although
human-agent teaming has become an expanding area of research and practice,
there are still significant gaps in knowledge of how humans and autonomous
agents work together in realistic, dynamic situations (O’Neill et al. 2020).
In particular, team processes like communication used when humans are working
with autonomous agents may differ from humans working with other humans, and
these differences may be especially apparent when teams encounter increasingly
difficult and complex tasking and cognitive load. Research into human-human
teams has shown that changes in cognitive workload inherent with more
difficult tasking causes changes in communication amongst team members (Urban
et al. 1996; Xiao et al. 2003). Further, high performing human-human teams
show patterns of communication that make their performance resilient to such
changes in team workload that low performing teams do not (Converse, Cannon-
Bowers, and Salas 1993). When interacting in teams with autonomous agents,
prior research has also revealed that human team members engage in fewer
communications with autonomous teammates as compared to their human
counterparts (Walliser et al. 2019). Such sub-optimal team communication
processes can hinder the ability of the team to be resilient to changes in
task and cognitive load and thus diminish performance of the team overall. In
addition, when autonomous agents were framed and perceived as an interactive
teammate and not simply an automated tool, participant communication with the
autonomous increased significantly, and overall team performance was improved
(Walliser et al. 2019). Taken together, these findings suggest that human
perceptions of their artificial team members may be an important contributor
to team processes and overall team performance. However, one notable gap in
HAT research has been the influence of cognitive workload on team dynamics.
Previous HAT research has focused on differences in perception in tasking
where workload has been static, yet understanding team dynamics in situations
with varying workload would have much greater ecological validity with real
life human-agent teams completing tasks with varying difficulty across the
lifespan of the team.

Thus, the purpose of this research is to investigate differences in team
communication, team perception, and team performance between teams composed of
humans and humans and artificial agents working together across varying levels
of task load. In the following sections, we report progress on a research
study where human actors will play a commercial off-the-shelf (COTS)
cooperative video game, Overcooked 2, with either another human or a simulated
autonomous teammate.

## Background

### Human-Agent Team Dynamics

There is inconsistency between human - human team perceptions and Human-agent
team perceptions. Such was demonstrated in research led by Ashktorab in 2020,
where although few differences were seen in performance between human-agent
and human-human teams in a word guessing game, human participants perceived
the agent teammates as less intelligent and likeable (Ashktorab et al. 2020).
A research group led by O’Neill in 2020 conducted an extensive literature
review of HATs and found that although human - human teams overall had higher
levels of performance compared to HATs, higher levels of interdependence and
greater levels of communication among HATs led to stronger coordination among
members and greater team functioning.

Extensive literature on human-human teams has shown that communication between
collaborative members is important for team performance especially for
distributing information and formulating strategies (Marlow et al. 2018).
Consequently, if a comparison between human - human teams and human - agent
teams is to be made, communication becomes a fundamental concern when
evaluating HATs performance. Mou and Xu (2017) explored the initial stages of
human communication with AI in comparison to human-human communications. The
data revealed that the participants were less open and agreeable when
interacting with AI than with other humans (Mou and Xu 2017). These findings
reiterate the necessity for further research on human-agent communication,
specifically regarding how it may impact performance.

### Input - Mediator - Output - Input Model

The Input - Mediator - Output - Input (IMOI) model is an extension of the
highly influential Input - Process - Output (IPO) model of team effectiveness
posited by Hackman and Morris in 1975. The IMOI model expands upon the IPO by
establishing that team processes are a complex system that involve
interactions among inputs, outputs and mediators,not a causal chain from one
process to the next (Ilgen et al. 2005). For the purposes of this study, we
focus on the IMOI in the context of virtual teams, a subfield that studies
teams in which members are not co - located in the same environment and must
operate virtually.

Explanations of the IMOI in the context of virtual teams have focused on the
importance of communication as a key process towards the overall effectiveness
of the virtual team (Marlow, Lacerenza, and Salas 2017). In 2017, Marlow and
associates distinguished key attributes of communication which hold
significance in team processes. Among these include communication frequency
(how often team members communicate amongst themselves) and communication
quality (an analysis of the clarity and effectiveness of interactions among
team members). Due to the lack of pertinent direct and indirect interaction
correlates such as non-verbal cues and body language (Dulebohn and Hoch 2017),
the interplay between communication frequency and communication quality become
integral to developing trust and cohesion among team members (Dulebohn and
Hoch 2017). In addition, studies have noted that key aspects of the IMOI
involve input processes such as team diversity (including teammate
demographics and personality), mediators including task complexity and
outcomes involving team performance and team satisfaction (Liu, Yan, and Sun
2010; Dulebohn and Hoch 2017; Marlow, Lacerenza, and Salas 2017).

This study will leverage the IMOI virtual team framework to discern how team
diversity (human v AI collaborator) affects processes of team effectiveness
such as communication, perceptions of competence and performance while
adjusting task complexity.

Dependent Measures | Description
---|---
Communication Quality | Ratio: number of participant commands accepted by teammate in a level divided
| by total participant commands
Communication Frequency | Total instructions
Team Perception | Combination of seven point team affect and team cohesion scales (Bishop et al. 2020)
Cognitive Workload | NASA-TLX (Hart and Staveland 1988)
| Gas Tank Questionnaire (Monfort et al. 2018)
Task Load | Operationally defined from analysis of stimuli in each level based on a set list of criteria
Level score | End of level score provided by Overcooked 2
Positive Chef Actions (PCA) | The total sum of all actions that culminate in the creation of a dish in a given
| Overcooked 2 level (Bishop et al. 2020)
Chef Role Contribution (CRC) | The relative proportion of confederate PCAs subtracted from the relative proportion of
| participant PCAs. Positive CRCs indicate that the participant contributes
more, negative
| CRCs that the confederate contributes more (Bishop et al. 2020)
Table 1: List of Planned Project Measures and their descriptions

### Commercial Off the Shelf (COTS) Games

COTS games like Starcraft II (Vinyals et al. 2019) and Hanabi (Eger, Martens,
and Córdoba 2017) have been utilized in an increasing number of human-agent
teaming studies due to the gamification of communication and immersion
necessary to obtain dedicated participation from participants. The division of
labor and reliance on cooperation in game play to complete objectives makes it
crucial for communication and interaction between teammates to occur -
allowing researchers the opportunity to track changes in communication quality
across tasking and game play. COTS games also allow researchers the ability to
easily define performance within the context of the game. Additionally, a
number of AI researchers have created approximations of COTS games to
investigate models or human-agent coordination (Carroll et al. 2019; Gao et
al. 2020; Song et al. 2019; Wu et al. 2021).

Figure 1: Screen capture of Overcooked 2 game play

Overcooked 2 (Figure 1) is a cooperative COTS game that relies on task
asymmetry and frequent task reassignment in order to complete as many food
orders as possible in a simulated restaurant within a predefined time limit.
By requiring frequent division of labor to complete orders, Overcooked 2
encourages teamwork and communication among team members to complete orders
promptly and gain high scores.

The Cooking with Humans and Autonomy in Overcooked! 2 for studying Performance
Teaming (CHAOPT) test-bed devised by a research group led by Bishop in 2020
determined that Overcooked 2 could be utilized as a viable platform for
testing team processes such as communication, perception and performance
(Bishop et al. 2020). This work derived individual and team performance
measures that could be gathered in-game and validated that these measures were
sensitive to changes in level difficulty.

Current research involving human - agent teams in COTS games has not discussed
how changing task load affects team dynamics such as communication as a
function of participant perception and its effect on team performance. Task
load measures the amount of stimuli and objectives present in a given task and
influences the subjective cognitive workload of team members in a given task.
In essence, as the amount of objectives and stimuli present in a given
environment increase, there is an increase in the cognitive resource required
to meet performance demands. Research has shown that increased workload has
significant effects on communication among team members (Marlow et al. 2018)
and high functioning teams consistently show the ability to adapt their
communication styles based on the difficulty of the task as well as the
perception of team members confidence in the competence of other members to
complete tasking (Wynne and Lyons 2018). By manipulating task load, this study
will expand upon current COTS human - agent team research by examining dynamic
team mechanics in varying task conditions, mirroring real life team
objectives. We aim to see how human perceptions of the competence of a
perceived AI teammate compared to a human teammate affect communication and
performance as workload increases in accordance with the IMOI model of team
effectiveness.

### Hypotheses

Based on the review of previous research, the following hypotheses are
proposed:

  * •

H1: Increased cognitive workload will be negatively associated in Overcooked
team performance, such that as task load increases cognitively overworked,
Overcooked scores will suffer.

  * •

H2: Positive team perceptions will have a positive impact on the communication
quality between user and teammate in both the human and agent teammate
condition.

  * •

H3: Increased task load will negatively affect communication quality in both
the human and agent conditions.

    * –

H3.1: Communication quality will degrade at a greater level for the agent
condition than human condition as a function of human perception towards
teammate.

  * •

H4: Increased task load will negatively affect task performance in both human
and agent teammate conditions.

    * –

H4.1: Performance will be worse for the agent condition than human condition
as a function of human perception towards teammate.

## Proposed Methods

### Participants

We aim for a sample size of approximately 102 participants for this study in
accordance with an a prior power analysis with a medium effect size.
Participants will be recruited via Overcooked online forums on Reddit, Steam
and Discord—targeting players who have completed the Overcooked 2 story mode
and have access to online play on their computer and a working microphone.
Only participants with Overcooked 2 experience will be recruited as a means of
selecting players that could be capable of providing concise instruction to a
confederate with knowledge of the game’s mechanics.

### Measures

Multiple existing subjective state scales and objective measures of process
and performance will be employed before, during and after game play (See Table
1). We will use objective measures of team communication quality and frequency
between teammates as well as objective measures of individual and team
performance. Communication Quality is defined as the percentage of commands
issued by the participant that were acknowledged and executed by the
confederate. We will also include subjective measures of cognitive workload
associated with changes in task load difficulty across game levels and
subjective perceptions of the team itself (e.g., team affect, team cohesion).

### Wizard of Oz paradigm

The Wizad of Oz (WoZ) paradigm is a common method for comparing perceptions
between human-human and human - agent teams by controlling the capabilities of
each teammate group (Musick et al. 2021). The WoZ paradigm will be used to
simulate agent activity with a human confederate simulating game play of an
autonomous agent.By incorporating a WoZ paradigm, all reported differences in
perception of competence across groups will be derived solely from the
participant’s belief in the identity of their teammate and not from the
abilities of the teammate itself (Musick et al. 2021).This study will
implement a WoZ paradigm via online play - a human confederate will play as
both a human and AI teammate. Communication from the confederate across both
groups will be limited to only the emoticon system in Overcooked. The
participant will be required to relay all commands verbally, and the
confederate will respond with emoticons.

### Procedures

Once recruited, participants will begin by completing an informed consent
form. After consenting, participants will then be asked to view a short
presentation detailing the tasks that participants will be expected to
complete and instructions on how to communicate commands to the confederate
teammate. Participants will interact with an experimenter guiding them through
these materials remotely using Zoom, and Zoom will be used to audio and video
record participant game play. Then, participants will be asked to complete a
baseline measure of cognitive workload, the NASA-TLX, as well as a
demographics survey containing questions pertaining to age and gender as well
as experience with AI and with Overcooked 2. Materials will be prepared using
the online study administration software, Qualtrics. Participants will be
randomly assigned to two groups - a human teammate condition and an AI
teammate condition.

Participants will enter into an online multiplayer game of Overcooked 2 and
complete 6 experimental levels, three levels will be low task load levels and
three will be high task load levels. For each participant, the first level
will always be the tutorial level to introduce players to game play with the
confederate and establish a baseline level of performance. The order of
completion of the remaining 6 levels will be pseudo-randomized across
participants using a Latin square design. After each level, participants will
complete the the Gas Tank Questionnaire of subjective cognitive workload as
well as the team perception measures. The experimenter will also video and
audio record all game play in each level which will provide a recording of
communication and individual and team performance. Once all levels are
complete, participants will be asked to complete a one question manipulation
check to discern if participants believed they were playing with an AI
teammate as well as a post-task team perception survey, debriefed, and then
compensated for their participation. All procedures will be reviewed by George
Mason University’s Institutional Review Board.

## Discussion and importance to HRI reseach

This research is designed to enrich our understanding of human-agent team
processes in dynamic tasks with fluctuating task load. We plan to investigate
the relationships between task and workload on team communication, perceptions
of the team, and team performance and their comparisons to human-human teams.
We hope to find significant changes in communication styles towards agent
teammates as task loads increase as well as differences in communication and
task performance relative to the Human - Human teams and influenced by
participant perception of their teammate.

There is some debate on the generalizability of HAT research to HRI domains
because some claim that the physical embodiment of robots can alter their
relationships with humans compared to disembodied AI counterparts (O’Neill et
al. 2020). We believe that the findings of this project will translate to
Human-Robot interactions. As researchers like Nass and Scheutz have
demonstrated, the dynamics by which Humans perceive non-human teammates with
comparable trust and coordination as human counterparts is ubiquitous
regardless of the form of the non-human teammate (Nass, Fogg, and Moon 1996;
Scheutz, DeLoach, and Adams 2017). Further, artificial agents may be able to
fluidly move into/out of and between ”bodies” in the future (Williams et al.
2021) and doing so will likely influence long term team interactions (De
Visser et al. 2020) over time. By investigating team dynamics in adaptive task
load in HATs, we gain an understanding of changes in human communication and
perception that vary across task loads that we can utilize to apply to similar
tasking with robotic agents. As both artificial agents and embodied robots
become increasingly used as operational teammates (Phillips et al. 2011), it
will be important to understand the differences in how people engage in team
process behaviors with these agents and consequently how we can encourage team
process behaviors that will lead to good performance of the human-agent team
overall.

We envision the findings of this project to be a precursor for future HAT and
HRI research. Projects of this kind would include robots assisting humans in
increasingly difficult tasks and analyzing how human perception of the robot
affects their communication towards the robot as well as the overall
performance as tasking becomes more complex.

## References

  * Ashktorab et al. (2020) Ashktorab, Z.; Liao, Q. V.; Dugan, C.; Johnson, J.; Pan, Q.; Zhang, W.; Kumaravel, S.; and Campbell, M. 2020.  Human-ai collaboration in a cooperative game setting: Measuring social perception and outcomes.  _Proceedings of the ACM on Human-Computer Interaction_ 4(CSCW2): 1–20.
  * Bishop et al. (2020) Bishop, J.; Burgess, J.; Ramos, C.; Driggs, J. B.; Williams, T.; Tossell, C. C.; Phillips, E.; Shaw, T. H.; and de Visser, E. J. 2020.  CHAOPT: a testbed for evaluating human-autonomy team collaboration using the video game overcooked! 2.  In _2020 Systems and Information Engineering Design Symposium (SIEDS)_ , 1–6. IEEE.
  * Carroll et al. (2019) Carroll, M.; Shah, R.; Ho, M. K.; Griffiths, T.; Seshia, S.; Abbeel, P.; and Dragan, A. 2019.  On the utility of learning about humans for human-ai coordination.  _Advances in Neural Information Processing Systems_ 32: 5174–5185.
  * Converse, Cannon-Bowers, and Salas (1993) Converse, S.; Cannon-Bowers, J.; and Salas, E. 1993.  Shared mental models in expert team decision making.  _Individual and group decision making: Current issues_ 221: 221–46.
  * De Visser et al. (2020) De Visser, E. J.; Peeters, M. M.; Jung, M. F.; Kohn, S.; Shaw, T. H.; Pak, R.; and Neerincx, M. A. 2020.  Towards a theory of longitudinal trust calibration in human–robot teams.  _International journal of social robotics_ 12(2): 459–478.
  * Dulebohn and Hoch (2017) Dulebohn, J. H.; and Hoch, J. E. 2017.  Virtual teams in organizations.
  * Eger, Martens, and Córdoba (2017) Eger, M.; Martens, C.; and Córdoba, M. A. 2017.  An intentional ai for hanabi.  In _2017 IEEE Conference on Computational Intelligence and Games (CIG)_ , 68–75. IEEE.
  * Gao et al. (2020) Gao, X.; Gong, R.; Zhao, Y.; Wang, S.; Shu, T.; and Zhu, S.-C. 2020.  Joint mind modeling for explanation generation in complex human-robot collaborative tasks.  In _2020 29th IEEE International Conference on Robot and Human Interactive Communication (RO-MAN)_ , 1119–1126. IEEE.
  * Hart and Staveland (1988) Hart, S. G.; and Staveland, L. E. 1988.  Development of NASA-TLX (Task Load Index): Results of empirical and theoretical research.  In _Advances in psychology_ , volume 52, 139–183. Elsevier.
  * Ilgen et al. (2005) Ilgen, D. R.; Hollenbeck, J. R.; Johnson, M.; and Jundt, D. 2005.  Teams in organizations: From input-process-output models to IMOI models.  _Annu. Rev. Psychol._ 56: 517–543.
  * Liu, Yan, and Sun (2010) Liu, Y.; Yan, X.; and Sun, Y. 2010.  A meta-analysis of virtual team communication based on IPO model.  In _Proceedings of the 1st International Conference on E-Business Intelligence (ICEBI2010), Kunming, doi_ , volume 10.
  * Marlow et al. (2018) Marlow, S. L.; Lacerenza, C. N.; Paoletti, J.; Burke, C. S.; and Salas, E. 2018\.  Does team communication represent a one-size-fits-all approach?: A meta-analysis of team communication and performance.  _Organizational Behavior and Human Decision Processes_ 144: 145–170.
  * Marlow, Lacerenza, and Salas (2017) Marlow, S. L.; Lacerenza, C. N.; and Salas, E. 2017.  Communication in virtual teams: A conceptual framework and research agenda.  _Human Resource Management Review_ 27(4): 575–589.
  * Monfort et al. (2018) Monfort, S. S.; Graybeal, J. J.; Harwood, A. E.; McKnight, P. E.; and Shaw, T. H. 2018.  A single-item assessment for remaining mental resources: development and validation of the Gas Tank Questionnaire (GTQ).  _Theoretical Issues in Ergonomics Science_ 19(5): 530–552.
  * Mou and Xu (2017) Mou, Y.; and Xu, K. 2017.  The media inequality: Comparing the initial human-human and human-AI social interactions.  _Computers in Human Behavior_ 72: 432–440.
  * Musick et al. (2021) Musick, G.; O’Neill, T. A.; Schelble, B. G.; McNeese, N. J.; and Henke, J. B. 2021\.  What Happens When Humans Believe Their Teammate is an AI? An Investigation into Humans Teaming with Autonomy.  _Computers in Human Behavior_ 122: 106852.
  * Nass, Fogg, and Moon (1996) Nass, C.; Fogg, B.; and Moon, Y. 1996.  Can computers be teammates?  _International Journal of Human-Computer Studies_ 45(6): 669–678.
  * O’Neill et al. (2020) O’Neill, T.; McNeese, N.; Barron, A.; and Schelble, B. 2020.  Human–autonomy teaming: A review and analysis of the empirical literature.  _Human Factors_ 0018720820960865\.
  * Phillips et al. (2011) Phillips, E.; Ososky, S.; Grove, J.; and Jentsch, F. 2011.  From tools to teammates: Toward the development of appropriate mental models for intelligent robots.  In _Proceedings of the Human Factors and Ergonomics Society Annual Meeting_ , volume 55, 1491–1495. SAGE Publications Sage CA: Los Angeles, CA.
  * Scheutz, DeLoach, and Adams (2017) Scheutz, M.; DeLoach, S. A.; and Adams, J. A. 2017.  A framework for developing and using shared mental models in human-agent teams.  _Journal of Cognitive Engineering and Decision Making_ 11(3): 203–224.
  * Song et al. (2019) Song, Y.; Wang, J.; Lukasiewicz, T.; Xu, Z.; and Xu, M. 2019.  Diversity-driven extensible hierarchical reinforcement learning.  In _Proceedings of the AAAI conference on artificial intelligence_ , volume 33, 4992–4999.
  * Urban et al. (1996) Urban, J. M.; Weaver, J. L.; Bowers, C. A.; and Rhodenizer, L. 1996.  Effects of workload and structure on team processes and performance: Implications for complex team decision making.  _Human Factors_ 38(2): 300–310.
  * Vinyals et al. (2019) Vinyals, O.; Babuschkin, I.; Czarnecki, W. M.; Mathieu, M.; Dudzik, A.; Chung, J.; Choi, D. H.; Powell, R.; Ewalds, T.; Georgiev, P.; et al. 2019.  Grandmaster level in StarCraft II using multi-agent reinforcement learning.  _Nature_ 575(7782): 350–354.
  * Walliser et al. (2019) Walliser, J. C.; de Visser, E. J.; Wiese, E.; and Shaw, T. H. 2019.  Team structure and team building improve human–machine teaming with autonomous agents.  _Journal of Cognitive Engineering and Decision Making_ 13(4): 258–278.
  * Williams et al. (2021) Williams, T.; Ayers, D.; Kaufman, C.; Serrano, J.; and Roy, S. 2021.  Deconstructed Trustee Theory: Disentangling Trust in Body and Identity in Multi-Robot Distributed Systems.  In _Proceedings of the 2021 ACM/IEEE International Conference on Human-Robot Interaction_ , 262–271.
  * Wu et al. (2021) Wu, S. A.; Wang, R. E.; Evans, J. A.; Tenenbaum, J. B.; Parkes, D. C.; and Kleiman-Weiner, M. 2021.  Too Many Cooks: Bayesian Inference for Coordinating Multi-Agent Collaboration.  _Topics in Cognitive Science_ 13(2): 414–432.
  * Wynne and Lyons (2018) Wynne, K. T.; and Lyons, J. B. 2018.  An integrative model of autonomous agent teammate-likeness.  _Theoretical Issues in Ergonomics Science_ 19(3): 353–374.
  * Xiao et al. (2003) Xiao, Y.; Seagull, F. J.; Mackenzie, C.; Ziegert, J.; and Klein, K. J. 2003.  Team communication patterns as measures of team processes: Exploring the effects of task urgency and shared team experience.  In _Proceedings of the human factors and ergonomics society annual meeting_ , volume 47, 1502–1506. SAGE Publications Sage CA: Los Angeles, CA.