\subsection{Star network}

Consider a star network of $n$ players with player 1 in the center. Without loss of generality we assume $s_1 = 1$ and $j \in \ccalS_0$ for $j \notin \{1\}$---see Figure \ref{fig:bipartite}. 




\begin{proposition} \label{thm_star_dynamicMPCAC}
The optimal dynamic MPCAC solutions for the star network are as follows. 
\begin{itemize}
\item[(a)] If $1>c_0$ and $1>c_1 (n-1)$, then
\begin{equation}
	\begin{cases}\ccalX^t =\varnothing, \ &\text{if } t < n \\ \ccalX^t =\{1\}, \delta_1^t = 0 &\text{if } t\geq n  \end{cases}
\end{equation}
The resulting optimal cost is $C^* = 1$.
\item[(b)] If $1<c_0$ and $1>c_1 (n-1)$, or $1>c_0$ and $1<c_1 (n-1)$, then $\ccalX^t = \varnothing$ for all $t$.
The resulting optimal cost is $C^* = 0$.
\item[(c)] If $1<c_0$ and $1<c_1 (n-1)$, then $\ccalX^1 = \{1\}$.
\begin{equation}
	\begin{cases}\ccalX^t =\{1\}, \delta_1^t = 0 \ &\text{if } t =0,1 \\ \ccalX^t =\varnothing &\text{if } t > 1  \end{cases}
\end{equation}
The resulting optimal cost is $C^* = 2/n$.
\end{itemize}
\end{proposition}
\begin{myproof}
In cases (a) and (b), the game is dominance solvable. Further, the algorithm converges in $t\leq 2$ steps. Lemma \ref{thm_dominance_solvable} together with Theorem \ref{thm_vertex_cover} gives the optimal policies (a) and (b), respectively. 
In case (c), the game is not dominance solvable and there exists two Nash equilibria belonging to $M(\ccalG_B)$: $(a_1=0,\{a_i=1\}_{i\neq 1})$ and $(a_1 = 1, \{a_i=0\}_{i\neq 1})$. By Lemma \ref{thm_anti_coordination_equilibria}, the optimal policy will induce the dynamics to converge to one of these configurations. Either of these equilibria can be achieved through a dynamic policy that targets only the center node for two time steps, which gives the optimal cost $2/n$. For instance, we set $\delta_1^0= 0$  so that fringe players select $a_i^1=1$.  We continue with $\delta_1^1 = 0$, so that the center node's unforced action is 0 by \eqref{best_case_bad_response}. We lift the control for all $t\geq 2$, by which time the players are in equilibrium and MAC is achieved. This policy is optimal because there cannot be a policy that achieves a smaller objective value than $2/ n$ and achieve MAC.
\end{myproof}

The above analysis exemplifies the three uncontrolled action profiles \eqref{eq_action_profile_k} that can arise in a star network: (a) all players decide but MAC is not satisfied; (b) MAC is satisfied; (c)  all players remain undecided. In case (a), we control center player to induce MAC. In case (b), no control is necessary. In case (c), we control the center player to trigger decisions for the fringe players. 



\subsection{Line network}

 We consider a line network in which the neighborhood of player $i\in\ccalN \setminus \{1,n\}$ is given by $\ccalN_i=\{i-1,i+1\}$. The players at the endpoints have neighbor sets $\ccalN_1 = \{2\}, \ccalN_n = \{n-1\}$.  The type configuration alternates between types 0 and 1: $i \in \ccalS_0$ for $i$ odd, and $i\in\ccalS_1$ for $i$ even. We will also refer to the subsets $\ccalS_m^{\text{odd}}, \ccalS_m^{\text{even}}$ for $m\in\{0,1\}$ to denote every odd (even) player from the set $\ccalS_m$ along the line. In the following, we consider all possible payoff cases for the line network.
 





\begin{proposition}\label{dynamic_odd_line}
	Depending on the utility constants $c_0$ and $c_1$, the optimal control policy $(\{\ccalX^t\},\Delta)$ for the dynamic MPCAC problem on a line network with $n$ odd  is
	\begin{itemize}
		\item[a)] If $1 > 2c_0$ and $1 > 2c_1$, then 
		\begin{equation}
			\begin{cases}\ccalX^t =\varnothing \ &\text{if } t <n \\ \ccalX^t =\ccalS_1, \{\delta_i^t\}_{i\in \ccalS} = 0 &\text{if } t \geq n  \end{cases}
		\end{equation}
		which gives the optimal cost $C^* =  \lfloor n/2 \rfloor$.
		\item[b)] If $1 > 2c_0$ and $2c_1 > 1 > c_1$, then $\ccalX^t = \varnothing$ for all $t \geq 0$.
		\item[c)] If $1 > 2c_0$ and $c_1 > 1$, then $\ccalX^t = \varnothing$ for all $t \geq 0$.
		\item[d)] If $2c_0 > 1 > c_0$ and $2c_1 > 1 > c_1$, then
		\begin{equation}
			\begin{cases}\ccalX^t = \ccalS_1^{\text{even}}, \delta_{\ccalX^t}^t = 0 \ &\text{if } t =0,1 \\ \ccalX^t =\varnothing &\text{if } t > 1  \end{cases}
		\end{equation}
		which gives the optimal cost $C^* =  2\lfloor n/4 \rfloor/n$.
		\item[e)] If $c_0 > 1$ and $2c_1 > 1 > c_1$, then
		\begin{equation}
			\begin{cases}\ccalX^t = \{i\}, \delta_i^t = s_i \ &\text{if } t =0,1 \\ \ccalX^t =\varnothing &\text{if } t > 1  \end{cases}
		\end{equation}
		for any $i \in \ccalN$. This gives the optimal cost $C^* =  2/n$.
		\item[f)] Suppose $c_0 > 1$ and $c_1 > 1$.  Then 
		\begin{equation}
			\begin{cases}\ccalX^t = \ccalS_0^{\text{even}}, \delta_{\ccalX^t}^t = 1 \ &\text{if } t =0,1 \\ \ccalX^t =\varnothing &\text{if } t > 1  \end{cases}
		\end{equation}
		 gives the optimal cost $C^* =  2\lceil (n-1)/4 \rceil/n$.
	\end{itemize}
\end{proposition}

