# Multi-Agent Dynamical Systems (2/3)

This second blog-post of the multi-agent series is dedicated to *solution concepts*: how we can characterize and compare different joint policies.
We will cover Pareto optimality, the definition and existence of Nash equilibrium,
as well as the minimax theorem in two-agents zero-sum games.

In stark contrast with the single-agent case ($n=1$), calling some joint policy “optimal” in a multi-agent context ($n>1$) is ambiguous at best.
In a multi-agent setting, an outside observer considers the whole *joint* policy; that is,
the collection of *marginal* agent-centric controllers.
While each agent tries to maximise its own return or utility, asking said observer (having no *a-priori* preference over agents) to rank different joint policies is an ill-defined problem.

## Ranking joint policies

Consider a general-sum partially observable stochastic game $\mathcal{M} = (n, \mathcal{S}, \mathcal{A}, \Omega, p, q, \bm{r})$.
For the sake of simplicity, we assume here that agents pursue a discounted reward objective.
Formally, this means that the value of some joint policy $\bm{\pi}$ in the eyes of some agent $i$ is:
$$
v_i(\bm{\pi}) := \mathbb{E}^{\bm{\pi}}_\nu\left[\sum_{t\geq 1} \lambda^{t-1} r^i(s_t, \bm{a}_t)\right]\; ,
$$
where $\nu$ is some initial state distribution.
The joint value function $\bm{v}_\lambda(\bm{\pi})$ is simply the collection of the agents marginal values:
$
\bm{v}(\bm{\pi}) := (v_1(\bm{\pi}), \ldots, v_n(\bm{\pi}))\in\mathbb{R}^n\; .
$
For $\bm{\pi}_1, \bm{\pi}_2$ two given joint policies, there is no *a-priori*
way to establish a strict order between the two: $\bm{v}(\bm{\pi}_1)$ and $\bm{v}(\bm{\pi}_2)$ are not comparable.

The only non-ambiguous case concerns cooperative games (shared reward), where, by construction, for every joint $\bm{\pi}$ one has: $ v_1(\bm{\pi}) = \ldots = v_n(\bm{\pi})\; . $ The problem of raking policies collapses back to the single-agent case, since one can now look for an optimal policy w.r.t to the coalition’s value.

## Pareto Optimality

Even if, in general, we cannot provide a strict order over joint values, we can still establish some partial ordering.
Concretely, this means that some situations can clearly be preferred over others: for instance, when one comes with a joint
improvement over another. This is called *Pareto domination*.

A Pareto-dominated policy can be jointly improved; any agent’s return can be increased, without
hindering the return of the others.
Any policy that is not Pareto-dominated by another is called *Pareto-optimal*.
For any such policy, the return of an agent can no longer be improved without having another see its value drop.

It is easy to check that every finite game admits a Pareto-optimal policy. Often, there will exist several Pareto-optimal policies, not all of them being useful or relevant. For instance, in a zero-sum game, every joint policy is Pareto-optimal! (This is a direct result of the reward structure.) At the opposite end of the spectrum where lay cooperative games, all Pareto-optimal policies have the same value (and are therefore completely equivalent). This visible variability behind the interpretation of Pareto-optimality testifies of this concept’s relative weakness. It is useful to trim out some dull policies, but not much more. Game-theorists have therefore somewhat let go of the concept to develop stronger agent-centric solution concepts.

## Best-Response

A *best-response* policy is not a solution concept *per se* as it only concerns marginal policies.
The idea will however be quite useful to introduce the Nash equilibrium, a proper solution concept.
To understand what a best-response is, let’s fix some joint policy $\bm{\pi}$ and put ourselves in the shoes of some agent $i$.
If the joint policy $\bm{\pi}_{-i}$ of the other agents is known and fixed, then agent $i$’s path is straight-forward.
To maximize its return, it should follow a *best-response* to $\bm{\pi}_{-i}$: a
marginal policy $\pi_i$ which maximizes $v_i$ assuming $\bm{\pi}_{-i}$ will not change. Below, we will explicitly
split $\bm{\pi} = (\pi_i, \bm{\pi}_{-i})$.

## Nash Equilibrium

The concept of Nash equilibrium is relatively straight-forward, yet arguably one of the most influential in game theory.
A joint policy
$\bm{\pi}$ is a Nash equilibrium if each marginal policy $\pi_i$ is a best-response to the remaining $\bm{\pi}_{-i}$.
Intuitively, this comes with plenty of stability: for any agent, even if he knew the
strategies of the others, he would have no advantage to change his.
As a result, no agents have *a-priori* some interest to deviate from the current joint strategy.

