\chapter{Stochastic Potential Games}
\label{chap:spg}

A large portion of works that approach MARL from a game theoretical prespective, have focused on either zero-sum \cite{leslie2020best,sayin2021decentralized,wei2021last,zhao2021provably}, or fully-cooperative games \cite{zhang2018fully,zhang2021finite,zhang2018model,zhang2019distributed,zhang2018networked}, and the study of other types of games have been limited. However, as discussed in Section~\ref{sec:mot}, an important family of games that connects cooperation and competition, and appears in numerous real-world scenarios, is potential games. Furthermore, every general-sum game can be decomposed into three games, a non-strategic game, a potential game, and a harmonic game \cite{candogan2011flows}. Therefore, studying MARL algorithms for stochastic potential games can be a step towards finding algorithms for arbitrary general-sum games.

\section[Related Works and Definitions]{Related Works and Definitions}
Stochastic (also known as dynamic or Markov) potential games were first studied outside the MARL framework and assuming that the dynamics of the environement are known, either with a centralized controller \cite{gonzalez2013discrete,macua2018learning,zazo2016dynamic}, or in a decentralized fashion \cite{mguni2018decentralised}. Recently, the study of SPGs from an RL prespective has become more prevalent. Extending the policy gradient method \cite{agarwal2021theory} to a multi-player setting, Leonardos et al. \cite{leonardos2021global} and Zhang et al. \cite{zhang2021gradient} proved the last iterate convergence of independent policy gradient (IPG) in SPGs. Fox et al. \cite{fox2022independent} showed the convergence of independent natural policy gradient (INPG), and experimentally showed its faster convergence compared to IPG. These three works define the SPG, and its corresponding potential function, based on the state value function of the agents. On the other hand, Mguni et al. \cite{mguni2021learning} provides an alternative definition based on reward functions in each state of the SG, and extend the game to continuous state and action spaces. They propose two algorithms for finding the Nash equilibrium in SPGs. The first one, SPotQ, is based on $Q$-learning and requires the potential function to be known. The second one, SPot-AC, is an actor-critic algorithm that needs to learn the potential function using minibatch data samples. Therefore, in both algorithms, the agents should be aware that the game is potential and either have to know or estimate the potential function. To best of our knowledge, up to know there has been no work adopting a pure value-based MARL approach in SPGs. In this thesis we consider the SPG formulation of Mguni et al. \cite{mguni2021learning} for discrete action spaces, and study such a value-based dynamics to bridge this gap. An SPG is defined as:

\begin{definition} [Stochastic potential game] \label{def:spg}
    A stochastic game is potential, if there exists a potential function $\Phi: \mathcal{S}\times \mathcal{A} \rightarrow R$ such that for every player $i\in \mathcal{N}$, every state $s \in \mathcal{S}$, and action profiles $(a_i, a_{-i}),(a'_i, a_{-i}) \in \mathcal{A}$, the following holds, 
    \begin{equation} \label{eq:spg}
        r_i(s, a_i, a_{-i}) - r_i(s, a_i', a_{-i}) = \Phi(s,a_i, a_{-i})-\Phi(s,a_i', a_{-i}).
    \end{equation}
\end{definition}

An intuitive condition that holds in many SPGs is state transitivity:

\begin{definition} [State transitivity] \label{def:stran}
    An SPG is said to be state transitive if for every player $i\in \mathcal{N}$, every action profile $(a_i, a_{-i}) \in \mathcal{A}$, and every state transition from $s$ to $s'$, the following holds, 
    \begin{equation} \label{eq:stran}
        r_i(s, a_i, a_{-i}) - r_i(s', a_i, a_{-i}) = \Phi(s,a_i, a_{-i})-\Phi(s',a_i, a_{-i}).
    \end{equation}
\end{definition}

In other words, when transiting to another state, the difference in rewards is the same for all agents. This assumption holds in many real-world applications of SPGs, such as network routing congestion games \cite{roughgarden2007routing} and distancing games \cite{leonardos2021global}. Similar to Mguni et al. \cite{mguni2021learning}, in our analysis, we also assume that state transitivity condition is satisfied.

\section[Benchmarks]{Benchmarks}
We consider two SPG benchmarks for experimental evaluation; network routing games, and distancing games. It is worth stating that the SPG literature is relatively young, and therefore, there are only few reported experimental results on these benchmarks.

\subsection{Network Routing Games}{Network Routing Games} \label{sec:networkrouting}
A network routing game is defined over an acyclic directed network of nodes, through which self-interested agents transfer their commodities. Passing through every edge has a cost that is proportional to the number of agents that are using the edge simultaneously. We consider an atomic routing game \cite{roughgarden2007routing} that involves $n$ agents who are transporting their commodities from a source node to a destination node. The atomic term implies that the commodity of each agent cannot be divided into smaller parts and should be transferred along a single edge. Figure~\ref{cong} shows two consecutive states of an atomic routing game with four agents. If we do not impose any restriction on the simultaneity of the agents' movement through the network, we will have a total of $|V|^n$ states in the MDP that constitutes the underlying SPG, where $|V|$ is the number of nodes in the network. In other words any configuration of the agents on different nodes is a state in the SPG. Every edge has a cost function $c_e(.)$, and therfore, each state of this SPG is a congestion game, and the potential function function is given by,

\begin{equation}
    \Phi(s,a^i,a^{-i}) = \sum_{e}\sum_{k=1}^{n_e}c(k)
\end{equation}

where $e$ is any edge that can be chosen as action by players in state $s$, and $n_e$ is the number of players who choose edge $e$.

\begin{figure}
    \centering
  \begin{subfigure}[b]{0.49\textwidth}
  \centering
  {\includegraphics[scale=0.19]{content/images/cong_intro1.pdf}}
  \end{subfigure}
    \hfill
 \begin{subfigure}[b]{0.49\textwidth}
  \centering
  {\includegraphics[scale=0.19]{content/images/cong_intro2.pdf}}
  \end{subfigure}
  \caption{Two consecutive states in an atomic network routing game}
   \label{cong}
\end{figure}

\subsection{Distancing Game} \label{sec:dist}
Distancing game \cite{fox2022independent} is an SPG environement that was introduced by Leonardos et al. \cite{leonardos2021global}, and consists of two states, both of which are congestion games. Each state has $m=4$ \emph{facilities} from which agents have to choose to stay when they are in that state. The first state is a safe state, and agents will receive a positive reward proportional to the value (weight) of their chosen facility and the number of agents in that facility. The weight of the facilities $\{A,B,C,D\}$ have the property $w_D>w_C>w_B>w_A$. Whenever there are more than $N/2$ number of agents in a single facility in the safe state, the agents will transit to the second state, \emph{spread} state. In this state, the agents receive a reward consisting of the same positive reward as the safe state, but with a large negative constant added to it. In order to transit back to the safe state, agents have to spread throughout the facilities as much as possible; if there are more than two $N/4$ players in the same facility, the agents stay in this harmful spread state until they spread and move back to the safe state. The potential function this game for each state is:

\begin{subequations}
\begin{equation}
    \Phi(s_{safe},a^i,a^{-i}) = \sum_{f}\sum_{k=1}^{n_f}kw_f,
\end{equation}
\begin{equation}
    \Phi(s_{spread},a^i,a^{-i}) = \sum_{f}\sum_{k=1}^{n_f}k(w_f-c),
\end{equation}
\end{subequations}

where $f$ is one of the facilities, and $n_f$ is the number of agents choosing facility $f$, and $c$ is the constant penalty term. Figure~\ref{fig:dist} shows a configuration of $n=8$ agents in the safe state.

\begin{figure}[h]
    \centering
       \includegraphics[width=0.75\linewidth]{content/images/dist_intro.pdf}
  \caption{Distancing game}
  \label{fig:dist} 
\end{figure}