\noindent The optimal control policies vary depending on the payoff constants. If all players decide to play action 1 as a result of the learning process, then we solve a minimum vertex covering problem along the lines of Theorem \ref{thm_vertex_cover}, and the players selected have to be controlled for all times $t\geq n$---case (a) in all of the propositions in this section. If the game is dominance solvable and all links are inactive in the equilibrium action profile, the optimal policy is the empty set---see \ref{thm_star_dynamicMPCAC}(b),  \ref{dynamic_odd_line}(b,c). If a subset of players remain undecided as a result of the learning algorithm and all links between decided players are inactive, an optimal policy can be found by leveraging Lemma \ref{thm_anti_coordination_equilibria}. In the benchmark examples, these policies required controlling a subset of the players for two time steps, causing the undecided players in the other type to decide in the first step and the controlled players to consolidate their decisions in the second time step.
Consequently, we can control a smaller subset of players and leverage the learning dynamics to create cascades of decision-making---see cases (d-f) in Propositions \ref{dynamic_odd_line}. In the latter scenarios, the policy suggested by Theorem \ref{thm_vertex_cover} is an upper bound of the optimal policy. The optimal static policies are similar to the dynamic MPCAC policies presented here.
\subsection{Proof of Lemma \ref{lem_est}} \label{ap_pr_2}
\begin{comment}
By Lemma \ref{lem_cond} it holds, $|| f^i_i(t)-\bbe_k||< \xi_1$ and $|| f^j_i(t)-\bbe_k||< \xi_2$ as the result of consecutively taking same action $\bbe_k$ and successful communication attempts by agent $i$ as described. Then, using Assumption \ref{as_max}, there exists a constant $L >0$, $\text{for all\ }{i} \in \ccalN$ such that, the following holds,
\end{comment}
Since the expectation of the utility function $u_i: \ccalA^N \rightarrow \reals$ is linear and Lipschitz continuous $\text{for all\ }{i} \in \ccalN$, there exists a constant $L >0$ $\text{for all\ }{i} \in \ccalN$ such that the following holds, 
\begin{align} \label{eq_lip_up_bound}
    |u_i(a_i,f^i_{-i}(t)-u_i(a_i,a_{-i})|& 
    \le L ||a_{-i}-f^i_{-i}(t) ||,\\
    &=L\sum_{j \in \ccalN \setminus \{i\}}||a_j-f^i_{j}(t)||,\\
    &\le {L (N-1)\xi < \frac{{{\mu}}}{2}}, \label{eq_lipschitz}
\end{align}
for some $\mu>0$. Next, we define the following mutually exclusive subsets of action space $\ccalA$ $\text{for all\ }{i} \in \ccalN$,
\begin{align}
    \ccalA_1(i)&=\{\bbe_{k_1} \in \ccalA \,| a_i=\bbe_{k_1} \in \argmax u_i(a_i,a_{-i})\}, \\
    \ccalA_2(i)&=\{\bbe_{k_2} \in \ccalA \,| a_i=\bbe_{k_2} \notin \argmax u_i(a_i,a_{-i})\}.
\end{align}
Since they are mutually exclusive subsets, it holds $\ccalA_i=\ccalA_1(i) \cup \ccalA_2(i)$ and $\ccalA_1(i) \cap \ccalA_2(i)=\emptyset$. Then, optimal set over a finite feasible set of utility functions cannot be empty set $\ccalA_1(i)\not =\emptyset$, while it is possible that $\ccalA_2(i)=\emptyset$. Firstly, suppose that $ \ccalA_2(i) \not =\emptyset$. Hence, there exist actions $a'_i \in \ccalA_1(i)$ and $a''_i \in \ccalA_2(i)$ such that,
\begin{equation}\label{eq_opt_dist}
    u_i(a''_i,a_{-i})- \mu < u_i(a'_i,a_{-i}).
\end{equation}
for some $\mu>0$ satisfying \eqref{eq_lip_up_bound}. Note that \eqref{eq_lipschitz} holds for both actions $a_i'\in \ccalA_1(i)$ and $a_i''\in \ccalA_2(i)$,
\begin{align}
    &|u_i(a'_i,f^i_{-i}(t))-u_i(a'_i,a_{-i})| < \frac{\mu}{2}, \label{eq_lipschitz_a} \\
    &|u_i(a''_i,f^i_{-i}(t))-u_i(a''_i,a_{-i})| < \frac{\mu}{2}.\label{eq_lipschitz_b}
\end{align}
Next, we add $u_i(a''_i,f^i_{-i}(t))$ and $u_i(a'_i,f^i_{-i}(t)) $ to the left and right hand sides of \eqref{eq_opt_dist}, respectively. Similarly, we subtract the same corresponding terms from the left and right hand sides of \eqref{eq_opt_dist}. Using the bounds in \eqref{eq_lipschitz_a} and \eqref{eq_lipschitz_b}, we get
\begin{align}
    u_i(a''_i,f^i_{-i}(t))< &u_i(a'_i,f^i_{-i}(t)).
\end{align}
Further, for any two best-response actions, ${a}'_i \in \ccalA_1(i)$ and $\Tilde{a}'_i \in \ccalA_1(i)$, it can be shown that
\begin{align}
    | u_i({a}'_i,f^i_{-i}(t&))- u_i(\Tilde{a}'_i,f^i_{-i}(t))| < {\mu}.
\end{align}
As a result, using its estimates $f^i_{-i}(t)$, agent $i$ only chooses an action from its optimal action set $\ccalA_1(i)$ for the both cases $\ccalA_2(i)= \emptyset$ and $\ccalA_2(i)\not = \emptyset$. Thus, it holds $\text{for all\ }{i} \in \ccalN$, 
\begin{equation}
    \argmax_{a_i \in \ccalA} u_i(a_i,f^i_{-i}(t))  \subseteq \argmax_{a_i \in \ccalA} u_i(a_i,a_{-i}).
\end{equation}


\subsection{Proof of Theorem \ref{lem_prob_com2}}

We note that the randomness stems from inertia, and communication and acknowledgement failures. The probability of given events in the following part, only depends on these random variables. Thus, showing that the event $\{||a_j(t+T)-f^i_j(t+T||\leq \xi\}$ has a positive probability follows from positive probability of successful communication and acknowledgement, and the positive probability of agent $j$ repeating the same action via inertia. 
Consider the following events:
\begin{align*}
  E_1(t)=\{&||a_j(t+T)-f^i_j(t+T)|| \le  \\
  &||a_j(t+T)-f_j(t+T)||+||f_j(t+T)-f^{i(j)}_{j}(t)|| \} \\
  E_2(t)=\{&||a_j(t+T)-f_j(t+T)|| \le \xi/2\} \\
  E_3(t)=\{&||f_j(t+T)-f^{i(j)}_{j}(t+T)|| \le \xi/2\}
\end{align*}
\begin{comment}
our aim is to provide lower bound on the given event rather than finding exact value. Therefore, it is enough to show intersection of the following events to have positive probability of $\mathbb{P}(||a_j(t+T)-f^i_j(t+T)|| \le \blue{\xi} | \red{\ccalH(t)}) \ge \hat{\epsilon}$ with given protocols,
\red{ \begin{align} \label{eq_prob_upper}
   \mathbb{P}(&(||a_j(t+T)-f^i_j(t+T)|| \le  \nonumber\\
  &||a_j(t+T)-f^j_j(t+T)||+||f^j_j(t+T)-f^{i(j)}_{j}(t)|| )\cap \nonumber  \\
   &(||a_j(t+T)-f_j(t+T)||+||f^j_j(t+T)-f^{i(j)}_{j}(t+T)|| \nonumber \\
   &\le\xi_1+\xi_2  \le \xi ) \: | \ccalH(t)) \ge \hat{\epsilon}.
\end{align}}
\end{comment}
By triangle equality we have,
\begin{align}
    &||a_j(t+T)-f^i_j(t+T)|| \le  \nonumber\\
    &||a_j(t+T)-f_j(t+T)||+||f_j(t+T)-f^i_j(t+T)||.
\end{align}
Then, via triangle inequality, showing that $E_1(t)$ happens with positive probability reduces to showing the positive probability of the following event,
\begin{align*}
E_4(t)=\{||f_j(t+T)&-f^i_j(t+T)||\le\nonumber \\& ||f_j(t+T)-f^{i(j)}_{j}(t+T)||\}.
\end{align*}
Given the assumptions on $\eta_1$, $\eta_2$ and $\eta_3$, condition \eqref{eq_ack_check} is satisfied, i.e., agent $j$ attempts to communicate with agent $i$, when $E_2$ and $E_3$ is true. 

In the event that agent $j$ successfully communicates with agent $i$ and receives an acknowledgement, we have $f^i_j(t+T)=f^{i(j)}_{j}(t+T)$. Thus, 
\begin{equation}
\mathbb{P}({E_1(t)}|\ccalH(t))=\mathbb{P}({E_4(t)}|\ccalH(t)) \ge  \nu^2,
\end{equation}
where the inequality is via the lower bound on communication and acknowledgement success probabilities. 

Next, the event   $E_2(t)$ is certain given repetition of the same action by agent $j$, and by Lemma \ref{lem_rep} (i) there exists a small enough $\xi_1 \le \xi/2$,

\begin{equation}\label{lem_rep_prob}
    \mathbb{P}(E_2(t) |\ccalH(t)) =1 .
\end{equation}


\begin{comment}
Then, the probability of the event is equal to the event $||\red{f^j_i(t)}-f_j(t)|| \le ||f^{i(j)}_{j}(t)-f_j(t)|| \le \xi_2$, since if the event holds, then it also holds $ ||a_j(t+T)-f^j_j(t+T)||+||f^j_j(t+T)-f^i_j(t+T)|| \le  ||a_j(t+T)-f^j_j(t+T)||+||f^j_j(t+T)-f^{i(j)}_{j}(t)|| \le \xi_1 + \xi_2$. Therefore,
\begin{align}
    \mathbb{P}(&||a_j(t+T)-f^i_j(t+T)|| \le \xi | \ccalH(t) )\\
    = \mathbb{P}(&|||f^j_i(t)-f_j(t)|| \le ||f^{i(j)}_{j}(t)-f_j(t)|| \\ \nonumber
     &\cap ||f^{i(j)}_{j}(t)-f_j(t)|| \le \xi_2  | \ccalH(t) ).
\end{align}
\end{comment}
Now, let $\phi_{j}(t+T)$ be the estimate of empirical frequency of agent $j$ constructed using limited information 
$\upsilon_j(t+T)$ \eqref{eq_lim_max} and $\kappa_j(t+T)$ \eqref{eq_lim_arg} at time $t+T$. By triangle equality, we have
\begin{align} \label{eq_cond2_bound}
    &||f_j(t+T)-f^{i(j)}_{j}(t+T)|| \le ||f_j(t+T)-\phi_{j}(t+T)|| \nonumber\\ &+||\phi_{j}(t+T)-f^i_j(t+T)|| +||f^i_j(t+T)-f^{i(j)}_{j}(t+T)||. 
\end{align}
Now, consider the following events, 
\begin{align*}
  E_5(t)=\{&||f_j(t+T)-\phi_{j}(t+T)|| \le \xi/2\}  \\
  E_6(t)=\{&|||\phi_{j}(t+T)-f^i_j(t+T)|| =0\} \\
  E_7(t)=\{&|||f^i_j(t+T)-f^{i(j)}_{j}(t+T)||=0\}
\end{align*}
Given the repetition of the same actions by agents $j \in \ccalN \setminus \{i\}$ and Lemma \ref{lem_rep} (ii), there exists a small enough $\xi_2 \le \xi/2 $ similar to \eqref{lem_rep_prob}, $\mathbb{P}( E_5(t)| \ccalH(t))=1$.
Further, see the remaining events have also positive probability as the result of successful communication and  acknowledgement, 
\begin{align}
    &\mathbb{P}(E_6(t)| \ccalH(t)) \ge \nu>0, \\
    &\mathbb{P}(E_7(t) | \ccalH(t)) \ge  \nu^2 >0.
\end{align}
\begin{comment}
In the same way, if successful communication and acknowledgement happen, it becomes $f^j_i(t)=f^{i(j)}_{j}(t)$. Hence, the probability of the event is at least the product of successful communication and  acknowledgement,
\begin{align}
    &\mathbb{P}(||f^j_i(t)-f_j(t)|| \le ||f^{i(j)}_{j}(t)-f_j(t)|| | \ccalH(t) ) \nonumber \\
    &\ge  p_{ij}(t)\beta_{ij}(t) \ge \nu^2>0. 
\end{align}
\end{comment}
From \eqref{eq_cond2_bound} and the bounds above, we have 
\begin{align}
     \mathbb{P}(E_3(t)| \ccalH(t)) \ge \mathbb{P}(E_5(t),E_6(t),E_7(t)| \ccalH(t))\ge \nu^2 >0.
\end{align}
Thus, there exists a positive real number $\hat{\epsilon}>0$ such that, 
\begin{align}
    &\mathbb{P} (||a_j(t+T)-f^i_j(t+T)|| \le {\xi}| \ccalH(t)) \ge \nonumber\\
    &\mathbb{P}(E_1(t),E_2(t),E_3(t)| \ccalH(t)) \ge \nu^2 =\hat{\epsilon}>0.
\end{align}
 



\begin{comment}


\red{let $\bbone_{\ccalH^{(t+T)}_{j}} \in \{0,1\}$} be indicator random variable defined over the event $\mathfrak{h}_{j}(t+T)$ given as below,
\red{
\begin{align}
   \mathfrak{h}_{j}(t+T)=\{ &(a_j(t+T),f^j_j(t+T),f^{i(j)}_{j}(t)) \nonumber\\
   &\in \{0,1\}^K \times [0,1]^K \times [0,1]^K: \nonumber\\
   & ||a_j(t+T)-f^j_j(t+T)||\le \eta_1 \le \xi_1 \le \eta_2, \nonumber\\
   & ||f^j_j(t+T)-f^{i(j)}_{j}(t)|| \le \eta _3 \le \xi_2 \}.
\end{align}}

Then, see that the probability $\mathbb{P}(||a_j(t+T)-f^i_j(t+T)|| \le \blue{\xi} | \ccalH(t+T))$, can be expressed with conditional probabilities on $\bbone_{\mathfrak{h}_{j}(t+T)}$ as follows,
\begin{align}
    &\mathbb{P}(||a_j(t+T)-f^i_j(t+T)|| \le \blue{\xi} | \ccalH(t+T)) \nonumber\\
    = &\sum_{m=0}^1\mathbb{P}(||a_j(t+T)-f^i_j(t+T)|| \le \blue{\xi} | \ccalH(t+T), \bbone_{\mathfrak{h}_{j}(t+T)}=1)\nonumber\ \\
    & \times \mathbb{P}(\bbone_{\mathfrak{h}_{j}(t+T)}=1 | \ccalH(t+T)).
\end{align}
By triangle equality and Lemma \ref{lem_rep}, there exists small and large enough $ \eta_1>\xi_1> \eta_2$ and $\xi_2 > \eta_3$ such that by satisfying communication protocols \eqref{eq_ack_check}, there exists small enough $\xi_1$ and $\xi_2$ as follows,
\begin{align} \label{eq_com_bound}
    &||a_j(t+T)-f^i_j(t+T)|| \nonumber\\
    &\le ||a_j(t+T)-f^j_j(t+T)||+||f^j_j(t+T)-f^i_j(t+T)||\\
    &\le ||a_j(t+T)-f^j_j(t+T)||+||f^j_j(t+T)-f^{i(j)}_{j}(t)||, \label{eq_com_bound_3} \\
    & \le \xi_1 + \xi_2 \le \blue{\xi} \label{eq_com_bound_last}.
\end{align}
By the inequalities \eqref{eq_com_bound}-\eqref{eq_com_bound_last}, therefore it holds that $\mathbb{P}(||a_j(t+T)-f^i_j(t+T)|| \le \blue{\xi} | \ccalH(t+T), \bbone_{\ccalH_{j}^{t+T}}=1)=1$ and otherwise $\mathbb{P}(||a_j(t+T)-f^i_j(t+T)|| \le \blue{\xi} | \ccalH(t+T), \bbone_{\ccalH_{j}^{t+T}}=0)=0$. Thus, it is enough to consider the event $\mathbb{P}(\bbone_{\ccalH_{j}^{t+T}}=1 | \ccalH(t+T))$ in order show that the event  $\mathbb{P}(||a_j(t+T)-f^i_j(t+T)|| \le \blue{\xi} | \ccalH(t+T)) \ge \hat{\epsilon}$ has positive probability. Again by triangle equality and Assumption \ref{as_ack},
\begin{align} \label{eq_cond2_bound}
    &||f^j_j(t+T)-f^{i(j)}_{j}(t)|| \le ||f^j_j(t+T)-\phi_j(t+T)|| \nonumber\\ &+||\phi_j(t+T)-f^i_j(t+T)|| +||f^i_j(t+T)-f^{i(j)}_{j}(t)|| 
\end{align}
Combining the inequalities \eqref{eq_com_bound_3} and \eqref{eq_cond2_bound} also implies, 
\begin{align}
     &||a_j(t+T)-f^i_j(t+T)|| \nonumber\\
     &\le  ||a_j(t+T)-f^j_j(t+T)||+||f^j_j(t+T)-\phi_j(t+T)||  \nonumber\\
     &+||\phi_j(t+T)-f^i_j(t+T)|| +||f^i_j(t+T)-f^{i(j)}_{j}(t)||.
\end{align}
Given the repetition of the same actions by agents $j \in \ccalN \setminus \{i\}$ and Lemma \ref{lem_rep}, it holds,
\begin{align}
    \mathbb{P}(||a_j(t+T)-f^j_j(t+T)|| \le {\xi_1} | \ccalH(t+T))=1, \\
    \mathbb{P}(||\phi_j(t+T)-f^j_j(t+T)|| \le {\xi_2}| \ccalH(t+T))=1.
\end{align}
Then, see the remaining events providing upper bound in  have also positive probability as the result of succesful communication and  acknowledgement, 
\begin{align}
    &\mathbb{P}(||\phi_j(t+T)-f^i_j(t+T)|| =0| \ccalH(t+T)) = p_{ij}(t) >0\\
    &\mathbb{P}(||f^i_j(t+T)-f^{i(j)}_{j}(t)|| =0| \ccalH(t+T)) =  p_{ij}(t)\beta_{ij}(t) >0.
\end{align}
Therefore, given the repetition of actions and Lemma \ref{lem_rep},
\begin{align}
    \mathbb{P}(\bbone_{\ccalH_{j}^{t+T}}=1 | \ccalH(t+T)) \ge  p_{ji}(t)\beta_{ji}(t)
\end{align}
Thus, there exists a small enough $\xi_1$ and $\xi_2$,
\begin{align}
    \mathbb{P} (||a_j(t+T)-f^i_j(t+T)|| \le \blue{\xi}| \ccalH(t+T)) >\hat{\epsilon}.
\end{align}
\end{comment}

\subsection{Technical Result}\label{ap_pr_1}
\begin{lemma}\label{lem_rep}
 Let $\{a(t)=(a_1(t),a_2(t),\cdots,a_N(t))\}_{t\ge1}$ be a sequence of actions  generated by the DFP-VL (Algorithm \ref{suboptimal_alg_com}). Suppose agent $j \in \ccalN \setminus \{i\}$ repeats the same action $a_{j}(s)=\bbe_k$ at least ${T>0}$ times for $s=t,t+1,\cdots,{t+T-1}$. Then, there exist $0 <\xi_1$ and $0 <\xi_2$ such that following  statements hold,
 \begin{itemize}
     \item [\textit{i)} ] $||a_j(t+T)-f_j(t+T)|| \le {\xi_1}$ for all $j\in\ccalN\setminus \{i\}$,
     \item [\textit{ii)} ] $||\phi_j(t+T)-f_j(t+T)|| \le {\xi_2}$ for all $j\in\ccalN\setminus \{i\}$,
 \end{itemize}
 where $\phi_j(t)$ is the reconstructed belief of agent $j$'s empirical frequency using $\upsilon_j(t)$ and $\kappa_j(t)$ defined in \eqref{eq_lim_max} and \eqref{eq_lim_arg}, respectively. 
\end{lemma}
\begin{myproof}
\begin{itemize}
 \item [\textit{i)} ] From \eqref{eq_empirical_frequency}, it holds that if $\bbe_k$ is repeated for any $\tau \in \{0,1,2,\cdots\}$ starting from time $t$ by a player ${j} \in \ccalN \setminus \{i\}$,
\begin{align}
    f_j(t+\tau)=(1-\rho)^{\tau}f_j(t)+(1-(1-\rho)^{\tau})\bbe_k,
\end{align}
    Subtracting $\bbe_k$ from both sides and taking the norm we obtain the following,
\begin{align}\label{eq_rep_1}
    ||f_j(t+\tau)-\bbe_k||&=||(1-\rho)^{\tau}(f_j(t)-\bbe_k)||, \\
    &= O((1-\rho)^{\tau}).
\end{align}
 Therefore, if agent $j \in \ccalN \setminus \{i\}$  repeat the same action $a_{j}(s)=\bbe_k)$  at least {$T>0$} times for {$s=t,t+1,\cdots,t+T-1$}, there exists a positive upper bound ${\xi_1} >0$,
\begin{equation}
    ||a_j(t+T)-f_j(t+T)|| \le {\xi_1}\;\; \text{for all\ } j\in\ccalN\setminus \{i\}.
\end{equation}
\item [\textit{ii)} ] To provide an upper bound on we can use triangle inequality as below,
\begin{align}
    ||\phi_j(t+T)-f_j(t+T)||& \le  ||\phi_j(t+T)-a_j(t+T)|| \nonumber\\
     &+||a_j(t+T)-f_j(t+T)||.
