 a time to concede the object to the other player. 
    If both concede at the same time, they share the object. 
    Each player has a valuation of the object, and each player’s utility is decremented at every time step.
    
    \item \textit{BertrandOligopoly:} All players in this game are producing the same item and are expected to set a price at which to sell the item. The player with the lowest price gets all the demand for the item and produces enough items to meet the demand so that obtain the corresponding payoff.
    
    \item 
    \textit{MajorityVoting:} 
    This is an $n$-player symmetric game.
    All players vote for one of the $|A_1|$ candidates. 
    Players' utilities for each candidate being declared the winner are arbitrary. 
    If there is a tie, the winner is the candidate with the lowest number. 
    There may be multiple Nash equilibria in this game.
\end{itemize}

\subsection{Game Generation}
\label{sec:game_generation}
The game generator tool GAMUT requires random seeds to generate a game.
According to the source code of GAMUT, the randomness includes:
\begin{itemize}
    \item 
    The interpretation of each action, especially 
when each action corresponds to a numerical value within a range. For instance, in TravelersDilemma, each action represents a bet. 
    \item 
    The utility of each player when it is not unique. For example, in MajorityVoting, players' utilities for each candidate being declared the winner are arbitrary.
    \item 
    The \textit{permutation} of the action space. The action space will be randomly shuffled, so as the corresponding utilities.
\end{itemize}


\section{Additional Experiments}
\label{sec:add:exp}

\subsection{Multi-player Games}
\label{sec:addexp:n-player}
\input{6.2-table}
We also conduct experiments on games with more than two players.
Specifically, we evaluate our Nash predictor in \textit{BertrandOligopoly} and \textit{MajorityVoting} with $3$ and $4$ players 
(Denote \textit{BertrandOligopoly}-3 and \textit{BertrandOligopoly}-4 as the $3$ and $4$ players version of \textit{BertrandOligopoly}, so as \textit{MajorityVoting}-3 and \textit{MajorityVoting}-4).
Due to the exponential dimension of multiple player games, we set the size of utility matrix as $30\times 30\times 30$ for $3$-player games and $15\times 15\times 15\times 15$ for $4$-player games.
The data generation procedure and the hypothesis class selection are the same as in the experiments of bimatrix games.
We also record the time, and iterations baseline algorithms spend to reach the same performance, except for the TS algorithm, since it is designed for bimatrix games only.

The experiment result of generalization and efficiency are shown in \cref{tab:time_2}.
As we can see in \cref{tab:time_2:1}, the learned Nash predictor still generalizes well on all the tasks, with Nash approximation value less than $0.0008$. 
Our PAC result verifies since we build our theoretical analysis upon $n$-player games.
In \cref{tab:time_2:2}, we can find that baseline algorithms still struggle to get the same performance as the learned Nash predictor (Fictitious play even fails in \textit{BertrandOligopoly}-3 and \textit{BertrandOligopoly}-4).
Our Nash predictor only needs one forward pass to develop a good approximate solution. 


\begin{figure*}[t]
    \centering
    \includegraphics[width=\textwidth]{fig/init_RD_loss_2.pdf}
    \caption{
    Experiment result of initializing replicator dynamics. 
    `RD' means replicator dynamics starting from random policy, and `RD+Initialization' represents RD initialized by our Nash predictor. Each experiment is run by $5$ different random seeds. 
    The average results and the $95\%$ confidence interval are shown.
    }
    \label{fig:init_RD_2}
\end{figure*}
\subsection{Initialize Replicator Dynamics}
\label{sec:addexp:RD}

We set the output solution of the trained predictor as the starting point for replicator dynamics. 
We present the experiment results for the remaining $4$ game classes in \cref{fig:init_RD_2}.
It can be seen that replicator dynamics with initialization always start with a lower Nash approximation loss and converges faster than the original version.

\section{Additional Theoretical Analysis}
\label{sec:proof}

\subsection{Proof of \cref{lemma:L_sigma}}
\label{sec:proof:L_sigma}
\begin{proof}[Proof of \cref{lemma:L_sigma}]
$\forall i \in N, \forall \sigma, \sigma'$, we have
\begin{equation}
\begin{aligned}
    |u_i(\sigma) - u_i(\sigma')|
    =& |u_i(\sigma_1, \sigma_2, \dots, \sigma_n) - u_i(\sigma'_1, \sigma'_2, \dots, \sigma'_n)| 
    \\
    =& \Big| \sum_{j=1}^n \Big(u_i(\sigma_1, \dots, \sigma_{j-1}, \sigma_j, \sigma'_{j+1}, \dots, \sigma'_n) - u_i(\sigma_1, \dots, \sigma_{j-1}, \sigma'_j, \sigma'_{j+1}, \dots, \sigma'_n) \Big)\Big|, 
    \\
    &\quad \text{define }y_{-j} := (\sigma_1, \dots, \sigma_{j-1}, \sigma'_{j+1}, \dots, \sigma'_n) 
    \\
    =& \Big| \sum_{j=1}^n \Big(u_i(\sigma_j, y_{-j}) - u_i(\sigma'_j, y_{-j}) \Big)\Big|
    \\
   
   
   
   
    =& \Big| \sum_{j=1}^n \sum_{a_j}(\sigma_j(a_j) - \sigma'_j(a_j)) \sum_{a_{-j}} u_i(a_j, a_{-j})y_{-j}(a_{-j})  \Big|
    \\
    \le& \sum_{j=1}^n \sum_{a_j}\Big|\sigma_j(a_j) - \sigma'_j(a_j)\Big|\sum_{a_{-j}} u_i(a_j, a_{-j})y_{-j}(a_{-j}) 
    \\
    \le& \sum_{j=1}^n \sum_{a_j}\Big|\sigma_j(a_j) - \sigma'_j(a_j)\Big|\sum_{a_{-j}}y_{-j}(a_{-j}),\quad\text{since }u_i(a_j, a_{-j}) \in [0, 1]
    \\
    \le& \sum_{j=1}^n \sum_{a_j\in A_j}\Big|\sigma_j(a_j) - \sigma'_j(a_j)\Big|
    \\
    =& \norm{\sigma - \sigma'}_1
\end{aligned}
\end{equation}
Therefore, $\forall a_i \in A_i$, 
\begin{equation}
\begin{aligned}
    u_i(a_i, \sigma_{-i}) - u_i(\sigma) =& u_i(a_i, \sigma_{-i}) - u_i(a_i, \sigma'_{-i}) + u_i(a_i, \sigma'_{-i}) - u_i(\sigma') + u_i(\sigma') - u_i(\sigma)
    \\
    \le& \norm{\sigma - \sigma'}_1 + \textsc{NashApr}(\sigma', u) + \norm{\sigma - \sigma'}_1
    \\
    =& \textsc{NashApr}(\sigma', u) + 2\norm{\sigma - \sigma'}_1.
\end{aligned}
\end{equation}
Based on this result, we get
\begin{equation}
\begin{aligned}
    \textsc{NashApr}(\sigma, u) 
    = \max_{i\in N, a_i \in A_i}[u_i(a_i, \sigma_{-i}) - u_i(\sigma)]
    \le \textsc{NashApr}(\sigma', u) + 2\norm{\sigma - \sigma'}_1
\end