Quickstart

Installation

MFGLib provides pre-built wheels for Python 3.9+ and can be installed via pip on all major platforms.

$ pip install mfglib

Additionally, the source code is directly available on GitHub.

Introduction

MFGs

Informal

Multi-agent systems are ubiquitous in modern engineering applications. However, large-population systems present a challenge. Traditional \(N\)-players methods eventually break down as \(N \to \infty\).

An MFG is a type of mathematical model capable of describing systems with many, many agents. To accomplish this, we must assume

  1. The agents/players are indistinguishable and

  2. Any individual agent is negligible relative to the population.

These assumptions allow us to reduce the game to studying the interactions between an arbitrary representative agent and the population as a whole.

Formal

In what follows, \(\Delta_{X}\) denotes the set of probability distributions over a given finite set \(X\). Furthermore, if \(X\) and \(Y\) are two given finite sets, then \(X^Y\) denotes the set of maps from \(Y\) to \(X\).

Let \(\mathcal{T} \triangleq \{0, 1, \dots, T\}\) denote the set of timesteps, \(\mathcal{S} \triangleq \{1, 2, \dots, S\}\) be the state space, and \(\mathcal{A} \triangleq \{1, 2, \dots, A\}\) be the action space. We describe the representative agent by a policy \(\pi \in \left( \Delta_{\mathcal{A}} \right)^{\mathcal{T} \times \mathcal{S}}\), which assigns a distribution over actions to any timestep and state. We describe the population by a time-indexed joint state-action distribution denoted \(L \in \left( \Delta_{\mathcal{S} \times \mathcal{A}} \right)^{\mathcal{T}}\). We refer to \(L\) as the “mean-field”.

Given a fixed mean-field \(L\), the representative agent faces a standard Markov Decision Process, ie. she seeks a policy \(\pi\) to maximize her value function

\[V(\pi; L) \triangleq \mathbb{E}\left[ \sum_{t=0}^{T} \gamma^t r_t(s_t, a_t, L_t) \mid s_0 \sim \mu_0 \right]\]

subject to dynamics \(a_t \sim \pi_t(s_t)\) and \(s_{t + 1} \sim P(s_t, a_t, L_t)\). If every agent were to follow policy \(\pi\) it would induce a mean-field we denote by \(L^{\pi}\).

To “solve” a MFG we seek a Nash equilibrium (NE). A pair \(\left( \pi^*, L^* \right)\) is a NE if it meets two conditions:

  1. (optimality) \(\pi^* \in \arg \max_{\pi} V(\pi; L^*)\)

  2. (consistency) \(L^* = L^{\pi^*}\)

Example

In this section we describe a very simple MFG environment known as Left Right3.

We let a large number of agents simultaneously choose between going left \((\ell)\) or right \((\varrho)\). Afterwards, each agent shall be punished proportional to the number of agents that chose the same action, but more-so for choosing right than left.

Formally, let \(\mathcal{T} = \{0, 1\}, \mathcal{S} = \{c, \ell, \varrho \}, \mathcal{A} = \mathcal{S} \setminus \{c\}, \mu_0(c) = 1\) and define the reward function

\[r_t(s_t, a_t, L_t) = - \mathbf{1}_{\{ \ell \}} (s_t) \mu_t(\ell) - 2 \cdot \mathbf{1}_{\{ \varrho \}} (s_t) \mu_t(\varrho)\]

Note \(\mu_t(s) \triangleq \sum_{a \in \mathcal{A}} L_t(s, a)\) denotes the proportion of the population occupying state \(s\) at time \(t\). The transition kernel allows picking the next state directly, ie. for all \(s, s' \in \mathcal{S}\) and \(a \in \mathcal{A}\)

\[\Pr(s_{t + 1} = s' \mid s_t = s, a_t = a) = \mathbf{1}_{\{ s' \}}(a)\]

One can verify that any NE policy \(\pi^* = (\pi_0^*, \pi_1^*)\) must satisfy

\[\begin{split}\pi_0^*(c) \equiv \begin{bmatrix} \Pr(a_t = \ell \mid s_t = c) \\ \Pr(a_t = \varrho \mid s_t = c) \end{bmatrix} = \begin{bmatrix} \frac{2}{3} \\ \frac{1}{3} \end{bmatrix}\end{split}\]

Exploitability

For most MFGs, we may not be able to get a closed-form of their NE solutions. Therefore, in order to find how close a given policy is to an NE solution, we use a metric called exploitability.

Exploitability characterizes the suboptimality of a policy \(\pi\) against mean-field \(L^{\pi}\) as follows:

\[\text{Expl}(\pi) \triangleq \max_{\pi'} V(\pi'; L^{\pi}) - V(\pi; L^{\pi})\]

If \(\text{Expl}(\pi^*) \leq \epsilon\) for some \(\epsilon \geq 0\) then \(( \pi^*, L^{\pi^*} )\) is said to be an \(\epsilon\)-Nash equilibrium. If \(\epsilon = 0\) then \(( \pi^*, L^{\pi^*} )\) is an exact NE. For a more complete description of exploitability, refer to Guo et al.6.