\end{align}
Then, notice that $||a_j(t+T)-f_j(t+T)||= O((1-\rho)^{T+1})$ implies $|\upsilon_j(t)-1| = O((1-\rho)^{T+1})$. Since $\phi_{j\kappa_i(t)}(t+T)\ge\upsilon_j(t)$ via \eqref{eq_proper_belief}, it also holds $ ||\phi_j(t+T)-a_j(t+T)||= O((1-\rho)^{T+1})$. Thus, given the repetition of the same action,  there exists a positive upper bound ${\xi_2} >0$,
\begin{align}
    &||\phi_j(t+T)-f_j(t+T)||  \nonumber\\
    & \le ||\phi_j(t+T)-a_j(t+T)||+||a_j(t+T)-f_j(t+T)|| \\
    & \le  O((1-\rho)^{T+1}) \le \xi_2.
\end{align}
 \end{itemize}
\end{myproof}




\section{Introduction}

\input{introduction.tex}



\begin{comment}
\begin{figure}
	\centering
	\begin{tabular}{c}
	\includegraphics[width=.9\linewidth]{final_draw.png} 


	\end{tabular}
	\caption{A team of robots are tasked to solve a target assignment problem. Each robot relies on local estimates of the possible target selection of other robots $f^i(t)$ to select targets. The local estimates are updated based on information received from other robots over a noisy wireless channel subject to failures. The probability of a successful communication from robot $i$ to $j$ ($\beta_{ij}(t)R_{ij}(t)$) depends on their locations ($x_i(t),x_j(t)$), and flow rate ($\beta_{ij}(t)$) determined by agent $i$.}\vspace{-14pt}
	\label{fig_draw}
\end{figure}
\end{comment}


\section{Multi-Agent Systems in Time-Varying Random Networks}\label{sec:model}

\subsection{Notation}

We use $||.||$ to denote Euclidean norm. The notation $\Delta(.)$ defines the space of probability distributions over given set. $\bbone_{(.)}$ is indicator function.  Its value is $1$ if the given condition is satisfied, otherwise $0$.
\begin{comment}

\red{In a multi-agent system defined by the set of agents $\ccalN=\{1,2,\cdots,i, \cdots N\}$, we are going to use the index set $(i,-i)$ where $-i$ denotes the set of agents other than agent $i \in \ccalN$ throughout the paper. Each agent $i$ takes an action $a_i$ from the identical set $\ccalA$ of finitely many $|\ccalA|=K$ elements. Hence, we can further suppose that action set $\ccalA$ can be represented with unit vectors $\bbe_k \in \reals^K$ so that  $\ccalA=\{\bbe_1,\bbe_2,\cdots,\bbe_k,\cdots,\bbe_K\}$. Beyond practical and theoretical implications to be discussed later, the mixed action space $\Delta (\ccalA)$ is defined over the action set $\ccalA$,  as the convex combination of unit vectors $\bbe_k$. As the result, agents' joint mixed action becomes $\sigma=(\sigma_i,\sigma_{-i}) \in \Delta^N\ccalA$, where $ \Delta^N(\ccalA) = \prod_{i \in \ccalN} \Delta(\ccalA)$. Therefore, each agent $i \in \ccalN$, has an utility function $u_i: \Delta^N(\ccalA) \rightarrow \reals$ dependent on the joint mixed strategy profile. Thus, multi-agent systems in the given setting constitute a game defined by $\Gamma:=(\ccalN,\{\mathcal{A},u_i\}_{i\in\ccalN})$. }
\green{CE: Avoid use of conjunctions such as ``Hence'', ``as a result'', ``therefore'', when you are explaining the model/setup. There is no clear causal argument in the setup. Conjunctions make it look like there is one. See below for a replacement paragraph. }
\end{comment}
\subsection{Game-Theoretical Definition}
We consider a strategic game $\Gamma$ among a set of $N$ agents denoted with $\ccalN=\{1,2,\cdots, N\}$. Each agent $i$ chooses an action $a_i$ from a common action set $\ccalA$ with finitely many actions, i.e., $|\ccalA|=K$. We represent each action with an unit vector $\bbe_k \in \reals^K$ so that  $\ccalA:=\{\bbe_1,\bbe_2,\cdots,\bbe_K\}$. Each agent has an utility function $u_i: \ccalA^N \rightarrow \reals$ that depends on the joint action profile $(a_i,a_{-i})\in\ccalA^N$ where $-i$ denotes the set of all agents, and $a_{-i}$ is the action profile of agents in the set $-i$. The strategic game $\Gamma$ is defined by the tuple $(\ccalN,\mathcal{A}^N,\{u_i\}_{i\in\ccalN})$. 

A mixed action (strategy) $\sigma_i$ is a probability distribution over the action space. We define the space of probability distributions over the action space as $\Delta (\ccalA)$. A strategy profile $\sigma=(\sigma_i, \sigma_{-i})$ is a joint mixed action profile belonging to the set of independent probability distributions over the space of action profiles, i.e., $\Delta^N(\ccalA) = \prod_{i \in \ccalN} \Delta(\ccalA)$. We denote the expected utility of agent $i$ given a strategy profile $\sigma$ as $u_i(\sigma) := \sum_{a\in\ccalA^N} u_i(a)\sigma(a)$ where $\sigma(a)$ is the probability of action profile $a \in \ccalA^N$.
\begin{comment}


\red{In the following, we define a Nash equilibrium strategy $\sigma^*=(\sigma^*_i,\sigma^*_{-i}))$. } \green{CE: This is OK but I would suggest providing an informal definition first followed by the formal definition. See below.  } 
\end{comment}



Next, we describe the standard FP and then introduce a generalization of FP for random communication networks. 

\subsection{Fictitious Play with Inertia} 

FP is a distributed game-theoretic learning algorithm in which agents repeatedly take actions in discrete time steps $t=1,2,\dots$ that maximize their expected utilities computed with respect to some estimate of the other agents' strategies. In estimating the strategies of others, each agent assumes other agents are taking actions drawn from a stationary probability distribution determined by the {\it empirical frequency} of the past actions of agents. The empirical frequency of agent $i$ is computed as follows,
\begin{equation} \label{eq_empirical_frequency}
    f_i(t) = (1-\rho)f_i(t-1)+\rho a_i(t),
\end{equation}
where $a_i(t)\in \ccalA$ is the action of agent $i$ at time $t\in \naturals^+$ and $\rho \in(0,1)$ is a fading memory constant determining the update rate of the empirical frequency. 

Given the empirical frequencies of other agents $f_{-i}(t)=\{f_j(t)\}_{j\in \ccalN\setminus i}$, agent $i$'s expected utility from taking action $a_i$ is given as, 
\begin{equation} \label{eq_exp_utility}
u_i(a_i, f_{-i}(t)) = \hspace{-4pt}\sum_{a_{-i} \in \ccalA^{N-1}}  u_i(a_i, a_{-i})  f_{-i}(t)(a_{-i}).
\end{equation}

In FP with inertia, each agent best-responds with inertia, i.e., either takes an action that maximizes its expected utility, or follows its previous action with a small probability $\epsilon\in(0,1)$. 
Agent $i$ needs to observe the past actions of {\it all} agents in order to compute the empirical frequencies as per \eqref{eq_empirical_frequency} so that it can compute the best response action.

\subsection{Decentralized fictitious play (DFP) in random networks}

When communication between agents is subject to failures, agents do not have immediate and permanent access to others' actions. One way to address this problem is by agents keeping local estimates of empirical frequencies of past actions, in which each agent forms estimates about the empirical frequencies of other agents based on information received from neighboring agents in the communication network. 

The estimate of agent $i$ on agent $j$'s empirical frequency in \eqref{eq_empirical_frequency} is denoted with $f^i_j(t)\in\Delta(\ccalA)$. Replacing the empirical frequencies $f_{-i}(t)$ with the estimates $f^i_{-i}(t):=\{f^i_j(t)\}_{j\in\ccalN\setminus\{i\}}$ in \eqref{eq_exp_utility}, we get the expected utility of agent $i$ from taking action $a_i \in\ccalA$ denoted as $u_i(a_i, f^i_{-i}(t))$. As in standard FP with inertia, agents best-respond with inertia, i.e., maximize their expected utility or continue taking the previous action,
 %
\begin{align}\label{eq_response_dc}
a_{i}(t)=
\begin{cases}
\argmax_{a_i\in\ccalA} u_i(a_i,f^i_{-i}(t-1)) &\;\; \text{w.pr. } 1-\epsilon ,\\
a_{i}(t-1) &\;\; \text{w.pr. } \epsilon.
\end{cases}
\end{align} 

In DFP, agents update their local estimates based on information they receive from agents that send information over the random communication network. 

Specifically, we assume point-to-point communication between each pair of agents is possible but communication is subject to random failures. The probability of the existence of a communication link between agent $i \in \ccalN$ and agent $j \in \ccalN \setminus \{i\}$ at time $t\in \naturals^+$ is distributed with a Bernoulli random variable, 
\begin{align} \label{eq_prob}
 c_{ij}(t)  \, \sim \text{Bernoulli} (p_{ij}(t)),
\end{align}
where the {probability of success is $0 \le  p_{ij}(t)<1$}. 

We denote the random communication network at time $t$ with $G(t)=(\ccalN, \ccalE(t))$ where $\ccalE(t)$ is the set of edges realized according to \eqref{eq_prob}. The random communication network $G(t)$ belongs to the space of all possible networks $\ccalG$. 