In other words, a Nash-equilibrium policy $\bm{\pi}$ is such that $ \bm{\pi} \in \mathcal{T}^\text{br}(\bm{\pi}) \; . $

The first question that pops into our mind is whether such policies exist. That’s the point of Nash’s theorem, which we will state and prove shortly. Before that, let’s establish a few useful results. Below, we denote $\Pi_i = \Delta(\mathcal{A}_i)$ the policy space for agent $i$, and $\bm{\Pi} = \prod_{i=1}^n \Pi_i$ the joint-policy space. Our first claim establishes that there always exists a deterministic best-response policy.

**Claim 1.** For every $\bm{\pi}\in\bm{\Pi}$ and $i\in\{1, \ldots n\}$ there exists
a deterministic policy in $\mathcal{T}^\text{br}_i(\bm{\pi}_{-i})$.

**Proof**

Our second claim gives us a tool to identify some best-response stochastic policies. More precisely, it establishes that if some policy $\pi_i$ cannot be improved by any deterministic policy, then it is a best-response. To formalise this, let us introduce the coefficients: $$ \alpha_{ij}(\bm{\pi}) = \max(0, v_i(a_j, \bm{\pi}_{-i}) - v_i(\bm{\pi})), \qquad j\in\{1, \ldots, \vert \mathcal{A}_i\vert\}\; . $$

**Claim 2.** For every $i\in\{1, \ldots n\}$ and $\bm{\pi}=(\pi_i, \bm{\pi}_{-i})\in\bm{\Pi}$, if $\max_{j\in\{1, \ldots, n\}} \alpha_{ij}(\bm{\pi}) = 0$ then $\pi_i \in\mathcal{T}_i^\text{br}(\bm{\pi}_{-i})$.

**Proof**

We are now ready to claim and prove Nash’s theorem.

**Proof**

A game can have several, distinct Nash equilibria–each with different expected returns for each agent. There exists
many variation to this solution concept (*e.g.*, $\varepsilon$-Nash, correlated equilibrium) which we will not cover here.
Their point is to describe equilibria that are compatible with rounding errors, extra information, ..

## Maximin and Minimax

This section is concerned with two-players ($n=2$) zero-sum games. The maximin and minimax concepts seamlessly generalise to other games, but we will keep the focus on two-player zero-sum games for simplicity.

The

*maximin*strategy for some agent $i$ consists in the following rationale: follow a best-response policy, assuming that the other agent is acting to minimize my return. In other words, play a policy that maximize agent $i$’s pay-off, assuming the other agent is out to cause him the greatest harm. The maximin policy for agent $i$ is formally defined defined as: $$ \bar{\pi}_i \in \argmax_{\pi_i} \min_{\pi_{-i}} v_i(\pi_i, \pi_{-i})\;, $$ and the maximin value as $\max_{\pi_i} \min_{\pi_{-i}} v_i(\pi_i, \pi_{-i})$. The maximin value is also sometimes referred to as the*security level*. It is the minimum value agent $i$ can guarantee, regardless of its opponent’s strategy.The

*minimax*strategy sees things the other way around. When agent $i$ follows a minimax strategy, it abandons the maximisation of its own return in order to minimize its opponent’s value. Formally, the maximin policy for agent $i$ is defined as: $$ \pi_i \in \argmin_{\pi_i} \max_{\pi_{-i}} v_i(\pi_i, \pi_{-i})\;, $$ and the minimax value as $\min_{\pi_i} \max_{\pi_{-i}} v_i(\pi_i, \pi_{-i})$. The minimax value is the maximum return agent $i$ can force on its opponent.

A maximin (resp. minimax) solution concept is a joint policy $\bm\pi$ where each player follows a maximin (resp. minimax) strategy. In two-player zero-sum games, the two concepts blend with one another to yield the so-called minimax solution.

In a minimax solution, the minimax and maximin values of agent $i$ coincide. Such a solution always exists in finite games. Below, we claim and prove the Minimax Theorem, which establishes this result for matrix games. The minimax solution concept has tight links with the Nash equilibrium; actually, in a two-player zero-sum games, every Nash equilibrium is a minimax solution (see the proof).

**Proof**

## Resources

This blog post material was taken from [Shoham and Leyton-Brown, Chapter 3].