We denote the history of the actions and networks up to time $t$ as {$H(t):=(\ccalA^N \times \ccalG)^t$}. We define a measurable space {$(H(\infty),\ccalB)$} as the sequence of actions and networks $H(\infty)$ and the Borel sigma-algebra ($\ccalB$). We let {$\{\ccalH(t)\}_{t \ge 0}$} be a sub-sigma algebra of $\ccalB$. The information available to agent $i$ at time $t$ is denoted with ${\ccalH_{i}(t)}$.

The information exchange protocol of agent $i$, denoted with {$\Omega_i: H(t) \to \ccalN\times H(t)$}, determines the set of agents agent $i$ is willing to communicate with (${\ccalN_{i}^{out}(t)\subseteq\ccalN}$) and the information agent $i$ shares with them that is measurable with respect to the information available ${\ccalH_{i}(t)}$. Upon receiving information from its neighbors ${\ccalN_{i}^{in}(t):=\{j\in\ccalN\setminus\{i\}: i\in \ccalN_j^{out}(t)\}}$, agent $i$ updates its estimates about the empirical frequencies of other agents $\{f^{i}_{j}(t)\}_{j\in\ccalN}$ according to a function {$\Phi_{i,j}:H(t)\to \Delta(\ccalA)$} that is measurable with respect to the information available at time $t+1$ ({$\ccalH_{i}(t+1)$}). We let $H_{i}(t)$ be the realization of the information available to agent $i$, $H_{i}(t):=\{\{a_{i}(s)\}_{s=1}^{t-1},\prod_{s=1}^{t-1}\prod_{j\in\ccalN_i^{in}(s)} \Omega_j(H_{j}(s))\}$ as a result of the exchange protocol $\{\Omega_j\}_{j\in\ccalN}$. The exchange protocol determines the information available to each agent in the next time step $H_{i}(t+1) = \{H_{i}(t), a_i(t), \prod_{j\in\ccalN_i^{in}(t)} \Omega_j(H_{j}(t))\}$. For the convergence analysis, we will be agnostic to the specifics of the estimate updates $(\Phi_{i})$  and the information exchange process $(\Omega_i)$, as long as they ensure that agents are able to learn others' actions under a static action profile. We state the condition formally next. 

\begin{condition}[Prediction under static actions]\label{cond_prob}
There exists a positive probability $\hat{\epsilon}>0$ and a finite time $\hat T$ such that if an agent $j\in\ccalN$ repeats the same action for at least $T>\hat T$ times starting from time $t>0$, i.e., $a_{j}(s)=\bbe_k$ for  $s=t,t+1,\cdots,{t+T-1}$ and $\bbe_k\in\ccalA$, agent $i\in\ccalN$ learns agent $j$'s action with positive  probability $\hat{\epsilon}>0$, i.e., $\mathbb{P} (||a_j(t+T)-f^i_j(t+T)|| \le {\xi}| \ccalH(t)) \ge \hat{\epsilon}$ for any $\xi>0$.
\end{condition}

Any estimate update and information exchange process that satisfies Condition \ref{cond_prob} makes sure that agent $i$'s estimate of agent $j$'s action  $f^i_j(t)$ gets close to agent $j$'s action whenever agent $j$ repeats its action long enough. 

We summarize key steps of the generic DFP  next. 
\begin{algorithm}[H] 
   \caption{Generic DFP for Agent $i$}
\label{suboptimal_alg_DFP}
\begin{algorithmic}[1]
   \STATE {\bfseries Input:} Inertia probability $\epsilon$ and fading constant $\rho$.
   \STATE {\bfseries Given:} $f_{-i}^i(0)$ and $a(0)$ for all $i \in \ccalN$.
\FOR{$t=1,2,\cdots $}
  \STATE {\it Best-respond}: Use $f^i(t-1):=\{f^i_j(t-1)\}_{j\in\ccalN\setminus i}$ in \eqref{eq_response_dc} \STATE {\it Share information}: Use $\Omega_i$ to determine ${\ccalN_{i}^{out}(t)}$ and information to be exchanged
\STATE {\it Observe}: Receive information from ${\ccalN_{i}^{in}(t)}\cap \{j: c_{ji}(t)=1\}$ 
\STATE {\it Update estimates}: $f_j^i(t+1)= {\Phi_{i,j}(H_{i}(t))}$ for $j\in\ccalN\setminus i$.
  \ENDFOR 
   \end{algorithmic}
\end{algorithm}

















 
\section{DFP Convergence for Weakly Acyclic Games} \label{sec_con}






We consider convergence of the DFP in the class of weakly acyclic games which have (finite) sequence of best-response updates that end up at a pure Nash equilibrium, named as finite improvement paths \cite{young1993evolution,milchtaich1996congestion}.

A Nash equilibrium strategy is an (mixed) action profile in which no individual agent can benefit by unilaterally switching to another action. A formal definition follows.

\begin{definition} [Nash Equilibrium] \label{def_Nash}
A strategy profile  $\sigma^*=(\sigma_i^*,\sigma_{-i}^*) \in \Delta^N(\mathcal{A})$ is a Nash equilibrium of the game $\Gamma$ if and only if for all $i\in\ccalN$
\begin{equation} \label{eq_Nash}
    u_i(\sigma^*_i,\sigma^*_{-i})\ge u_i(\sigma_i,\sigma_{-i}), \quad \text{for all\ } \sigma_i \in \Delta(\mathcal{A}).
\end{equation}
A pure NE strategy profile $\sigma^*$ is a NE that selects an action profile $a=(a_i,a_{-i}) \in \ccalA^N$ with probability 1. 
\end{definition}

A best-response path is a sequence of action profiles obtained by a single agent best-responding to the current action profile at each step of the sequence. Next, we provide a formal definition of weakly acyclic games. 

\begin{definition} [Weakly Acyclic Games] \label{def_WA}
A game $\Gamma$ is weakly acyclic if from any joint action profile $a=(a_i,a_{-i})\in\ccalA^N$, there exists a best-response path ending at a pure NE $a^*=(a^*_i,a^*_{-i})$.
\end{definition}

The existence of a finite best-response path ensures that no agent can improve its utility after some finite number of iterations. 
Weakly acyclic games are {a} broad class of games that include potential games and its several variants such as best-response potential and pseudo-potential games.

We consider weakly acyclic games in which optimal action is unique against others' actions if other agents take actions according to a pure NE action profile. Specifically, we make the following assumption.


\begin{assumption}\label{as_single}
For any pure NE action profile $a^*\in \ccalA^N$ of the game $\Gamma$, it holds that,
\begin{equation}
  \{a^*_i\} = \argmax_{a_i\in\ccalA} u_i(a_i,a^*_{-i}).
\end{equation}
\end{assumption}
This assumption makes sure that agents are not indifferent between multiple actions at a pure Nash equilibrium.

\begin{comment}
\green{CE: The section below is mostly redundant given the rewrite above. Can remove as you see fit. You can add the communication success probability assumption here. }
\subsection{General Assumptions}
\red{ To analyze convergence of action profile }, we \red{need to limit} the scope of games into weakly acylic games  \cite{young1993evolution,milchtaich1996congestion}. We start with the definition of weakly acyclic games as follows,

Next assumption states that the estimates are measurable with respect to the observations of the agents.
\red{\begin{assumption}\label{as_filt}
 \red{Then,} $\{\mathcal{F}_t\}_{t \ge 0}$ is defined as a filtration with   $\mathcal{F}_t:=\sigma(\{a(s)\}^{t-1}_{s=1},\{f(s)\}^{t-1}_{s=1})$. The  estimate $f^{i}_{j}(t)$ of agent $i$ for agent $j$'s strategy is measurable with respect to $\mathcal{F}_t$. 
\end{assumption}}

\red{Next two assumptions impose certain restrictions on the utility functions. 

\begin{assumption}\label{as_single}
For any pure NE action profile $a^*\in \ccalA^N$ of the game $\Gamma$, it holds that,
\begin{equation}
  \{a^*_i\} = \argmax_{a_i\in\ccalA} u_i(a_i,a^*_{-i}).
\end{equation}
\end{assumption}

This assumption implies that optimal action is unique against others' actions if other agents take actions according to a pure NE action profile.

\begin{assumption}\label{as_max}
The utility functions $u_i: \Delta(\ccalA^N) \rightarrow \reals$ are  Lipschitz continuous $\text{for all\ }{i} \in \ccalN$. 
\end{assumption}
}


\red{This assumption assures as the estimates $f^i_{-i}(t) \in \Delta^{N-1}(\ccalA)$ converges to pure strategies $a_{-i} \in \ccalA^{N-1}$, such that $f^i_{-i}(t) \rightarrow a_{-i}$, the differences between values of utility functions shrinks, i.e., $| u_i(a_{i},f^i_{-i}(t))- u_i(a_{i},f_{-i}(t))| \rightarrow 0$.} \green{CE:This assumption does not directly assure what you are saying. You use this assumption to show that...} 

\red{In the standard fictitious play using best-response with inertia, the convergence of $f^j_j(t)$ to a pure action $a_j(t)$ is required, $|| a_i(t)- f_i(t)|| \rightarrow 0$. Since the convergence to pure action must be visible to the others agents, this requirement extends to $|| a_j(t)- f^i_j(t)|| \rightarrow 0$ in decentralized systems. Each agent $j$ should recognize the convergence to a pure action of another agent $j$, where $f^j_i(t)$ is the estimate of agent $i$ on the empirical frequency of agent $j$. Therefore, as the result of action repetition for sufficient times in row, the next condition can be stated as follows, }


\red{
\begin{condition}\label{cond_prob}
There exists a positive probability $\hat{\epsilon}>0$, after at least $T>\hat{T}$ times repetition of the same action $a_{j}(s)=\bbe_k)$  for $s=t,t+1,\cdots,T-1$ such that each agent $i \in \ccalN$ learns others' actions $a_{-i}=\{a_j\}_{j \in \ccalN \setminus \{i\}}$ with the probability $\mathbb{P} (||a_j(t+T)-f^i_j(t+T)|| \le \eta| \ccalF(t+T)) \ge \hat{\epsilon}$.
\end{condition}
}
\red{ Any communication scheme that assures, $|| a_i(t)- f^j_i(t)|| < \eta$ is enough for other agents to make a decision, with discrete actions and Lipschitz continuous utility functions. We are going to use this condition in order to show convergence to a pure NE. In the following section, implementation of different communication schemes that satisfy this condition will be discussed in detail. }
\end{comment}

\subsection{Convergence to a Pure Nash Equilibrium}

We show almost sure convergence of joint action profile $a(t)$ to a pure NE $a^*$ (Theorem \ref{thm_main}). 
The convergence result relies on the fact that action profile stays forever at a pure NE once it reaches the NE (Lemma \ref{lem_ab}), and there is a positive probability to reach a pure NE from any action profile(Lemma \ref{lem_pos_ab}). Before showing these lemmas, we show that the best response action of an agent computed with respect to the estimated empirical frequencies  $\{f^i_j(t)\}_{j\in \ccalN}$ belongs to the best response action set computed with respect to the actual actions of others $a_{-i}(t)$, whenever the estimates are close enough to $a_{-i}(t)$--see Appendix  \ref{ap_pr_2} for the proof.


\begin{lemma}\label{lem_est}
There exists a small enough ${{\xi>0}}$ such that if $||a_j(t)-f^i_j(t)|| \le {\xi}$ for agents $j \in \ccalN \setminus \{i\}$ at time step $t$, then $\argmax_{a_i \in \ccalA} u_i(a_i,f^i_{-i}(t)) \subseteq \argmax_{a_i \in \ccalA} u_i(a_i,a_{-i})$ for all $i\in\ccalN$.
\end{lemma}



Next, we prove that pure NE have absorption property. When agents play a pure NE and are aware of others' actions, agent are going to stay in this pure NE indefinitely. 






\begin{comment}


\begin{lemma}\label{lem_prob_repeat}\textbf{(positive probability of repetition and communication)}
Suppose Assumption \ref{as_filt} holds and condition in \eqref{eq_condition} is not true  $\text{for all\ }{(i,j)} \in \ccalN \times \ccalN \setminus \{j\}$. Let $E_1$ be the event is defined follows ,
\begin{align} \label{eq_event}
    E_1(t)=\{&a(s)=a,c_{ij}(t+T)=1, \nonumber\\
    &\text{for all\ }{s} \in \{t,t+1,\cdots,t+T\}\},
\end{align}
where $a(s)$ is a joint action profile at time $s$ and $c_{ij}(t)$ is the realization of Bernoulli random variable determining communication link between $i$ and $j$. Then, the probability of the event $E_1(t)$ conditioned on $\ccalF(t)$ is bounded below by a positive constant $\epsilon_1(T)$,
\begin{equation}
    \mathbb{P}(E_1(t)|\ccalF_t,\beta_{ij}(t+T)=1) \ge \epsilon_1(T).
\end{equation}
\end{lemma}
\begin{myproof}
The proof follows from the fact that due to inertia, the probability of repetition of actions in finite $T$ time is always positive. Further, there is a positive probability of communication (at least $p_{ij}(t)>\epsilon_{com}$) before condition \eqref{eq_condition} is satisfied. Thus the probability of action repetitions and communication is at least $\epsilon_1=\epsilon^{NT}\epsilon_{com}^{N(N-1)}$. 
\end{myproof}
\end{comment}


\begin{lemma}\label{lem_ab} \textbf{(absorption property)}
Suppose Assumption \ref{as_single} holds. Assume $||a_j(t+T)-f^i_j(t+T)|| \le {\xi}$ where $\xi>0$ satisfies Lemma \ref{lem_est}  for all pairs of agents $(i,j) \in \ccalN \times \ccalN \setminus \{i\}$ at time step $t+T$. Further, let $a^*\in \ccalA^N$ be a pure NE action profile and $a(t+T)=a^*$. Then, $a(s)=a^*=(a_1^*,a_2^*,\cdots,a_N^*)$ holds, $\text{for all\ }{s} \ge t+T$.
\end{lemma}
 
\begin{myproof}
By Assumption \ref{as_single}, the set of optimal actions given others' actions $a_{-i}(t+T)=a^*_{-i}$ is a singleton given by $\argmax_{a_i \in \ccalA} u_i(a_i,f^i_{-i}(t+T)) = \argmax_{a_i \in \ccalA} u_i(a_i,a^*_{-i})=\{a_i^*\}$. Otherwise, by inertia agent $i$ takes the the same action $a_i^*$. Thus, the joint action profile remains at the pure NE, i.e., $a(s)=a^*, \, \text{for all\ }{s} \ge t+T$.
\begin{comment}
Then, by definition of a pure NE $\{a_i^*\}\in\argmax_{a_i \in \ccalA} u_i(a_i,f^i_{-i}(s))$ for $s\ge t+T_1+T_2$. Moreover, by Lemma \ref{lem_single}, the set $\argmax_{a_i \in \ccalA} u_i(a_i,f^i_{-i}(s))$ is a singleton for each $i \in\ccalN$. Thus the action profile $a^*$ is repeated at time $t+T_1+T_2$. Inductively, $a(s) = a^*$ for all $s \geq t$.
\end{comment}
\end{myproof}

The next lemma states that there is a positive probability that agents can reach a NE action profile with any communication scheme that satisfies Condition \ref{cond_prob}.

\begin{lemma}[\textbf{positive probability of absorption}]\label{lem_pos_ab}
Suppose Assumption \ref{as_single} and Condition \ref{cond_prob} hold. Let $a(t)$ be the joint action profile at time $t$ and $f^i(t):=\{f^i_j(t)\}_{j\in\ccalN}$ be agent $i$'s estimate on all agents at time $t$. At time $t$, we define the following event $\text{for all\ }{(i,j)} \in \ccalN \times \ccalN \setminus \{i\}$, 
\begin{align*}
     E(t)=&\{a(s)=a^*, \, ||a_j(\bar{s}+T)-f^i_j(\bar{s}+T)||  \le {\xi} \\
    
     &\text{for all\ }{s} \in \{\bar{s},\bar{s}+1,\cdots,\bar{s}+T-1\} \\
    
     &\text{for some}\, \bar{s} \in \{t, t+1, \cdots,
     t+K^NT\}\}
\end{align*}
where $a^*$ is a pure NE. There exists ${\xi}>0$  small enough such that the transition probability $\mathbb{P}({E(t)}|{\ccalH(t)}) \ge \bar{\epsilon}(T)$, is bounded below by $\bar{\epsilon}(T)>0$ and always positive $\text{for all\ }{t} \in \naturals^+$.
\end{lemma}
\begin{myproof}
To show the result, we are going to use the fact that in weakly acyclic games, there exists a finite path from any action profile to a pure NE. Since, the action  set of each agent is finite and its size is equal to $K$, there exist $K^N$ different joint action profiles in total. Hence, it is the upper bound on the length of finite path to a pure NE. Thus, if $a(t)=a^*$, the pure NE is reached and, the proof is trivially completed. 


If $a(t)\not =a^*$, we are going to exploit the fact that the finite path to a pure NE consists of finite improvement paths. In each improvement path, only one agent improve its utility by changing its action. Therefore, all agents firstly stay in their actions  
so that it holds  $||a_j(t+T)-f^i_j(t+T)|| \le {\xi}$ with probability at least $\hat{\epsilon}^N$ by Condition \ref{cond_prob}. Then, by inertia, at time step $t+T$, there exists a positive probability $\epsilon^{(N-1)}$, $N-1$ agents continue to stay in the same action for one more time step, and only one agent takes the optimal action against others with probability $(1-\epsilon)$. Since it holds $\argmax_{a_i \in \ccalA} u_i(a_i,f^i_{-i}(t+T)) \subseteq \argmax_{a_i \in \ccalA} u_i(a_i,a_{-i})$ by Lemma \ref{lem_est}, a finite improvement path can complete with at least the probability $\epsilon_1=\hat{\epsilon}^N(1-\epsilon)\epsilon^{(N-1)}$.

After the completion of an improvement path, the event of another improvement path until $a^*$ is reached has at least the same positive probability $\epsilon_1$. As stated before, total number of improvement paths cannot exceed $K^N$ times. Once $a(\bar{s})=a^*$, the probability of learning other's actions is again $\hat{\epsilon}^N$ corresponding to the event that all agents repeat their actions at least $T$ times. Using this, the probability to reach a pure NE is bounded below as $\mathbb{P}({E(t)}|{\ccalH(t)}) \ge \bar{\epsilon}= \epsilon_1^{K^N}\hat{\epsilon}^N$. 
\begin{comment}
The case $a(t)=a^*$, is trivially satisfied by inertia in best response \eqref{eq_response_dc}. For the case $a(t)\neq a^*$, see that as long as the thresholds $H_{ii}(t)$ and $H_{ij}(t)$ are not satisfied, communication between agents continues with at least probability $\epsilon_{com}>0$. Then, suppose that the event $E_1(t)$ happened. The probability of this repetition and communication is at least $\epsilon_1(T)$ by Lemma \ref{lem_prob_repeat}.


Since $a(t)\neq a^*$, there is at least one agent that can improve because of the existence of a best-response improvement path. Suppose $a(t)$ is repeated $T>T_1$ stages where $T_1$ is defined in Lemma \ref{lem_est}. By Lemma \ref{lem_est}, with sufficiently small $\eta_1$ and $\eta_2$, it holds that $\argmax_{a_i \in \ccalA} u_i(a_i,f^i_{-i}(t+T),\mu_i(t+T)) \subseteq \argmax_{a_i \in \ccalA} u_i(a_i,a_{-i},\mu)$. That is, agent $i$ can select a best-response action. 
The probability that only one agent improves its action and the others stay at the same action is given by $\epsilon_2:= (1-\epsilon)\epsilon^{N-1}$. Once agent $i^*$ takes the best response action at time $t+T$, either $a(t+T)=a^*$ or $a(t+T)\neq a^*$. If $a(t+T)=a^*$, then the probability of absorption is satisfied by Lemma \ref{lem_prob_repeat}. Indeed after the final improvement, the probability of absorption is given by $\epsilon_4=\epsilon^{T}\epsilon_{com}^{N-1}$. This is the probability that the action profile is repeated again for $T>T_1$ steps and agent $i^*$  communicated its empirical frequency to all agents at time $t+2T$.

If $a(t+T)\neq a^*$, we need to continue the path of improvement for at most finite $K\in\naturals^+$ number of steps as per the definition of weakly acyclic games. In order for the next improvement to happen, all agents need to repeat their actions for the next $T$ steps, and agent $i^*$ communicates successfully with all agents at time $t+2T$. The probability of this event happening is $\epsilon_3=\epsilon^{N(T-1)}\epsilon_{com}^{N-1}$. Thus, we have $\mathbb{P}({E_2(t)}|\ccalF(t))$ bounded below by $\bar{\epsilon}(T_1,T_2)=\epsilon_1 (\epsilon_2\epsilon_3)^{K} \epsilon_4$.
\end{comment}
\end{myproof}


Above result leverages the fact that as long as each agent recognizes others' empirical frequencies converge to a pure action profile when they continue to take the same action, an agent can improve its utility. Now, we are ready to state the main convergence theorem.  

\begin{theorem}\label{thm_main}
Suppose Assumption \ref{as_single} and Condition \ref{cond_prob} hold. Let $\{a(t)=(a_1(t),(a_2(t),\cdots,a_N(t))\}_{t\ge1}$ be a sequence of actions by the DFP Algorithm (Algorithm \ref{suboptimal_alg_DFP}) and random time-varying communication networks $\{G(t)\}_{t\ge 1}$. The action sequence $\{a(t)\}_{t\ge1}$ converges to a pure NE $a^*$ of the game $\Gamma$, almost surely. 
\end{theorem}
\begin{myproof}
By Lemma \ref{lem_ab}, pure Nash equilibria are the only absorbing states among joint action profiles. By Lemma \ref{lem_pos_ab}, there exists a positive probability to reach a pure NE. Therefore, in finite time with probability $1$, a pure NE is reached and action profile stays same once reached. Thus,  the action sequence $\{a(t)\}_{t\ge1}$ converges to a pure NE $a^*$ of the game $\Gamma$, almost surely. 
\end{myproof}


The convergence theorem relies on the idea of absorbing Markov chains in which pure Nash equilibria are the only absorbing states among all joint action profiles (states). We proved almost sure convergence of actions to a pure NE by the existence of finite improvement paths and the fact that reaching a pure NE from any joint action profile has a positive probability. 



\section{Information Exchange and Belief Update Protocols for Random Communication Networks} \label{sec_com}


We introduce information exchange $\Omega_i(\cdot)$ and belief update $\Phi_i(\cdot)$ protocols that aim to reduce the number of communication attempts while at the same time guaranteeing that prediction under static actions condition (Condition \ref{cond_prob}) holds. 

\subsection{Voluntary Communication Protocols} 
We use two metrics, novelty and belief similarity, to determine whether agent $i$ attempts to communicate to agent $j$ or not. The novelty metric is the distance between the empirical frequency of agent $i$ and its current action denoted with $h_{ii}(t):= ||a_i(t)- f_i(t)||$. The belief similarity metric, defined as  $h_{ij}(t):= ||f_i(t)- {f}^{j(i)}_i(t)||$, is the distance between agent $i$'s empirical frequency $f_i(t)$ and the second order belief of agent $i$, i.e., agent $i$'s belief on agent $j$'s belief on $f_i(t)$ denoted with ${f}^{j(i)}_i(t)$. Based on these metrics, agent $i$ decides to communicate its empirical frequency $f_i(t)$ to agent $j$ if the following logical condition is satisfied, 
\begin{align}\label{eq_ack_check}
    \bbone(\eta_1 \le h_{ii}(t) \le \eta_2) \land \bbone(h_{ij}(t) \ge \eta_3)
\end{align}
where $\eta_2> \eta_1\ge 0$ and $\eta_3\ge 0$, $\bbone(\cdot)$ is the indicator function, and $\land$ is the logical AND operator. Condition \eqref{eq_ack_check} determines the set of agents agent $i$ is willing to communicate with at time step $t$, i.e., $\ccalN_i^{out}(t)$. The set of agents that send their empirical frequencies to agent $i$ at time step $t$ is given by $\ccalN_i^{in}(t)= \{j\in\ccalN\setminus \{i\}: i \in \ccalN_j^{out}(t)\}$.

The intuition for the condition in \eqref{eq_ack_check} is as follows. {The novelty metric $h_{ii}(t)$ has to be between a range for agent $i$ to initiate a communication attempt. The novelty $h_{ii}(t)$ is likely to be small when agent $i$ takes the same action for several steps indicating that it may have converged on an action. If $h_{ii}(t)$ is large, it means agent $i$ is undecided, taking a different action from its past set of actions. When $h_{ii}$ is neither too small or too large, agent $i$ attempts to communicate. Agent $i$ only attempts to send its empirical frequency to agent $j$ if it believes agent $j$ does not have an accurate estimate of its empirical frequency, i.e., if $h_{ij}$ is large enough.} 

Given the communication scheme, agent $i$ updates its belief about agent $j$'s empirical frequency at each time step as follows,
\begin{align}\label{eq_info_ex}
f^{i}_{j}(t)=
\begin{cases}
 f_{j}(t), \, \text{if } c_{ji}(t) =1,\\
f^{i}_{j}(t-1), \, \text{otherwise}.
\end{cases}
\end{align}
That is, agent $i$ replaces its estimate on agent $j$'s empirical frequency with the empirical frequency received from agent $j$ upon a successful communication attempt. Otherwise, its estimate remains the same.

In computing the belief similarity $h_{ij}(t)$, agent $i$ has to form and update beliefs about agent $j$'s belief on its own empirical frequency $f^j_i(t)$. This can be done via an acknowledgement process where each time agent $i$ makes a successful communication attempt to agent $j$, agent $j$ sends back 1-bit acknowledgement signal. We allow the acknowledgement signal to be subject to failures with a Bernoulli variable $b_{ij}(t)\sim \text{Bernoulli}(\beta_{ij}(t))$ with success rate  $0 \le \beta_{ij}(t)\le 1$. We note that the acknowledgement procedure is executed if and only if agent $i$ receives information from agent $j$. Thus, we have $\mathbb{P}(b_{ij}(t)=0| c_{ji}(t)=0) = 1$. Otherwise, we have $\mathbb{P}(b_{ij}(t)= 1 | c_{ji}(t)=1) > \beta_{ij}(t)$. Given the acknowledgement scheme, agent $i$'s second order belief is updated as follows,
\begin{align}\label{eq_first_order_belief}
f^{j(i)}_{i}(t)=
\begin{cases}
 f_{i}(t), \, \text{if } b_{ji}(t) =1,\\
f^{j(i)}_{i}(t-1), \, \text{otherwise}.
\end{cases}
\end{align}
Upon receiving the acknowledgement, agent $i$ knows that its empirical frequency is transmitted to agent $j$, and agent $j$ has updated its belief as per \eqref{eq_info_ex}. In a scenario where $c_{ij}(t)=1$ and $b_{ji}(t)=1$, empirical frequencies and estimates align, i.e., $f^j_i(t)=f^{j(i)}_{i}(t)= f_{i}(t)$.

\begin{remark}
In the information exchange and belief update protocols described above, each agent keeps an estimate of the empirical frequencies of all other agents $\{f^{i}_j(t)\}_{j\in\ccalN}$, an $N\times K$ real-valued matrix, and second order beliefs about other agents' estimates about its empirical frequency $\{f^{j(i)}_i(t)\}_{j\in\ccalN}$, an $N\times K$ real-valued matrix. 
Agent $i$ attempts to send its empirical frequency $f_i(t)$, a real-valued vector of length $K$, to a subset of agents in $\ccalN$ according to the condition in \eqref{eq_ack_check}. In the decentralized FP considered in \cite{swenson2018distributed}, each agent shares their estimates of all the other agents, $\{f^{i}_j(t)\}_{j\in\ccalN}$, an $N\times K$ real-valued matrix, to all of their neighbors at each step.
\end{remark}

\begin{remark}
The condition in \eqref{eq_ack_check} can be less or more selective depending on the constants $\eta_1$, $\eta_2$, and $\eta_3$. The information exchange protocol becomes more selective as $\eta_1$ and $\eta_3$ is increased and $\eta_2$ is decreased close to $\eta_1$. In contrast, if $\eta_1=\eta_3=0$ and $\eta_2$ is large enough, then each agent broadcasts their empirical frequency to all the agents at each step. If $\eta_3=0$, then there is no need for agents to keep second order beliefs as the term with $h_{ij}(t)$ in \eqref{eq_ack_check} is no longer relevant. If $\eta_2$ is large enough and $\eta_3=0$, the information exchange protocol is equivalent to the communication censoring protocol used for distributed optimization algorithms \cite{chen2018ordered,chen2018lag,li2019communication}. 
\end{remark}

\subsection{Limited Information Communication}

Agents share the maximum value and the index of their empirical frequency, i.e., 
\begin{align}
    \upsilon_i(t)&=\max_{k \in \ccalK} f_{ik}^i(t) \label{eq_lim_max}, \\
    \kappa_i(t)&=\argmax_{k \in \ccalK} f_{ik}^i(t) \label{eq_lim_arg},
\end{align}
instead of their empirical frequencies. When an agent $j$ successfully sends the maximum value $\upsilon_j(t)$ and its index $\kappa_j(t)$ \eqref{eq_lim_arg} to agent $i$, agent $i$ needs to reconstruct a well-defined empirical frequency and update its belief $f^i_j(t)$ accordingly. Upon successful communication of $\upsilon_j(t)$ and $\kappa_j(t)$, the reconstructed belief $f^i_j(t)$ has to satisfy 
\begin{align} \label{eq_proper_belief}
    \sum_{k \in \ccalK} f^i_{jk}(t) =1, \;     f^i_{jk}(t) \ge 0, \;
    f^i_{j\kappa_i(t)}(t) \ge \upsilon_i(t), 
\end{align}
where $f^i_{jk}$ denotes the $k$th index. While the first two constraints above define a proper distribution over the space of actions, the third constraint makes sure that the receiving agent uses the information received. There could multiple update rules $\Phi_i(\kappa_j(t), \upsilon_j(t))$ that satisfy the conditions in \eqref{eq_proper_belief}. For instance, one update rule can assume full support on the most frequent action of agent $j$, i.e., $f^i_{j\kappa_j(t)}(t)=1$ and $f^i_{jk}(t)=0$ for $k\in \ccalK\setminus \kappa_j(t)$. Another update rule can assume actions other than the most common are equally likely, i.e., $f^i_{j\kappa_i(t)}(t)=\upsilon_j(t)$ and $f^i_{jk}(t)=(1-\upsilon_j(t))/(|\ccalK|-1)$ for $k\in \ccalK\setminus \kappa_j(t)$. 


\begin{remark}
The limited communication protocol described further reduces the information sent per communication attempt to a single real value $\upsilon_i(t)$ and an integer $\kappa_i(t)$.  
\end{remark}
\subsection{Convergence of Communication and Belief Update Protocols}

We describe the specific steps of the DFP  with limited and voluntary communication protocols (DFP-VL) in Algorithm \ref{suboptimal_alg_com}. Step 4 corresponds to the {\it best response} step in Algorithm \ref{suboptimal_alg_DFP}. Steps 5-7 correspond to the information sharing and observation steps in Algorithm \ref{suboptimal_alg_DFP}. Steps 8-9 update the empiricial frequency estimates and second order beliefs. 


\begin{algorithm}[H]
   \caption{DFP-VL for Agent $i$}
\label{suboptimal_alg_com}
\begin{algorithmic}[1]
   \STATE {\bfseries Input:} The parameters $\rho,\epsilon, \eta_1, \eta_2$, $\eta_3$.
   \STATE {\bfseries Given:} $f_{-i}^i(0)$, $f_{i}^{-i}(0)$, ${f}_{i}^{j(i)}(0)$  and $a(0)$ for all $i \in \ccalN$.
\FOR{$t=1,2,\cdots $}
  \STATE Agent $i$ takes action $a_i(t)$ using \eqref{eq_response_dc}. 
  \STATE Determine $\ccalN_i^{out}(t)$ by checking \eqref{eq_ack_check} for all $j\in \ccalN \setminus \{i\}$. 
  \STATE Transmit $\upsilon_i(t)$ and $\kappa_i(t)$ to agent $j\in \ccalN_i^{out}$.
  \STATE Send an acknowledgement signal to agent $j\in \ccalN_i^{in}(t)\cap \{j: c_{ji}(t)=1\}$.
  \STATE   Update $\{f^{i}_j(t)\}_{j \in \ccalN \setminus \{i\}}$ using \eqref{eq_info_ex} .
\STATE  For agent $\{j\in \ccalN_i^{out}\cap \{j: b_{ji}(t)=1\}\}$, i.e., if communication and acknowledgement are successful, update $f^{j(i)}_{i}(t) = f_i^i(t)$ accordingly, otherwise $f^{j(i)}_{i}(t) = f^{j(i)}_{i}(t-1)$.
  \ENDFOR 
   \end{algorithmic}
\end{algorithm}




\begin{comment}

We make the following assumption in showing that the communication and information protocols in DFP-LV guarantee prediction under static action (Condition \ref{cond_prob}). 
\red{\begin{assumption} \label{as_ack}
Acknowledgement procedure has to satisfy the condition below,  
\begin{align}
||f^j_i(t)-f_j(t)|| \le ||f^{i(j)}_{j}(t)-f_j(t)||
\end{align}
for all times $t$. 
\end{assumption}} \green{CE: we have to find a way to do away with this assumption. This assumption is clearly not true. So what you are proving does not make sense. I think your proof of Lemma 4 holds if (13) holds with positive probability...}
\red{The above assumption states that the second order belief of agent $j$ about agent $i$'s estimate $f^{i(j)}_{j}(t)$ trail behind agent $i$'s estimate of agent $j$'s empirical frequency $f^{i}_{j}(t)$. Next we state the main result of this section.}

\end{comment}






\begin{theorem} \label{lem_prob_com2}
Suppose the communication and acknowledgement success probabilities are lower bounded by a positive value, i.e., $p_{ij}(t)>\nu>0$ and $\beta_{ji}(t)>\nu>0$ for all $t\in \naturals^+$ and $i\in \ccalN, j\in\ccalN$. Let $\{a(t)=(a_1(t),(a_2(t),\cdots,a_N(t))\}_{t\ge1}$ be a sequence of actions generated by the DFP-VL (Algorithm \ref{suboptimal_alg_com}). Then, Condition \ref{cond_prob} is satisfied for any $\xi>0$ given small enough $0\le\eta_1<\xi/2$, large enough $\xi/2< \eta_2$, and small enough $0\le \eta_3\le \xi/2$ such that
if an agent $j\in\ccalN$ repeats the same action for at least $T>\hat T$ times starting from time $t>0$, i.e., $a_{j}(s)=\bbe_k$ for  $s=t,t+1,\cdots,t+T-1$ and $\bbe_k\in\ccalA$, agent $i\in\ccalN$ learns agent $j$'s action with positive  probability $\hat{\epsilon}>0$, i.e., $\mathbb{P} (||a_j(t+T)-f^i_j(t+T)|| \le {\xi}| {\ccalH(t))} \ge \hat{\epsilon}$.
\end{theorem}

\begin{myproof}
See Appendix.
\end{myproof}

Theorem \ref{lem_prob_com2} implies that DFP-VL converges to a pure NE of any weakly acyclic game via Theorem \ref{thm_main}. 





 
\begin{figure*}
	\centering
	\begin{tabular}{ccc
	}
	\includegraphics[width=.33\linewidth]{dist_nE.pdf}& 
	\includegraphics[width=.33\linewidth]{belief_er.pdf} &
    \includegraphics[width=.33\linewidth]{com_atp.pdf} \\ 

	(a) & (b) & (c) \\
   
	\end{tabular}
	\caption{Convergence results over 100 replications.  (a) Convergence of empirical frequencies to pure NE $\frac{1}{N}\sum_{i \in \ccalN} || f^i_i(t)-a^*_i||$ on average. We obtain the nearest pure NE by solving a linear assignment problem. (b) Convergence of beliefs $\frac{1}{N(N-1)}\sum_{i \in \ccalN} \sum_{j \in \ccalN \setminus \{i\}}||f^i_i(t)-f^j_i(t) ||$.(c) Average attempt per communication link over time. } \vspace{0pt}
	\label{fig_conv}
\end{figure*}


\section{Numerical experiments} \label{sec_numeric}


We investigate the performance of different communication protocols in terms of convergence rate and cost of communication in the target assignment game. 

\subsection{Target Assignment Game}


A team of $N$ agents aim to cover $N$ targets with minimum effort. Given the  decentralized decision-making setting, we can represent the problem as a game with the following utility function for agent $i$,

\begin{equation}\label{util_target}
    u_{i}(a_i,a_{-i})= \frac{a_i^T \bbone_{a_{-ik}=0}}{a_i^T d_{i}},
\end{equation}
where $a_i=\bbe_k \in \mathbb{R}^K$ is an unit vector and $\mathbbm{1}_{a_{-ik}=0} \in \{0,1\}^K$ is a binary vector whose $k^{th}$ index is 1 if none of the other agents $j \in \ccalN \setminus \{i\}$ selects target $k$, and otherwise the $k^{th}$ index is equal to 0. 
The distance vector $d_i=[d_{i1},\cdots,d_{ik}, \cdots, d_{iK}] \in \mathbb{R}_+^K $ measures the distance between agent $i$ and each target $k$ in 2D plane, where $d_{ik}=||\theta_i-\theta_k||$. Agent $i$ obtains a positive utility that is inversely proportional to the distance of the agent to the selected target if the  target is not selected by another agent $j$. Otherwise, agent $i$ receives zero utility. Given the utility function  \eqref{util_target}, any joint action that is one-to-one assignment between agents and targets is a pure NE.

 





\begin{comment}
Next, in the generic form of this game, channel interference parameter $\theta_{ij}$ is pairwise symmetric and known.


We can extend this formulation  into a scenario where the parameters $\theta_{ij}$ are random and each agent $i$ learns the distributions of them. Using estimate $f^i_{-i}(t)$ we can rewrite the formulation \eqref{ut_ch} as,

\begin{equation}
    u_i(a_i(t),f^i_{-i}(t))=-\varrho_i I(t)= -\varrho_i\sum_{j \in \ccalN \setminus \{i\} } \varrho_j \mathbb{E}(\theta^i_{ij}) \hat{\delta}_{ij}(t).
\end{equation}
where $\hat{\delta}_{ij}(t) \in [0,1]$ is the probability that agent $i$ selects the same channel $k \in \ccalK$ with agent $j$, given the estimates $f^i_{-i}(t)$. Further see that channel interference game defined by \eqref{ut_ch} is a potential game
\end{comment}




In the numerical experiments, we consider {a} target assignment problem with $N=20$ agents and $K=20$ targets. Positions of agents and targets are randomly generated in  a $2$-D plane. 
{Target positions are generated with polar coordinates whose radii are uniformly sampled from $15$ to $20$, and angular coordinates are also uniformly sampled between $0$ and $2\pi$}. Similarly, the positions of agents on the x-y plane are determined by sampling from a normal distribution with mean $0$ and standard deviation 1 independently for each axis. Using the positions, distances between agents and targets are computed.



The communication and acknowledgement probability for each link are given as $p_{ij}(t)=0.6$ and $\beta_{ij}(t)=0.9$ for all $t\geq 1$ and pairs of agents. Initial empirical frequencies of agents $f_i(0)$ are set to uniform discrete distribution, i.e., $f_{ik}=1/K$ for $k=\{1, \dots, K\}$. We run each simulation for $T_f=10,000$ steps. 

\subsection{Effects of the Communication Protocol}

We compare three versions of the DFP-VL algorithm to the standard DFP in which agents attempt to communicate with all the agents after each decision. In DFP-VL1 we have all the communication bounds in \eqref{eq_ack_check} relevant. In DFP-VL2, we ignore the upper bound on $h_{ii}(t)$ by making $\eta_2$ large. In DFP-VL3, agents attempt to communicate with all the other agents as long as $h_{ii}(t)$ is bounded by $\eta_2$. See Table~\ref{table:param} for specific parameter values.










\begin{table}[t]
\centering
\begin{tabular}{@{}l l l l l @{}}\toprule
\multicolumn{1}{ c  }{} & \multicolumn{1}{ c  }{}&     \multicolumn{1}{ c  }{Parameters}&            \multicolumn{1}{ c}{}\\
\cmidrule{2-5}
\multicolumn{1}{ c  }{} & \multicolumn{1}{ c }{DFP-VL1} &\multicolumn{1}{ c }{DFP-VL2}   &\multicolumn{1}{ c }{DFP-VL3} &\multicolumn{1}{ c }{DFP} \\
\cmidrule{2-5}
\multicolumn{1}{ c  }{$\eta_1$}& 0.01 & 0.01 &- &- \\
\multicolumn{1}{ c  }{$\eta_2$}& 0.6 & - &0.7  &- \\ 
\multicolumn{1}{ c  }{$\eta_3$}& 0.01 & 0.01 &- &-\\
\multicolumn{1}{ c  }{$\epsilon$}& 0.3 & 0.3 &0.1 &0.9 \\
\multicolumn{1}{ c  }{$\rho$}& 0.6 & 0.6 &0.4 &0.1 \\
\bottomrule
\vspace{0pt}
\end{tabular}
\caption{PARAMETER VALUES OF ALGORITHMS}
\label{table:param}
\end{table}



\begin{comment}
\begin{align}
    \sum_{i \in \ccalN} &\sum_{k \in \ccalK}  |f^i_{ik}(T_f)-a^*_{ik}| \\ 
    &\sum_{i \in \ccalN}a^*_{ik}=1, \: k \in \ccalK, \\
    &\sum_{k \in \ccalN}a^*_{ik}=1 \: i \in \ccalN,\\
    &a^*_{ik} \in \{0,1\},
\end{align}
where $a^*_{ik}$ is the binary variables that provides the action of agent $i$ in closest pure NE $a^*$.
\end{comment}




 DFP achieves fastest convergence rates and ends with closest distances to pure NE on average (Fig.~\ref{fig_conv}(a)). DFP-VL1 and DFP-VL2 achieve comparable convergence rates to DFP. DFP-VL3 is the slowest algorithm but shows convergence at acceptable rate around $0.1$ on average at time $T_f=10,000$. We observe that constant communication in DFP achieves a  faster convergence of beliefs, while voluntary communication have a slower convergence in beliefs as shown in Fig.~\ref{fig_conv}(b). Together, Figs.~\ref{fig_conv}(a-b) signify that communication protocols increase belief error but preserve rate of convergence to an equilibrium.
 




\begin{comment}


\begin{table}[t]
\centering
\begin{tabular}{@{}l l l l l @{}}\toprule
\multicolumn{1}{ c  }{} & \multicolumn{1}{ c  }{}&     \multicolumn{1}{ c  }{Coverage}&            \multicolumn{1}{ c}{}\\
\cmidrule{2-5}
\multicolumn{1}{ c  }{Covered Targets} & \multicolumn{1}{ c }{DFP-IVL} &\multicolumn{1}{ c }{DFP-VL}   &\multicolumn{1}{ c }{DFP-I} &\multicolumn{1}{ c }{DFP} \\
\cmidrule{2-5}
\multicolumn{1}{ c  }{20}& 18 & 7 &2 &6 \\
\multicolumn{1}{ c  }{19}& 27 & 29 &8 &14 \\ 
\multicolumn{1}{ c  }{18}& 15 & 20 &20 &18\\
\multicolumn{1}{ c  }{17}&  & 24 &17 &16 \\
\multicolumn{1}{ c  }{16}& 8 & 7 &25 &23 \\
\multicolumn{1}{ c  }{15}& 6 & 10 &12 &11 \\
\bottomrule
\vspace{0pt}
\end{tabular}
\caption{COVERAGE STATS OF FINAL JOINT ACTIONS}
\label{table:cover}
\end{table}
\end{comment}

\begin{figure*}
	\centering
	\begin{tabular}{ccc
	}
	\includegraphics[width=.33\linewidth]{dist_nE_param_18.pdf}& 
	\includegraphics[width=.33\linewidth]{belief_er_param.pdf}&
	\includegraphics[width=.33\linewidth]{com_atp_param.pdf} \\
   
    	(a) & (b) & (c) \\
	\end{tabular}
	\caption{ Convergence results of DFP-VL with different parameter values over $100$ replications. Fading rate $\rho=0.8$ and inertia probability $\epsilon=0.1$. (a) Convergence of empirical frequencies to pure NE $\frac{1}{N}\sum_{i \in \ccalN} || f^i_i(t)-a^*_i||$ on average.\
 (b)	Convergence of Beliefs $\frac{1}{N(N-1)}\sum_{i \in \ccalN} \sum_{j \in \ccalN \setminus \{i\}}||f^i_i(t)-f^j_i(t) ||$.    (c) Average attempt per communication link over time.} \vspace{0pt}
	\label{fig_conv_param}
\end{figure*}


DFP-VL1 and DFP-VL2 utilize $44\%$ and $46\%$ of the communication links, respectively while DFP-VL3 uses $90\%$ of the communication links on average at any point in time (Fig.~\ref{fig_conv}(c)). DFP-VL1 and DFP-VL2 start at full usage of links and then cease the communication attempts almost entirely toward the end of the simulation horizon. Fig.~\ref{fig_conv}(a) and (c) highlight that DFP-VL1 and DFP-VL2 have a faster rate of convergence to NE with a smaller communication effort than DFP-VL3.  








\subsection{Parameter Sensitivity}
We assess the performance of DFP-VL under different communication thresholds in Fig. \ref{fig_conv_param}. Here we consider a higher fading and a smaller inertia values compared to Fig. \ref{fig_conv}. Compared with the baseline case (DFP-VL1 shown with black line in Fig. \ref{fig_conv}), we observe that DFP-VL performs better with higher fading and smaller inertia as indicated by the faster convergence to equilibrium by green, blue and red lines in Fig. \ref{fig_conv_param}. The reason is that agents utilize new information faster and update their best-response actions to others accordingly per successful communication when fading is higher and inertia is smaller. In contrast, in standard DFP with constant communication attempts, slow fading rate and increased probability of inertia yields better performance in terms of convergence. This is because in standard DFP, agents are more likely to receive new information at each step. Slow fading rate and increased probability of inertia prevent agents from being oversensitive to new information. We also observe that higher fading and smaller inertia further reduce the communication attempts, e.g., DFP-VL utilizes 27$\%$ of the communication links in Fig. \ref{fig_conv_param}(c) green line. 

Lastly, we observe a counter intuitive phenomenon in Fig. \ref{fig_conv_param}(a-c). As the region of communication is increased, i.e., we decrease $\eta_1$, increase $\eta_2$, and decrease $\eta_3$, not only we get faster convergence and smaller belief errors, but also we see a reduction in communication attempts on average (observe green line with $\eta_1 = 0.001$, $\eta_2 =0.9$ and $\eta_3=0.001$ tread below rest of the lines in Fig. \ref{fig_conv_param}(a-c)). This is counter intuitive because we would expect that a larger region of communication would lead to more communication attempts. However, the frequency of communication attempts is lower in green line except for the first few initial steps. This shows the value of initial communication attempts. Communication in the first few steps allow agents to coordinate early on leading to a smaller belief error, faster convergence to an equilibrium, and reduction in communication attempts later on. Another factor is that smaller $\eta_1$ and $\eta_3$ values yield more precise estimates of agent behavior. This allows agents to be sure early on about the target selections of other agents, and thus eliminate certain targets.







 

\begin{comment}


\begin{figure*}
	\centering
	\begin{tabular}{cc
	}
	\includegraphics[width=.4\linewidth]{dist_nE_bit.pdf}& 
	\includegraphics[width=.4\linewidth]{belief_er_bit.pdf}\\ 
	\includegraphics[width=.4\linewidth]{ack_er_bit.pdf} &
    \includegraphics[width=.4\linewidth]{com_atp_bit.pdf} 
	\end{tabular}
	\caption{ Convergence results over 100 replications.  (Top-Left) Convergence of empirical frequencies to pure NE $\frac{1}{N}\sum_{i \in \ccalN} || f^i_i(t)-a^*_i||$ on average.
 (Top-Right)	Convergence of Beliefs $\frac{1}{N(N-1)}\sum_{i \in \ccalN} \sum_{j \in \ccalN \setminus \{i\}}||f^i_i(t)-f^j_i(t) ||$.(Bottom-Left)	Convergence of Second Order Beliefs $\frac{1}{N(N-1)}\sum_{i \in \ccalN} \sum_{j \in \ccalN \setminus \{i\}}||f^i_i(t)-\hat{f}^j_i(t) ||$.    (Bottom-Right) Average attempt per communication link over time.} \vspace{0pt}
	\label{fig_conv}
\end{figure*}
\end{comment}


\section{Conclusion}
We considered inertial best-response type algorithms for learning Nash equilibria in weakly acyclic games in random communication networks. We showed that the actions generated from inertial best-response type algorithms converge to a pure Nash equilibrium in weakly acyclic games almost surely under the condition that agents are learn to predict the actions of other agents when those agents repeat the same action. We then proposed voluntary communication protocols for FP in which agents decided who to send the empirical frequencies of their actions based on the novelty of empirical frequency to the receiving agent. We showed that the proposed communication protocols satisfy the prediction under static actions condition, and thus are guaranteed to converge to a pure NE. Compared to standard DFP with constant communication attempts, numerical experiments showed that the voluntary communication protocol significantly reduces communication attempts while achieving a similar convergence rate to a NE. 

\begin{comment}
\red{We proposed decentralized mobility and communication controls for a team of agents solving a target assignment problem by best responding to the intended target selection of other agents. Each agent learns about others' intended selections by keeping track of others' frequency of past actions. For keeping such estimates, agents need to be able to transmit their empirical frequencies to each other over a wireless network subject to path loss and fading. The proposed communication protocol relies on metrics that measure novelty of information and information need of the agents to decide whether to transmit or not and how to allocate available communication resources. Moreover, agents may alter their mobility to overcome fading in communication depending on their assessment of the need to communicate certain agents. We stated sufficient conditions for convergence to an NE, and presented numerical results that demonstrated the benefits of the proposed learning-aware voluntary communication and the communication-aware mobility protocols on reducing communication need while retaining convergence guarantees.}
\green{CE: This is old. Rewrite...}
\end{comment}



\subsection{Related Literature}


FP converges to rational behavior in various games including potential \cite{monderer1996fictitious}, weakly acyclic \cite{young2004strategic,marden2009cooperative}, zero-sum \cite{robinson1951iterative}, near-potential \cite{candogan2013dynamics}, and stochastic games \cite{sayin2020fictitious}. In FP, each agent takes an action that maximizes its expected utility (best responds) assuming other agents select their actions randomly from a stationary distribution. Agents assume this stationary distribution is given by the past empirical frequency of past actions. FP is not a decentralized algorithm, since agents need to observe past actions of everyone to be able to keep track of empirical frequencies, and compute the expectations of their utilities. Recent works \cite{Swenson_et_al_2014,eksin2017distributed,swenson2018distributed,arefizadeh2019distributed} consider a decentralized form of the fictitious play, in which agents form estimates on empirical frequencies of other agents' actions by averaging the estimates received from their neighbors in a communication network. These algorithms are shown to converge to a NE in weakly acyclic games, i.e., games that admit finite best-response improvement paths. However, they rely on communication with neighbors after every decision-making step. This assumption ignores the randomness of communication attempts, e.g., in wireless communication settings, and the energy costs of communication. Preliminary versions of this paper either consider a specific setting for the voluntary communication protocol design, namely the target assignment game in \cite{aydin2020communication}, or focus on the convergence of a specific communication protocol for DFP in \cite{aydin2020decentralized}.
Theorem \ref{thm_main} generalizes the convergence results in DFP and the preliminary results in \cite{aydin2020communication,aydin2020decentralized} to show that a generic inertial best-response type behavior will converge to a rational action profile as long as there exists a belief update and information exchange protocol in which agents are able to learn the actions of other agents when these agents repeat the same action long enough. We then leverage this result to design an intuitive and novel class of communication efficient belief update and information exchange protocols.


In the voluntary information exchange protocols, the assessment of the novelty of information to a potential receiving agent is based on two metrics: {\it i)} novelty of local information and {\it ii)} its potential effect on the belief of the receiving agent. Such metrics that are based on second order beliefs (estimating the estimates of the receiving agents) can provide similar benefits to communication efficiency in other decentralized game-theoretic learning algorithms based on, e.g., gradient descent \cite{alpcan2005distributed,koshal2016distributed,Shamma_Arslan_2005,de2019distributed}, best-response \cite{scutari2013joint}, ADMM \cite{salehisadaghiani2019distributed}, and other adaptive strategies \cite{ye2021adaptive}. Indeed, communication-censoring based protocols that rely on some form of novelty of information metrics recently proved viable in reducing communication attempts in distributed stochastic gradient descent \cite{chen2018ordered,chen2018lag} and ADMM \cite{li2019communication} in the context of optimization. In the class of information exchange protocols considered here, while the novelty of information metric is sender specific, the metric on potential effect of information on other's assessment is receiving agent specific. Thus, agents manage their local information by deciding whom to communicate with. This is a novel communication protocol that relies on agents keeping track of second order beliefs, i.e., forming beliefs on beliefs, in order to estimate the novelty of their information to the candidate receiving agent. 
 

















 






 
\begin{comment}
{\it Learning-aware communication} refers to agents assessing novelty of their information and the information need of other agents who are potential receivers of information. Indeed, if an agent has little new information to share, the individual agent can save energy by abstaining from communication without hampering team performance. Based on this premise, recent studies in distributed optimization  \cite{chen2018ordered,chen2018lag,liu2018coca} propose local threshold based communication protocols that rely on novelty of information measured by, e.g., change in local gradient. These communication protocols are also referred to as censoring since a sender agent self-censors if it deems its information as stale. In \cite{aydin_eksin_2020}, we consider a similar censoring-based communication scheme for the DFP algorithm. Along the same lines, here we consider a communication protocol that provides full autonomy to agents in deciding whether to communicate or not based changes in their estimates of empirical frequencies. Our protocol departs from the past approaches by the feature that agents also determine who to communicate with by assessing information need of other agents, in addition to the novelty of their information. Specifically, agents keep an estimate of the similarity between each others' estimates of empirical frequencies. If agent $i$'s assesses that agent $j$ may have similar estimates due to past interactions, it may choose to not transmit its new estimate to agent $j$. Moreover, each agent  allocates their communication resources based on a statistic that measures the similarity of target selections. That is, if an agent is more likely to select the same target with another agent, then it is more urgent for these two agents to coordinate their selections. These features in which agents determine who to communicate with and allocate communication resources based on urgency of information exchange makes the communication protocol learning-aware. 
\end{comment}

\begin{comment}
{\it Communication-aware mobility} refers to agents determining their heading directions not just based on their target selections, but also based on their need to communicate in the presence of fading. In the target assignment game, if robots move toward their selected targets, they may quickly lose connectivity due to growing distances. This may lead to certain robots committing early to their target selections without spending the time needed to coordinate their actions with all the  other agents. Since the team would need to resolve agent-target allocations eventually, this mobility would be highly inefficient as some agents may take many steps toward their selected targets only to change their selections. In addressing some of these issues, recent works in distributed mobility and communication control in autonomous teams propose mobility decisions that mind communication \cite{fink2011robust,stephan2017concurrent,kantaros2016distributed}. However, in these studies network connectivity is treated as a constraint to be satisfied by the team. Ensuring connectivity as mobile robots move to reach their selected targets can significantly hamper team performance, and cause the target assignment problem to be infeasible since some targets may never be covered to remain connected. More recent studies on mobile robotic teams  \cite{kantaros2019temporal,khodayi2019distributed} account for intermittent communication for distributed state estimation problems.  Along similar lines, we incorporate information exchange needs of agents and fading effects into their mobility decisions. Our goal is to reduce total distance traversed by the team by increasing the chances of successful communication attempts.
\end{comment}
 
 
 
 
 \begin{comment}
 \red{We analyze the convergence properties of the DFP algorithm equipped with learning-aware communication and communication-aware mobility protocols in the target assignment game (Section \ref{sec_con}). First we show that the target assignment game is best-response potential game, i.e., there exists a potential function such that the best action for an agent is the same regardless of whether it minimizes its utility function or the potential function.  Then, we show that the DFP algorithm converges to a pure Nash equilibrium of the target assignment game (Theorem \ref{thm_main}) given appropriate choices of the threshold parameters in the learning-aware communication protocol. Given the convergence to pure Nash equilibrium in finite time, we are able to show that all targets are eventually covered by the team (Corollary \ref{cor_physical}).  Numerical experiments demonstrate the reduction in the number of communication attempts due to learning-aware communication, and the increased likelihood of finishing the given task by the final time due to communication-aware mobility (Section \ref{sec_numeric}). }
 \end{comment}

 









\subsubsection{#1}\vspace{-3\baselineskip}\color{black}\medskip{\noindent \bf \thesubsubsection. #1.}}

\newcommand{\myparagraph}[1]{\needspace{1\baselineskip}\medskip\noindent {\it #1.}}

\newcommand{\myindentedparagraph}[1]{\needspace{1\baselineskip}\medskip \hangindent=11pt \hangafter=0 \noindent{\it #1.}}

\newcommand{\myparagraphtc}[1]{\needspace{1\baselineskip}\medskip\noindent {\it #1.}\addcontentsline{toc}{subsubsection}{\qquad\qquad\quad#1}}


\subsection{Game theoretic preliminaries}
We consider the  Nash equilibrium solution concept as a rational action profile. A Nash equilibrium (NE) $a^{\text{NE}} \in [0,1]^n$ is an action profile that satisfies
\begin{align} \label{Nash_definition}
u_i(a_i^{\text{NE}}, a_{\ccalN_i}^{\text{\text{NE}}}) \geq  u_i(a_i, a_{\ccalN_i}^{\text{NE}}) \quad a_i \in [0,1], i \in \ccalN
\end{align}
In other words, the individuals best-respond to the NE actions of other individuals. For a given neighbor action profile $a_{\ccalN_i}$ the best response for player $i$ is
\begin{align}
BR_i(a_{\ccalN_i}) &:= \argmax_{a_i \in [0,1]} u_i(a_i, a_{\ccalN_i}) \label{best_response} \\
& = \bbone\left({1} >  (c_0 (1-s_i)+c_1 s_i) \sum_{j\in \ccalN_i} a_j \right) \label{best_response_specific}
\end{align}
where $\bbone(\cdot)$ is an indicator function. Since the payoffs are linear in self-actions, the actions that maximize the payoffs are in the extremes---$a_i =1$ or $a_i = 0$---depending on the types and actions of their neighbors. 
We can equivalently represent the NE definition in \eqref{Nash_definition} by using the best response definition,  
\begin{align} \label{NE_best_response}
a_i^{\text{NE}} = BR_i(a_{\ccalN_i}^{\text{NE}}) \quad \text{for all\ } i\in \ccalN.
\end{align}

The notion of strictly dominated is defined in the following.

\begin{definition}[Strictly dominated action] \label{strictly_dominated_definition}
An action $a_i \in [0,1]$ is strictly dominated if and only if there exists an action $a_i' \in [0,1]$ such that 
\begin{equation}\label{eq:strictly_dominated_definition}
u_i(a_i', a_{\ccalN_i}) >  u_i(a_i, a_{\ccalN_i}) \quad \text{for all\ } a_{\ccalN_i}\in \ccalA_{\ccalN_i}.
\end{equation}
\end{definition}
If an action $a_i$ is strictly dominated then there exists a more preferable action $a_i'$ for any circumstance. From \eqref{NE_best_response}, a strictly dominated action cannot be rational .

In the game $\Gamma$, we can iteratively remove the strictly dominated actions. This process is called the iterated elimination of strictly dominated strategies, defined below.
\begin{definition}[Iterated elimination] \label{def:elimination_strict}
Set the initial set of actions $A_i^0 = [0,1]$ for all $i$, and for any $k\in \naturals$ let 
\begin{equation}
	\begin{aligned}
	A_i^k = \{a_i \in &A_i^{k-1} \given \\
	&a_i \text{ is not strictly dominated by any } a_{\ccalN_i} \in A_{\ccalN_i}^{k-1}\}.
	\end{aligned}
\end{equation}
\end{definition}
We denote the set of player $i$'s actions that survive the iterated elimination by $A_i^\infty := \bigcap_{k =0}^\infty A_i^k$. If $A_i^\infty$ is a singleton (has a single element) for all $i\in\ccalN$, then the game is dominance solvable, and has a unique Nash equilibrium given by the action profile that survives the iterated elimination process. 
\subsection{Convergence}




The following theorem states that Algorithm \ref{local_alg} eliminates all strictly dominated actions in finite number of steps.

\begin{theorem} \label{local_algorithm_convergence}
Assume all players are undecided, i.e., $a_{i}^0 = \epsilon$ for $i\in\ccalN$. Algorithm \ref{local_alg} converges in at most $n$ iterations, that is, no player changes its action after the $n$th update. If all players are decided, i.e., $a_{i}^n = \{0,1\}$ for all $i\in\ccalN$, the resultant action profile $a^n$ is a Nash equilibrium. Otherwise, if a player $i \in \ccalN$ is undecided, then there does not exist $a_i \in \ccalA_i$ that can be strictly dominated. 
\end{theorem}


The proof (see Appendix) relies on showing that Algorithm \ref{local_algorithm_convergence} is a decentralized version of the iterated elimination of strictly dominated actions as given by Definition \ref{def:elimination_strict}. The intuition for $n$ step convergence is that at each step at least one player needs to eliminate its action using \eqref{worst_case_good_response} or \eqref{best_case_bad_response}. If no player updates at a time step, the players stop updating because no new eliminations are triggered. Therefore, there could  at most be $n$ iterations to rule out $n$ players one player at a time.



