# Game Theoretic Rating in N-player general-sum games with Equilibria

Luke Marris  Marc Lanctot  Ian Gemp  Shayegan Omidshafiei  Stephen McAleer
Jerome Connor  Karl Tuyls  Thore Graepel

###### Abstract

Rating strategies in a game is an important area of research in game theory
and artificial intelligence, and can be applied to any real-world competitive
or cooperative setting. Traditionally, only transitive dependencies between
strategies have been used to rate strategies (e.g. Elo), however recent work
has expanded ratings to utilize game theoretic solutions to better rate
strategies in non-transitive games. This work generalizes these ideas and
proposes novel algorithms suitable for N-player, general-sum rating of
strategies in normal-form games according to the payoff rating system. This
enables well-established solution concepts, such as equilibria, to be
leveraged to efficiently rate strategies in games with complex strategic
interactions, which arise in multiagent training and real-world interactions
between many agents. We empirically validate our methods on real world normal-
form data (Premier League) and multiagent reinforcement learning agent
evaluation.

Machine Learning, ICML

##  1 Introduction

Traditionally, rating systems assume transitive dependencies of strategies in
a game (such as Elo (Elo, 1978) and TrueSkill (Herbrich et al., 2007)). That
is, there exists an unambiguous ordering of all strategies according to their
relative strengths. This ignores all other interesting interactions between
strategies, including cycles where strategy S beats P beats R beats S in the
classic game of Rock, Paper, Scissors (Table 2). Many interesting games have
this so-called “strategic” dimension (Czarnecki et al., 2020), or “gamescapes”
(Balduzzi et al., 2018), that cannot be captured by pairwise transitivity
constraints.

Game theoretic rating of strategies is an emerging area of study which seeks
to overcome some of these drawbacks. These methods can be employed in normal-
form games, or in empirical games, constructed normal-form games where
strategies are policies competing in a multiagent interaction (e.g. a
simulation or a game) and the payoffs are approximate expected returns of the
players employing these policies (Wellman, 2006; Walsh et al., 2002; Tuyls et
al., 2020).

The Nash Average (NA) (Balduzzi et al., 2018) algorithm proposed a way of
rating strategies in two-player, zero-sum, normal-form games. This approach is
known as maximal lottery (Kreweras, 1965; Fishburn, 1984) in social choice
theory, where it first arose, and is so fundamental it has been rediscovered
across many fields (Brandt, 2017). In particular, NA proposed two applications
of rating: agent-vs-agent interactions and agent-vs-task interactions. NA
possesses a number of interesting properties: its ratings are invariant to
strategy duplication, and it captures interesting non-transitive interactions
between strategies. However, the technique is difficult to apply outside of
two-player, zero-sum domains due to computational tractability and equilibrium
selection difficulties. More recent work, $\alpha$-Rank (Omidshafiei et al.,
2019), sought to remedy this by introducing a novel computationally feasible
solution concept based on the stationary distribution a discrete-time
evolutionary process. Its main advantages concerns its uniqueness and
efficient computation in N-player and general-sum games.

This work expands game theoretic rating techniques to established equilibrium
concepts correlated equilibrium (CE) (Aumann, 1974), and coarse-correlated
equilibrium (CCE) (Moulin & Vial, 1978). In Section 2 we provide background to
rating algorithms, game theory, and equilibrium based solution concepts. In
particular, we describe CEs and CCEs that are suitable in the N-player,
general-sum setting. In Section 3 we define a novel general rating definition:
payoff rating, which is equivalent to NA if the game is two-player zero-sum.
Payoff rating is the expected payoff under a joint distribution, conditioned
on taking a certain strategy. The choice of joint distribution is what
provides payoff ratings with its interesting properties. In Section 4 we
suggest joint distributions to parameterize game theoretic rating algorithms.
In Section 5 we test these algorithms on instances of N-player, general-sum
games using real-world data. Finally, Section 6 is a discussion of the
connections of this work to other areas of machine learning and the relevance
of the work to machine learning.

##  2 Preliminaries

First we cover background on game theory (Section 2.1), rating and ranking
(Section 2.2), equilibria (Section 2.3), and game theoretic rating (Section
2.4).

###  2.1 Empirical Game Theory

A normal-form game is a single step game where all players take an action
simultaneously, and each receive a payoff. With n players, we denote a joint
strategy as the tuple $a=(a_{1},...,a_{n})\in\mathcal{A}$, where
$a_{p}\in\mathcal{A}_{p}$ is the strategy space available to player $p$. The
payoff given to player $p$ from a joint strategy $a$ is $G_{p}(a)$. A player’s
objective is to maximize their payoff in the presence of other players, who
are maximizing their own payoffs.

It is possible to construct normal-form game representations from observations
of much larger systems. This process is known as empirical game theoretic
analysis (EGTA) (Wellman, 2006; Walsh et al., 2002). The most common example
in artificial intelligence is when studying a set of policies111A mapping from
information states to actions. in large extensive form games (e.g., Chess or
Go). Often the set of policies is too large to enumerate entirely so we retain
a subset of them and track their performance against one another, therefore
constructing a normal-form game from the policies’ expected returns within the
environment (Lanctot et al., 2017). For example, a given season of the Premier
League can be modeled as a normal-form game involving a set of 20 team
policies, out of many possible football teams222The full permutation of all
players and coaches in the world.. EGTA has proved essential to multiagent
reinforcement learning (MARL) recently in scaling to human-level StarCraft
(Vinyals et al., 2019).

###  2.2 Rating and Ranking

Ranking is the problem of assigning a partial ordering to a set. Rating is the
more general problem of assigning a scalar value to each element of a set,
which then could be used to describe a ranking. The simplest rating procedure
is to take the mean performance of a strategy against all other strategies.
Viewed through a game theoretic lens, this is equivalent to assuming each
opponent strategy is equally likely to be encountered: the opponent player is
playing a uniform distribution. The key drawback of this approach is that it
is heavily influenced by the strategies available, and that an opponent
player, in practice, will favour their strongest strategies. This argument is
made thoroughly in Balduzzi et al. (2018).

Perhaps the best known rating algorithm is Elo (Elo, 1978). It is used to rate
players in many two-player, zero-sum games, most famously in Chess. It is also
commonly used for evaluating artificial agents in two-player settings (Silver
et al., 2016; Schrittwieser et al., 2019). The skill (Elo) of each competitor,
$a_{1}$, is described using a single variable $r(a_{1})$ which maps to a win
probability compared to other competitors, $a_{2}$,
$G_{1}(a_{1},a_{2})=(1-10^{\frac{r(a_{1})-r(a_{2})}{400}})^{-1}$. This
therefore defines a two-player, symmetric, constant-sum game where competitors
are strategies, with payoff defined as $G_{2}=1-G_{1}=G_{1}^{T}$. It is only
suitable for describing highly transitive games. Multi-dimensional Elo
(Balduzzi et al., 2018) is a method that attempts to overcome the limitations
of Elo by introducing additional variables for each competitor which describe
cyclic structure in the game. This gives a more accurate approximation of the
payoff, however it does not provide a way of rating strategies on its own333It
assigns vectors, not scalars, to strategies.. Decomposed Elo (Jaderberg et
al., 2019) is a method that works for $m$ vs $m$ constant-sum, team games. It
is capable of assigning a rating to each competitor in the team as well as a
rating for the team. However, it is also only suitable for transitive games,
both where team compositions and between-team interactions are transitive.

###  2.3 Equilibria

The joint strategy distribution over the set of all joint strategies is
denoted $\sigma(a)=\sigma(a_{1},...,a_{n})$, where
$\sum_{a\in\mathcal{A}}\sigma(a)=1$ and $\sigma(a)\geq 0\,\,\forall
a\in\mathcal{A}$. Furthermore we define the marginal strategy distribution as
$\sigma(a_{p})=\sum_{q\in-p}\sum_{a_{q}\in\mathcal{A}_{q}}\sigma(a_{1},...,a_{n})$,
where ${-p}=\\{1,...,p-1,p+1,...,n\\}$. Sometimes it is possible to factorize
the joint strategy distribution into its marginals
$\sigma(a)=\otimes_{p}\sigma(a_{p})$. Finally, the conditional distribution
$\sigma(a_{-p}|a_{p})=\frac{\sigma(a)}{\sigma(a_{p})}$ is defined if
$\sigma(a_{p})>0$. Sometimes we may denote the joint in terms of one players
strategies versus all other players:
$\sigma(a)\equiv\sigma(a_{1},...,a_{n})\equiv\sigma(a_{p},a_{-p})$.

A popular class of solution concepts are equilibrium based: joint
distributions, $\sigma(a)$, where under certain definitions, no player has
incentive to deviate. The most well known is Nash equilibrium (Nash, 1951)
(NE), which is tractable, interchangeable and unexploitable in two-player,
zero-sum games (Shoham & Leyton-Brown, 2009). NEs are always factorizable
joint distributions. A related solution concept is correlated equilibrium
(Aumann, 1974) (CE) which is more suitable for N-player, general-sum settings
where players are allowed to coordinate strategies with each other if it is
mutually beneficial. Furthermore, CEs are more compatible with the Bayesian
perspective, and arise as a result of learning rules (Foster & Vohra, 1997;
Cesa-Bianchi & Lugosi, 2006). The mechanism of implementing a CE is via a
correlation device which samples a joint strategy from a known public
distribution and recommends the sampled strategy secretly to each player. A
distribution is in correlated equilibrium if no player is incentivised to
unilaterally deviate from the recommendation after receiving it. CEs that are
factorizable are also NEs. An additional solution concept, the coarse
correlated equilibrium (Moulin & Vial, 1978) (CCE), requires players to commit
to the recommendation before it has been sampled. It is less computationally
expensive and permits even higher equilibrium payoffs. These sets are related
to each other $\text{NE}\subseteq\text{CE}\subseteq\text{CCE}$. The empirical
average policy of no-regret learning algorithms in self-play are known to
converge to CCEs (Foster & Vohra, 1997; Hart & Mas-Colell, 2000).

All these equilibria have approximate forms which are parameterized by the
approximation parameter $\epsilon$ which describes the maximum allowed
incentive to deviate to a best response (across all players). There are two
common methods of defining an approximate equilibrium: the standard
approximate equilibrium (Shoham & Leyton-Brown, 2009) describes the bound on
incentive to deviate under the joint, and the well-supported (WS) approximate
equilibrium (Goldberg & Papadimitriou, 2006) describes the bound on incentive
to deviate under the conditionals. When $\epsilon=0$, these definitions become
equivalent. The standard method has the property that any
$\epsilon>\epsilon^{\min}$ will permit a full-support equilibrium (Section A),
where $\epsilon^{\min}\leq 0$ is the minimum $\epsilon$ that permits a
feasible solution in a game. Each player may have individual tolerances to
deviation, $\epsilon_{p}$. For the rest of this work we only consider the
standard definition, similar derivations can be adopted for the well-supported
definition.

CEs can be defined in terms of linear inequality constraints, defined in terms
of the deviation gain of a player:
$A^{\text{CE}}_{p}(a^{\prime}_{p},a_{p},a_{-p})=G_{p}(a^{\prime}_{p},a_{-p})-G_{p}(a_{p},a_{-p})$,
$a^{\prime}_{p}\neq a_{p}\in\mathcal{A}_{p},a_{p}\in\mathcal{A}_{p},\forall
p$, where each constraint corresponds to a pair of strategies: $a_{p}$
deviating to $a^{\prime}_{p}$.

$\epsilon$-CE:
$\displaystyle\smashoperator[]{\sum_{a_{-p}\in\mathcal{A}_{-p}}^{}}\sigma(a_{p},a_{-p})A^{\text{CE}}_{p}(a^{\prime}_{p},a_{p},a_{-p})$
$\displaystyle\leq\epsilon_{p}$ (1)

CCEs can be derived from the CE definition by summing over strategies
available to a player: $\sum_{a_{p}}\sigma(a_{p})(\cdot)$, therefore there is
only a constraint for each possible deviation
$a^{\prime}_{p}\in\mathcal{A}_{p},\forall p$ with a deviation gain of
$A^{\text{CCE}}_{p}(a^{\prime}_{p},a)=G_{p}(a^{\prime}_{p},a_{-p})-G_{p}(a)$.

$\epsilon$-CCE:
$\displaystyle\smashoperator[]{\sum_{a\in\mathcal{A}}^{}}\sigma(a_{p},a_{-p})A^{\text{CCE}}_{p}(a^{\prime}_{p},a)$
$\displaystyle\leq\epsilon_{p}$ (2)

NEs have similar definitions to CEs but have an extra constraint: the joint
distribution factorizes $\otimes_{p}\sigma(a_{p})=\sigma(a)$, resulting in
nonlinear constraints444This is why NEs are harder to compute than (C)CEs..

$\epsilon$-NE:
$\displaystyle\smashoperator[]{\sum_{a_{-p}\in\mathcal{A}_{-p}}^{}}\otimes_{q}\sigma(a_{q})A^{\text{CE}}_{p}(a^{\prime}_{p},a_{p},a_{-p})$
$\displaystyle\leq\epsilon_{p}$ (3)

When a distribution is in equilibrium, no player has incentive to
_unilaterally_ deviate from it to achieve a better payoff. There can however
be many equilibria in a game, choosing amongst these is known as the
_equilibrium selection problem_ (Harsanyi & Selten, 1988).

For NEs it has been suggested to use a maximum entropy criterion (MENE)
(Balduzzi et al., 2018), which always exists and is unique in two-player,
constant-sum settings. Another strategy is to regularize the NE of the game
with Shannon entropy resulting in the quantal response equilibrium (QRE)
(McKelvey & Palfrey, 1995). There exists a continuum of QREs starting at the
uniform distribution, finishing at the limiting logit equilibrium (LLE), which
is unique for almost all games. Solvers (Gemp et al., 2021) can find LLEs,
even in scenarios with stochastic payoffs.

(C)CEs permit a convex polytope of valid solutions which are defined by their
linear inequality constraints. Convex functions can be used to uniquely select
from this set. Multiple objectives have been proposed to select from the set
of valid solutions including maximum entropy,
$-\sum_{a}\sigma(a)\ln(\sigma(a))$ (ME(C)CE) (Ortiz et al., 2007), maximum
Gini, $\sum_{a}1-\sigma(a)^{2}$ (MG(C)CE) (Marris et al., 2021a), and maximum
welfare555Not convex and hence not always unique.,
$\sum_{p}\sum_{a}\sigma(a)G_{p}(a)$ (MW(C)CE).

###  2.4 Game Theoretic Rating

It is natural to formulate rating problems as rating strategies in a normal-
form game. For example, a football league is a symmetric, two-player game
where strategies are teams and payoffs are win probabilities or points. Teams
can therefore be ranked by analysing this empirical game. Single player multi-
task reinforcement learning can be formulated as a game between an agent
player and an environment player, with strategies describing different
policies and different tasks respectively (Balduzzi et al., 2018). We call the
problem of assigning a rating to each player’s strategies the _game theoretic
rating problem_. While any joint distribution can be used to calculate a
rating (Section 3), game theoretic distributions, such as ones that are in
equilibrium have a number of advantages.

Nash Average (Balduzzi et al., 2018) leverages the properties of NE to rate
strategies in two-player, zero-sum games according to the payoff rating
definition (Section 3.1). This approach can also be used to rate relative
strengths between populations of strategies in sub-games: relative population
performance (RPP) (Balduzzi et al., 2019; Czarnecki et al., 2020). It also has
an interesting property that it is invariant to strategy repeats.

Using NEs to rate general-sum games has not been explored, however LLEs
(McKelvey & Palfrey, 1995) could be leveraged to select an equilibrium that is
unique in _almost_ all games. However it is difficult to compute and
sophisticated solvers such as gambit-logit (Turocy, 2005; McKelvey et al.,
2016) do not scale well to large N-player games (Gemp et al., 2021). In
contrast, (C)CEs which have not been considered as rating algorithms until
now, a) have a convex optimization formulation, b) have unique principled
equilibrium selection, c) can capture coordination in games, d) are
established and understood, and e) have a number of interesting rating
properties.

##  3 Game Theoretic Rating

We introduce a novel generalized rating for N-player, general-sum: the _payoff
rating_. The definition functions for arbitrary joint strategy distributions,
however we propose using equilibrium distributions to ensure the rating is
game theoretic.

###  3.1 Payoff Rating

The rating is defined terms of the payoff, $G_{p}$, and the joint distribution
players are assumed to be playing under, $\sigma$. We define the payoff
rating:

$\displaystyle r^{\sigma}_{p}(a_{p})$
$\displaystyle=\frac{\partial}{\partial\sigma(a_{p})}~{}~{}\smashoperator[]{\sum_{a\in\mathcal{A}}^{}}G_{p}(a)\sigma(a)$
(4)
$\displaystyle=\frac{\partial}{\partial\sigma(a_{p})}~{}~{}\smashoperator[]{\sum_{a_{-p}\in\mathcal{A}_{-p}}^{}}G_{p}(a_{p},a_{-p})\sigma(a_{-p}|a_{p})\sigma(a_{p})$
$\displaystyle=\smashoperator[]{\sum_{a_{-p}\in\mathcal{A}_{-p}}^{}}G_{p}(a_{p},a_{-p})\sigma(a_{-p}|a_{p})$
(5)

######  Theorem 3.1.

(Nash Average Equivalence) When using an MENE for the joint strategy
distribution in two-player, zero-sum games, payoff rating is equivalent to
Nash Average (NA).

###### Proof.

For NE, a player’s strategies are independent from the other player’s
strategies, $\sigma(a_{2}|a_{1})=\sigma(a_{2})$. Therefore
$r^{\sigma}_{1}(a_{1})=\sum_{a_{2}\in\mathcal{A}_{2}}G_{1}(a_{1},a_{2})\sigma(a_{2})$
and
$r^{\sigma}_{2}(a_{2})=\sum_{a_{1}\in\mathcal{A}_{1}}G_{2}(a_{1},a_{2})\sigma(a_{1})$,
which is the definition of NA. ∎

This definition has two interpretations: a) the change in the player’s payoff
under a joint strategy distribution,
$\sum_{a\in\mathcal{A}}G_{p}(a)\sigma(a)$, with respect to the probability of
selecting that strategy, $\sigma(a_{p})$ b) the expected strategy payoff under
a joint strategy distribution conditioned on that strategy. When defined, the
payoff rating is bounded between the minimum and maximum values of a
strategy’s payoff, $\min_{a}G_{p}(a_{p},a_{-p})\leq
r^{\sigma}_{p}(a_{p})\leq\max_{a}G_{p}(a_{p},a_{-p})$.

Note the mathematical edge case that strategies with zero marginal
probability, $\sigma(a_{p})=0$, have undefined conditional probability,
$\sigma(a_{-p}|a_{p})$, and therefore have undefined payoff rating. Consider a
symmetric two-player zero-sum transitive game where strategy $S$ dominates
$A$, and $A$ dominates $W$. Many game theoretic distributions (including NE,
CE and CCE) will place all probability mass on $(S,S)$, leaving strategies $A$
and $W$ with undefined rating. This may be unsatisfying for two reasons;
firstly that there could be a further ordering between $A$ and $W$ such that
$S>A>W$ reflected in the ranking, and secondly, that all strategies should
receive a rating value. It could argued that if a strategy dominates all
others then an ordering over the rest is redundant. However there are ways to
achieve ordering, a) with approximate equilibria (Section 4), certain joint
strategies (such as $\epsilon^{\min+}$-MECCE) are guaranteed to place at least
some mass on all strategies (Section A), b) assign
$r^{\sigma}_{p}(a)=\min_{a}G_{p}(a)$ for undefined values, and c) rate using a
sub-game with dominating strategies pruned.

###  3.2 Joint Strategy Distributions

We now turn our discussion to the joint distributions we measure such a rating
under. The most ubiquitous approach is the uniform distribution which is
equivalent to calculating the mean payoff across all opponent strategies. As
discussed previously, this approach does not consider any interesting dynamics
of the game. It is, however, the distribution with maximum entropy and
therefore makes the fewest assumptions (Jaynes, 1957) .

In order to be more game theoretic, using distributions that are in certain
types of _equilibrium_ is beneficial. Firstly, consider the definitions of
several equilibria (Equations (1)-(3)). These equations are linear666In joint
distribution space. inequality constraints between strategies, so already
closely resemble a partial ordering. Rankings are nothing more than partial
orderings between elements. Secondly, values of the payoff ratings depend
entirely on the payoffs under distributions that all players are not
incentivized to deviate from. Therefore this set of joint distributions are
representative of ones which rational agents may employ in practice. In
contrast, the uniform distribution is rarely within an equilibrium set.
Therefore, we argue, equilibrium distributions are a much more natural
approach. Further mathematical justification is given in Section B.

It is possible to mix the opinionated properties of an equilibrium with the
zero-assumption properties of the uniform: there exists a principled continuum
between the uniform distribution and an equilibrium distribution (Marris et
al., 2021a) to achieve this balance. The uniform distribution is recovered
when using a large enough approximation parameter
$\epsilon_{p}\geq\epsilon_{p}^{\text{uni}}$. The value of
$\epsilon_{p}^{\text{uni}}$ depends on the solution concept, and can be
determined directly from a payoff (Section A).

###  3.3 Properties of Equilibria Ratings

Naively, one may want a rating strategy to differentiate the strategies it is
rating. Game theoretic rating does the opposite: it groups strategies into
similar ratings that _should not_ be differentiated, such as strategies that
are in a cycle with one another (Tables 0(a), and 0(b)). We call this
phenomenon the _grouping property_. Other properties, such as strategic
dominance resulting in dominated ratings, and consistent ratings over repeated
strategies or between players in a symmetric game can also be achieved when
using the maximum entropy criterion (Section B).

##  4 Rating Algorithms

A generalized payoff rating algorithm (Algorithm 1) is therefore parameterized
over an equilibrium concept, and an equilibrium selection criterion. This
section makes some recommendations on suitable parameterizations.

Algorithm 1 Generalized Payoff Rating

$\sigma(a)\leftarrow\textsc{ConceptAndSelection}(G(a),\epsilon)$$p\leftarrow
1...n$$r^{\sigma}_{p}(a_{p})\leftarrow\smashoperator[]{\sum_{a_{-p}\in\mathcal{A}_{-p}}^{}}G_{p}(a_{p},a_{-p})\sigma(a_{-p}|a_{p})$$(r^{\sigma}_{1}(a_{1}),...,r^{\sigma}_{n}(a_{n}))$

###  4.1 $\epsilon^{\min+}$-MECCE Payoff Rating

We recommend using Coarse Correlated Equilibrium (CCE) as the joint strategy
distribution, maximum entropy (ME) for the equilibrium selection function. We
consider the solution when $\epsilon\to\epsilon^{\min}$ (or equivalently with
a sufficiently small $\epsilon=\epsilon^{\min+}$), where $\epsilon^{\min}\leq
0$ is the minimum approximation parameter that permits a feasible solution
(Section A) (Marris et al., 2021b). We call the resulting rating
$\epsilon^{\min+}$-MECCE Payoff Rating.

Using CCEs as the solution concept has a number of advantages: a) full joint
distributions allow cooperative as well as competitive games to be rated;
factorizable distributions such as NE struggle with cooperative components of
a game b) CCEs are more tractable to compute than CEs and NEs, c) full-support
CCEs only require a single variable per strategy to define777With the payoff
tensor., d) they are amenable to equilibrium selection because it permits a
convex polytope of solutions, e) under a CCE, no player has incentive to
deviate from the joint (possibly correlated) distribution to any of their own
strategies unilaterally since it would not result in higher payoff, and f) the
empirical joint strategy of no-regret algorithms in self-play converge to a
CCE.

In combination with CCEs, ME with any $\epsilon>\epsilon^{\min}$ (Section A)
spreads at least some mass over all joint strategies (“full support” (Ortiz et
al., 2007)) meaning that the conditional distribution, and hence the payoff
rating, is always well defined. This equilibrium selection method is also
invariant under affine transforms (Marris et al., 2021a) of the payoff, scales
well to large numbers of players and strategies, and is principled in that it
makes minimal assumptions about the distribution (Jaynes, 1957). Empirically,
it groups strategies within strategic cycles with each other. Using a solution
near $\epsilon^{\min}$ allows for a strong, high value equilibrium to be
selected which is particularly important for coordination games.

###  4.2 $\frac{\epsilon}{\epsilon^{\text{uni}}}$-MECCE Payoff Rating

A drawback of using $\epsilon=\epsilon^{\min+}$ is that sometimes (usually
when strategies are strictly dominated by others) the distribution needs to be
computed to a very high precision, otherwise numerical issues will complicate
the calculation of the conditional distributions.

In order to mitigate this problem let us use an approximate equilibrium
distribution which will spread more mass. It is advantageous to normalize the
approximation parameter(Marris et al., 2021a),
$\frac{\epsilon}{\epsilon^{\text{uni}}}$, where $\epsilon^{\text{uni}}$ is the
minimum $\epsilon$ that permits the uniform distribution in the feasible set.
When $\frac{\epsilon}{\epsilon^{\text{uni}}}=1$ the uniform distribution is
selected by ME, when $\frac{\epsilon}{\epsilon^{\text{uni}}}=0$ the MECCE
solution is recovered. For some games, it is possible to set
$\frac{\epsilon}{\epsilon^{\text{uni}}}\leq 0$ to produce ratings with very
robust distributions. This is similar in idea to the continuum of QREs
(McKelvey & Palfrey, 1995). Figure 7 shows how ratings change with
$\frac{\epsilon}{\epsilon^{\text{uni}}}$ for a two-player, zero-sum game.

##  5 Experiments

In order to build intuition and demonstrate the flexibility of the rating
algorithms presented, this section shows ratings for a number of standard and
real world data games. We compare against uniform and $\alpha$-Rank rating
methods. Section F contains further experiments.

###  5.1 Standard Normal Form Games

First let us consider the payoff, equilibrium and payoff ratings of some two-
player normal-form games (Table 1). RPS has three strategies in a cycle, and
therefore equilibrium ratings dictate that we cannot differentiate between
their strengths. This is true even if the cycles are biased (Table 0(a)) for
the MECCE rating. In this case the probability mass is spread unevenly but the
resulting payoff rating is equal for all the strategies in the cycle, grouping
them together. $\alpha$-Rank does not produce equal payoff ratings for BRPS,
but _does_ spread mass equally (not shown in the table). The uniform payoff
incorrectly ungroups these strategies. It is also possible to construct a
general-sum game with two sets of cycles where one cycle “dominates” the other
(Table 0(b)). MECCE successfully groups the ratings of each of the cycles.

In prisoner’s Dilemma (Table 0(c)) the dominant joint strategy receives all
the mass (using slightly above $\epsilon^{\min}$ means $(C,D)$ also gets some
mass). Uniform rating results in the correct ordering in transitive games, but
with less intuitive values. In Bach or Stravinsky (Table 0(d)) and the
coordination game (Table 0(e)) MECCE is able to perfectly correlate actions to
give better mutual payoffs. LLE is unsatisfactory on coordination games
because factorizable distributions cannot exploit coordination opportunities.
Interestingly, in the chicken game (Table 0(f)) $C$ has better payoff rating
than $S$ because it is the strategy that gives the highest payoff when the
other player swerves. This is an example of when the the uniform rating gives
a different ordering to the payoff rating.

Table 1: Player 1’s payoff ratings for standard games. ER:
$\epsilon^{\min+}$-MECCE. LR: LLE. $\alpha$R: $\alpha$-Rank. UR: uniform.

(a) Biased Rock, Paper, Scissors ($G_{2}=1-G_{1}=G_{1}^{T}$).

$G_{1}$ | R | P | S
---|---|---|---
R | $\frac{1}{2}$ | $\frac{2}{10}$ | $1$
P | $\frac{8}{10}$ | $\frac{1}{2}$ | $\frac{3}{10}$
S | $0$ | $\frac{7}{10}$ | $\frac{1}{2}$

$\sigma^{\text{ER}}$ | R | P | S
---|---|---|---
R | $.04$ | $.10$ | $.06$
P | $.10$ | $.25$ | $.15$
S | $.06$ | $.15$ | $.09$

$r_{1}^{\sigma}$ | ER | LR |  $\alpha$R∗ | UR
---|---|---|---|---
R | $.5$ | $.5$ | $.567$ | $.567$
P | $.5$ | $.5$ | $.533$ | $.533$
S | $.5$ | $.5$ | $.400$ | $.400$

(b) Dominated Biased Rock, Paper, Scissors ($G_{2}=G_{1}^{T}$)

$G_{1}$ | BRPS |  $\frac{1}{2}$BRPS
---|---|---
BRPS | $G_{1}^{\text{BRPS}}$ | $0$
$\frac{1}{2}$BRPS | $0$ | $\frac{1}{2}G_{1}^{\text{BRPS}}$

$\sigma^{\text{ER}}$ | BRPS |  $\frac{1}{2}$BRPS
---|---|---
BRPS | $\frac{1}{3}\sigma^{\text{BRPS}}$ | $0$
$\frac{1}{2}$BRPS | $0$ | $\frac{2}{3}\sigma^{\text{BRPS}}$

$r_{1}^{\sigma}$ | ER | LR |  $\alpha$R | UR
---|---|---|---|---
R | $0.5$ | $0.5$ | $0.479$ | $0.283$
P | $0.5$ | $0.5$ | $0.511$ | $0.267$
S | $0.5$ | $0.5$ | $0.444$ | $0.200$

$r_{1}^{\sigma}$ | ER | LR |  $\alpha$R | UR
---|---|---|---|---
$\frac{1}{2}$R | $0.25$ | $0.0$ | $0.239$ | $0.142$
$\frac{1}{2}$P | $0.25$ | $0.0$ | $0.256$ | $0.133$
$\frac{1}{2}$S | $0.25$ | $0.0$ | $0.222$ | $0.100$

(c) Prisoner’s Dilemma.

$G_{p}$ | C | D
---|---|---
C |  $-1$, $-1$ |  $-3$, $0$
D |  $0$, $-3$ |  $-2$, $-2$

$\sigma^{\text{ER}}$ | C | D
---|---|---
C | $0^{+}$ | $0^{\par}$
D | $0^{\par}$ | $1$

$r_{1}^{\sigma}$ | ER | LR |  $\alpha$R | UR
---|---|---|---|---
C | $-3$ | $-3$ | -3 | $-2$
D | $-2$ | $-2$ | -2 | $-1$

(d) Bach or Stravinsky.

$G_{p}$ | B | S
---|---|---
B |  $3$, $2$ |  $0$, $0$
S |  $0$, $0$ |  $2$, $3$

$\sigma^{\text{ER}}$ | B | S
---|---|---
B | $\frac{1}{2}$ | $0$
S | $0$ | $\frac{1}{2}$

$r_{1}^{\sigma}$ | ER | LR |  $\alpha$R | UR
---|---|---|---|---
B | $3$ | $1.2$ | $3$ | $\frac{3}{2}$
S | $2$ | $1.2$ | $2$ | $1$

(e) Preferential Pure Coordination ($G_{2}=G_{1}$).

$G_{p}$ | P | L
---|---|---
P | $1$ | $0$
L | $0$ | $\frac{1}{2}$

$\sigma^{\text{ER}}$ | P | L
---|---|---
P | $\frac{1}{3}$ | $0$
L | $0$ | $\frac{2}{3}$

$r_{1}^{\sigma}$ | ER | LR |  $\alpha$R | UR
---|---|---|---|---
P | $1$ | $1$ | $1$ | $\frac{1}{2}$
L | $\frac{1}{2}$ | $0$ | $\frac{1}{2}$ | $\frac{1}{4}$

(f) Chicken.

$G_{p}$ | C | S
---|---|---
C | $-10$ |  $1$, $-1$
S |  $-1$, $1$ | $0$

$\sigma^{\text{ER}}$ | C | S
---|---|---
C | $0$ | $\frac{1}{2}$
S | $\frac{1}{2}$ | $0$

$r_{1}^{\sigma}$ | ER | LR |  $\alpha$R | UR
---|---|---|---|---
C | $1$ | $-0.1$ | $1$ | $-\frac{9}{2}$
S | $-1$ | $-0.1$ | $-1$ | $-\frac{1}{2}$

(a) P1 payoff, $G_{1}(a_{1},a_{2})$

(b) $0^{+}$-ME(C)CE $\sigma(a_{1},a_{2})$

(c) $0^{+}$-ME(C)CE $\sigma(a_{2}|a_{1})$

(d) Ratings, $r_{1}^{\sigma}(a_{1})$

Figure 1: Symmetric, two-player, zero-sum Premier League game where players
pick between clubs as strategies. The clubs are ordered according to their
average win probability. The conditional distribution is recovered from very
small mass present in the joint distribution (MENE/CE/CCE shown). Log scales
of the joint distribution can be found in Figure 7(a).

(a) $G_{2}(H,a_{2},a_{3})$

(b) Location ratings, $r_{1}^{\sigma}(a_{1})$

(c) Home ratings, $r_{2}^{\sigma}(a_{2})$

(d) Away ratings, $r_{3}^{\sigma}(a_{3})$

(e) $0.1$-MECCE Home joint slice, $\sigma(H,a_{2},a_{3})$

(f) $0.1$-MECCE Away joint slice, $\sigma(A,a_{2},a_{3})$

(g) $0.1$-MECE Home joint slice, $\sigma(H,a_{2},a_{3})$

(h) $0.1$-MECE Away joint slice, $\sigma(A,a_{2},a_{3})$

Figure 2: Three-Player Premier League game where the players are location vs
home club vs away club. The resulting payoff tensor is of shape $3\times
2\times 20\times 20$ and joint strategy distribution is shaped $2\times
20\times 20$. All slices of the payoff are either arithmetic inverse or
transpose of the data shown in Figure 2(a). The clubs are ordered the same as
in Figure 1.

###  5.2 Zero-Sum Premier League Ratings

We consider a two-player, zero-sum, symmetric win probability888In practice,
the Premier League is general-sum with 3 points for a win, 1 point each for a
draw, and 0 points for a loss. representation of clubs playing against each
other in the 2018/2019 season of the premier league. Figure 1(a) shows win
rates between clubs. For example, we can see that Liverpool is very strong and
beats every club apart from Man City. Although Man City can beat Liverpool,
Man City draws against four other clubs: Chelsea, Leicester, Crystal Palace
and Newcastle, the latter three being middle of the table. Furthermore,
Chelsea beats Crystal Palace, Crystal Palace beats Leicester, and Leicester
beats Chelsea. Newcastle at best draws against Leicester. Therefore there is a
weak cycle including Man City, Chelsea, Leicester and Crystal Palace, where
Man City can threaten Liverpool. Because of this cycle, all these clubs have
strategic relevance, and therefore should be rated equally highly by a game
theoretic rating technique.

The $0^{+}$-ME(C)CE rating spreads the majority of the mass (Figure 1(b)) over
clubs within this cycle. Note that for two-player, zero-sum games, exact CCE,
CE and NE distributions are identical, and are therefore factorizable.
Although it cannot be observed in the figure, there is nonzero support for
every joint strategy and the conditional distribution (Figure 1(c)) reflects
this. The payoff rating (Figure 1(d)) is identical for all strategies with
nonzero NE support (see Section B.1 for an explanation).

Furthermore, we study the $\frac{\epsilon}{\epsilon^{\text{uni}}}$-MECCE mass
(Figure 7(a)) and payoff (Figure 7(b)) ratings when varying
$\frac{\epsilon^{\min+}}{\epsilon^{\text{uni}}}=0^{+}\leq\frac{\epsilon}{\epsilon^{\text{uni}}}\leq
1$. We can observe that some clubs (including Leicester, Crystal Palace and
Newcastle which are in a weak cycle with Man City) improve their rankings as
the rankings as the joint distribution nears the $0^{+}$-MECCE solution.

###  5.3 Three-Player Premier League Ratings

Using the same data we introduce another player, the location player, which
has two strategies: home or away. The location player gets a point if the club
playing in the location it selects wins. The clubs get a point if they win
irrespective of what the location player plays. This results in a three-
player, general-sum game: location vs home club vs away club (Figure 2(a)).

This time we consider ratings using an approximate equilibrium with
$\frac{\epsilon}{\epsilon^{\text{uni}}}=0.1$. As expected, the location
player’s ratings (Figure 2(b)) favour the home strategy (reflecting the well-
known home advantage phenomenon). The performance of clubs at home (Figure
2(c)) is high. The away performance (Figure 2(d)) of Leicester and Crystal
Palace earn them top payoff ratings even though they are in the middle of the
table.

###  5.4 Multiagent Learning Dynamics

It is well-known that the general multiagent reinforcement learning (MARL)
problem is challenging due to nonstationarity (Hernandez-Leal et al., 2017),
limited theoretical guarantees (Zhang et al., 2021), computational resource
requirements and implementation challenges (Hernandez-Leal et al., 2019).
Often there is a lack of “ground truth” to quantify the behavior of the
algorithms; hence, the field has developed tools to analyze their dynamics
qualitatively (Bloembergen et al., 2015). In this subsection, we demonstrate
the use of ratings that change over time as an analysis tool for (MARL)
dynamics. In particular, ratings allow game-theoretic relative performance to
be assessed over time. For all experiments in this section, we use OpenSpiel
(Lanctot et al., 2019) agents, with some additional custom agents and
experimental setups.

Figure 3: Two-Player General-Sum Sheriff. Figure 4: Three-Player General-Sum
Goofpsiel.

We run experiments where agents in a population play against each other.
Players play an $n$-player game; the population has $n$ instantiations of each
of 8 agent types (Random, Deep Q-networks (DQN) (Mnih et al., 2015), Neural
Fictitious Self-Play (NFSP) (Heinrich & Silver, 2016), Advantage Actor-Critic
(A2C) (Mnih et al., 2016), Online MCCFR (Lanctot et al., 2009), Tabular Actor
Critic, QPG, and RPG (Srinivasan et al., 2018)), for a total of $8n$ agents.
At the start of each episode, an agent type is uniformly sampled for each
player, and observations are extended to include each player’s agent type.

We show two environments: the general-sum game of Sheriff (Farina et al.,
2019b) (Figure 3) and the three-player general-sum game of Goofspiel (Farina
et al., 2019a) (Figure 4). It is clear to observe the grouping properties of
$\epsilon^{\min+}$-MECCE payoff ratings: when the agents have learned policies
that are in strategic cycles with one another their ratings are grouped,
allowing for a fairer description of the relative strengths of each policy.
This information cannot be learned from studying uniform ratings alone.
$\epsilon^{\min+}$-MECEE therefore provides a remarkable way of summarizing
the complex interactions of strategies in N-player general-sum games into an
interpretable scalar value for each strategy.

##  6 Discussion

Considering the payoff ratings when $\epsilon\to\epsilon^{\min}$ gives a
mathematically sound way of ensuring all joint strategies have positive mass.
Furthermore, using a normalised $\frac{\epsilon}{\epsilon^{\text{uni}}}$
allows a smooth parameterized transition from traditional uniform payoff
rating to game theoretic payoff rating. Equilibria have a grouping property
that ensures strategies that are in strategic cycles with one another have
similar ratings. Maximum entropy is a principled way to select amongst
equilibria and also gives consistent ratings across symmetric games and
repeated strategies.

Formulating the environment as a player (Balduzzi et al., 2018) in an agent vs
environment game is an interesting way of ensuring the distribution of tasks
(strategies available to the environment player) does not bias the ratings of
the agents training on those tasks. In Sections 5.3 and F.4 we examined
environment vs agent vs agent games demonstrating that these ideas can be
extended to multiagent learning. Indeed a multiagent inspired path to
developing increasingly intelligent agents has been proposed (Bansal et al.,
2018; Leibo et al., 2019) based on the richness of such dynamics.

As well as evaluating agents (Section 5.4), payoff ratings could also be used
as a fitness function to evaluate agents within a population to drive an
evolutionary algorithm, for example like in population based training (PBT)
(Jaderberg et al., 2019). $\alpha$-PSRO (Muller et al., 2020) can be seen as
optimizing agents for the $\alpha$-Rank mass rating. Similarly, JPSRO (Marris
et al., 2021b) can be seen as optimizing agents for the MGCE payoff rating.

An emerging line of research called _gamification_ (Gemp et al., 2020) seeks
to reinterpret existing problems as games, and apply game theory to improve
upon the solutions. Problems with multiple objectives, constraints,
competitiveness are potentially amenable to gamification. The ranking problem
is suitable for this approach because it is defined in terms of a partial
ordering (inequality constraints), can have multiple players, and is
inherently competitive.

##  7 Conclusions

In this work we have developed methods for generalising game theoretic rating
techniques to N-player, general-sum settings, using the novel payoff rating
definition. This builds upon fundamental rating techniques developed in two-
player, zero-sum evaluation. We suggest some parameterizations of these
algorithms and show ratings results on real world data to demonstrate its
flexibility and ability to summarize complex strategic interactions. Finally,
we demonstrate the power of this rating as a MARL evaluation technique.

## References

  * Anthony et al. (2020) Anthony, T., Eccles, T., Tacchetti, A., Kramár, J., Gemp, I., Hudson, T. C., Porcel, N., Lanctot, M., Pérolat, J., Everett, R., et al.  Learning to play no-press Diplomacy with best response policy iteration.  _arXiv preprint arXiv:2006.04635_ , 2020.
  * Aumann (1974) Aumann, R.  Subjectivity and correlation in randomized strategies.  _Journal of Mathematical Economics_ , 1(1):67–96, 1974.
  * Balduzzi et al. (2018) Balduzzi, D., Tuyls, K., Perolat, J., and Graepel, T.  Re-evaluating evaluation.  In _Proceedings of the 32nd International Conference on Neural Information Processing Systems_ , NIPS, pp. 3272–3283, Red Hook, NY, USA, 2018\. Curran Associates Inc.
  * Balduzzi et al. (2019) Balduzzi, D., Garnelo, M., Bachrach, Y., Czarnecki, W., Perolat, J., Jaderberg, M., and Graepel, T.  Open-ended learning in symmetric zero-sum games.  In _International Conference on Machine Learning_ , pp. 434–443. PMLR, 2019.
  * Bansal et al. (2018) Bansal, T., Pachocki, J., Sidor, S., Sutskever, I., and Mordatch, I.  Emergent complexity via multi-agent competition.  In _Proceedings of the Sixth International Conference on Learning Representations_ , 2018.
  * Bloembergen et al. (2015) Bloembergen, D., Tuyls, K., Hennes, D., and Kaisers, M.  Evolutionary dynamics of multi-agent learning: A survey.  _Journal of Artificial Intelligence Research_ , 53:659–697, 2015.
  * Brandt (2017) Brandt, F.  Fishburn’s Maximal Lotteries.  _Workshop on Decision Making and Contest Theory_ , 1 2017.
  * Cesa-Bianchi & Lugosi (2006) Cesa-Bianchi, N. and Lugosi, G.  _Prediction, Learning, and Games_.  Cambridge University Press, 2006.
  * Czarnecki et al. (2020) Czarnecki, W. M., Gidel, G., Tracey, B., Tuyls, K., Omidshafiei, S., Balduzzi, D., and Jaderberg, M.  Real world games look like spinning tops.  _Advances in Neural Information Processing Systems_ , 33, 2020.
  * Du et al. (2021) Du, Y., Yan, X., Chen, X., Wang, J., and Zhang, H.  Estimating $\alpha$-rank from a few entries with low rank matrix completion.  In _International Conference on Machine Learning_ , pp. 2870–2879. PMLR, 2021.
  * Elo (1978) Elo, A. E.  _The rating of chessplayers, past and present_.  Arco Pub., New York, 1978.  ISBN 0668047216 9780668047210.
  * Farina et al. (2019a) Farina, G., Bianchi, T., and Sandholm, T.  Coarse correlation in extensive-form games, 2019a.
  * Farina et al. (2019b) Farina, G., Ling, C. K., Fang, F., and Sandholm, T.  Correlation in extensive-form games: Saddle-point formulation and benchmarks.  In _Conference on Neural Information Processing Systems (NeurIPS)_ , 2019b.
  * Fishburn (1984) Fishburn, P. C.  Probabilistic social choice based on simple voting comparisons.  _The Review of Economic Studies_ , 51(4):683–692, 1984.  ISSN 00346527, 1467937X.  URL http://www.jstor.org/stable/2297786.
  * Foster & Vohra (1997) Foster, D. P. and Vohra, R. V.  Calibrated learning and correlated equilibrium.  _Games and Economic Behavior_ , 21:40–55, 1997.
  * Gemp et al. (2020) Gemp, I. M., McWilliams, B., Vernade, C., and Graepel, T.  Eigengame: PCA as a nash equilibrium.  _CoRR_ , abs/2010.00554, 2020.  URL https://arxiv.org/abs/2010.00554.
  * Gemp et al. (2021) Gemp, I. M., Savani, R., Lanctot, M., Bachrach, Y., Anthony, T. W., Everett, R., Tacchetti, A., Eccles, T., and Kramár, J.  Sample-based approximation of nash in large many-player games via gradient descent.  _CoRR_ , abs/2106.01285, 2021.  URL https://arxiv.org/abs/2106.01285.
  * Goldberg & Papadimitriou (2006) Goldberg, P. W. and Papadimitriou, C. H.  Reducibility among equilibrium problems.  In _Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing_ , STOC ’06, pp. 61–70, New York, NY, USA, 2006. Association for Computing Machinery.  ISBN 1595931341.  doi: 10.1145/1132516.1132526.  URL https://doi.org/10.1145/1132516.1132526.
  * Harsanyi & Selten (1988) Harsanyi, J. and Selten, R.  _A General Theory of Equilibrium Selection in Games_ , volume 1.  The MIT Press, 1 edition, 1988.
  * Hart & Mas-Colell (2000) Hart, S. and Mas-Colell, A.  A simple adaptive procedure leading to correlated equilibrium.  _Econometrica_ , 68(5):1127–1150, 2000.
  * Heinrich & Silver (2016) Heinrich, J. and Silver, D.  Deep reinforcement learning from self-play in imperfect-information games.  _CoRR_ , abs/1603.01121, 2016.
  * Herbrich et al. (2007) Herbrich, R., Minka, T., and Graepel, T.  Trueskill™: A bayesian skill rating system.  In Schölkopf, B., Platt, J. C., and Hoffman, T. (eds.), _Advances in Neural Information Processing Systems 19_ , pp. 569–576. MIT Press, 2007.
  * Hernandez-Leal et al. (2017) Hernandez-Leal, P., Kaisers, M., Baarslag, T., and de Cote, E. M.  A survey of learning in multiagent environments: Dealing with non-stationarity, 2017.
  * Hernandez-Leal et al. (2019) Hernandez-Leal, P., Kartal, B., and Taylor, M. E.  A survey and critique of multiagent deep reinforcement learning.  _Autonomous Agents and Multi-Agent Systems volume_ , 33:750–797, 2019.
  * Jaderberg et al. (2019) Jaderberg, M., Czarnecki, W., Dunning, I., Marris, L., Lever, G., Castañeda, A., Beattie, C., Rabinowitz, N., Morcos, A., Ruderman, A., Sonnerat, N., Green, T., Deason, L., Leibo, J., Silver, D., Hassabis, D., Kavukcuoglu, K., and Graepel, T.  Human-level performance in 3d multiplayer games with population-based reinforcement learning.  _Science_ , 364(6443):859–865, 05 2019.
  * Jaynes (1957) Jaynes, E. T.  Information theory and statistical mechanics.  _Phys. Rev._ , 106:620–630, May 1957.
  * Kreweras (1965) Kreweras, G.  Aggregation of preference orderings.  _Mathematics and Social Sciences I: Proceedings of the seminars of Menthon-Saint-Bernard, France (1–27 July 1960) and of Gösing, Austria (3–27 July 1962)_ , pp. 73–79, 1965.
  * Lanctot et al. (2009) Lanctot, M., Waugh, K., Zinkevich, M., and Bowling, M.  Monte Carlo sampling for regret minimization in extensive games.  In Bengio, Y., Schuurmans, D., Lafferty, J., Williams, C. K. I., and Culotta, A. (eds.), _Advances in Neural Information Processing Systems 22_ , pp. 1078–1086, 2009.
  * Lanctot et al. (2017) Lanctot, M., Zambaldi, V., Gruslys, A., Lazaridou, A., Tuyls, K., Perolat, J., Silver, D., and Graepel, T.  A unified game-theoretic approach to multiagent reinforcement learning.  In _NIPS_. 2017.
  * Lanctot et al. (2019) Lanctot, M., Lockhart, E., Lespiau, J.-B., Zambaldi, V., Upadhyay, S., Pérolat, J., Srinivasan, S., Timbers, F., Tuyls, K., Omidshafiei, S., Hennes, D., Morrill, D., Muller, P., Ewalds, T., Faulkner, R., Kramár, J., Vylder, B. D., Saeta, B., Bradbury, J., Ding, D., Borgeaud, S., Lai, M., Schrittwieser, J., Anthony, T., Hughes, E., Danihelka, I., and Ryan-Davis, J.  OpenSpiel: A framework for reinforcement learning in games.  _CoRR_ , 2019.
  * Leibo et al. (2019) Leibo, J. Z., Hughes, E., Lanctot, M., and Graepel, T.  Autocurricula and the emergence of innovation from social interaction: A manifesto for multi-agent intelligence research, 2019.
  * Marris et al. (2021a) Marris, L., Muller, P., Lanctot, M., Tuyls, K., and Graepel, T.  Multi-agent training beyond zero-sum with correlated equilibrium meta-solvers.  _CoRR_ , abs/2106.09435, 2021a.  URL https://arxiv.org/abs/2106.09435.
  * Marris et al. (2021b) Marris, L., Muller, P., Lanctot, M., Tuyls, K., and Graepel, T.  Multi-agent training beyond zero-sum with correlated equilibrium meta-solvers.  In Meila, M. and Zhang, T. (eds.), _Proceedings of the 38th International Conference on Machine Learning_ , volume 139 of _Proceedings of Machine Learning Research_ , pp. 7480–7491. PMLR, 18–24 Jul 2021b.  URL http://proceedings.mlr.press/v139/marris21a.html.
  * McKelvey & Palfrey (1995) McKelvey, R. D. and Palfrey, T.  Quantal response equilibria for normal form games.  _Games and Economic Behavior_ , 10(1):6–38, 1995\.
  * McKelvey et al. (2016) McKelvey, R. D., McLennan, A. M., and Turocy, T. L.  Gambit: Software tools for game theory, version 16.0.1, 2016.
  * McMahan et al. (2003) McMahan, H. B., Gordon, G. J., and Blum, A.  Planning in the presence of cost functions controlled by an adversary.  In _Proceedings of the 20th International Conference on Machine Learning (ICML-03)_ , pp. 536–543, 2003.
  * Mnih et al. (2015) Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., Veness, J., Bellemare, M. G., Graves, A., Riedmiller, M., Fidjeland, A. K., Ostrovski, G., Stig Petersen, C. B., Sadik, A., Antonoglou, I., King, H., Kumaran, D., Wierstra, D., Legg, S., and Hassabis, D.  Human-level control through deep reinforcement learning.  _Nature_ , 518:529–533, 2015.
  * Mnih et al. (2016) Mnih, V., Badia, A. P., Mirza, M., Graves, A., Lillicrap, T. P., Harley, T., Silver, D., and Kavukcuoglu, K.  Asynchronous methods for deep reinforcement learning.  In _Proceedings of the 33rd International Conference on Machine Learning (ICML)_ , pp. 1928–1937, 2016.
  * Moulin & Vial (1978) Moulin, H. and Vial, J.-P.  Strategically zero-sum games: the class of games whose completely mixed equilibria cannot be improved upon.  _International Journal of Game Theory_ , 7(3-4):201–221, 1978.
  * Muller et al. (2020) Muller, P., Omidshafiei, S., Rowland, M., Tuyls, K., Perolat, J., Liu, S., Hennes, D., Marris, L., Lanctot, M., Hughes, E., Wang, Z., Lever, G., Heess, N., Graepel, T., and Munos, R.  A generalized training approach for multiagent learning.  In _International Conference on Learning Representations_ , 2020.
  * Nash (1951) Nash, J.  Non-cooperative games.  _Annals of Mathematics_ , 54(2):286–295, 1951\.
  * Omidshafiei et al. (2019) Omidshafiei, S., Papadimitriou, C., Piliouras, G., Tuyls, K., Rowland, M., Lespiau, J.-B., Czarnecki, W. M., Lanctot, M., Perolat, J., and Munos, R.  $\alpha$-rank: Multi-agent evaluation by evolution.  _Scientific Reports_ , 9(1):9937, 2019.
  * Ortiz et al. (2007) Ortiz, L. E., Schapire, R. E., and Kakade, S. M.  Maximum entropy correlated equilibria.  In Meila, M. and Shen, X. (eds.), _Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics_ , volume 2 of _Proceedings of Machine Learning Research_ , pp. 347–354, San Juan, Puerto Rico, 21–24 Mar 2007. PMLR.
  * Rashid et al. (2021) Rashid, T., Zhang, C., and Ciosek, K.  Estimating $\alpha$-rank by maximizing information gain.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 35, pp. 5673–5681, 2021.
  * Rowland et al. (2019) Rowland, M., Omidshafiei, S., Tuyls, K., Perolat, J., Valko, M., Piliouras, G., and Munos, R.  Multiagent evaluation under incomplete information.  _arXiv preprint arXiv:1909.09849_ , 2019.
  * Schrittwieser et al. (2019) Schrittwieser, J., Antonoglou, I., Hubert, T., Simonyan, K., Sifre, L., Schmitt, S., Guez, A., Lockhart, E., Hassabis, D., Graepel, T., Lillicrap, T. P., and Silver, D.  Mastering atari, go, chess and shogi by planning with a learned model.  _CoRR_ , abs/1911.08265, 2019.  URL http://arxiv.org/abs/1911.08265.
  * Shoham & Leyton-Brown (2009) Shoham, Y. and Leyton-Brown, K.  _Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations_.  Cambridge University Press, 2009.
  * Silver et al. (2016) Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., Van Den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M., et al.  Mastering the game of go with deep neural networks and tree search.  _nature_ , 529(7587):484–489, 2016.
  * Srinivasan et al. (2018) Srinivasan, S., Lanctot, M., Zambaldi, V., Pérolat, J., Tuyls, K., Munos, R., and Bowling, M.  Actor-critic policy optimization in partially observable multiagent environments.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , 2018.
  * Turocy (2005) Turocy, T. L.  A dynamic homotopy interpretation of the logistic quantal response equilibrium correspondence.  _Games and Economic Behavior_ , 51(2):243–263, 2005.
  * Tuyls et al. (2020) Tuyls, K., Pérolat, J., Lanctot, M., Hughes, E., Everett, R., Leibo, J. Z., Szepesvári, C., and Graepel, T.  Bounds and dynamics for empirical game theoretic analysis.  _Auton. Agents Multi Agent Syst._ , 34(1):7, 2020\.
  * Vinyals et al. (2019) Vinyals, O., Babuschkin, I., Czarnecki, W., Mathieu, M., Dudzik, A., Chung, J., Choi, D., Powell, R., Ewalds, T., Georgiev, P., Oh, J., Horgan, D., Kroiss, M., Danihelka, I., Huang, A., Sifre, L., Cai, T., Agapiou, J., Jaderberg, M., and Silver, D.  Grandmaster level in starcraft ii using multi-agent reinforcement learning.  _Nature_ , 575, 11 2019.
  * Walsh et al. (2002) Walsh, W., Das, R., Tesauro, G., and Kephart, J.  Analyzing complex strategic interactions in multi-agent systems.  01 2002.
  * Wellman (2006) Wellman, M. P.  Methods for empirical game-theoretic analysis.  In _Proceedings, The Twenty-First National Conference on Artificial Intelligence and the Eighteenth Innovative Applications of Artificial Intelligence Conference, July 16-20, 2006, Boston, Massachusetts, USA_ , pp. 1552–1556. AAAI Press, 2006.  URL http://www.aaai.org/Library/AAAI/2006/aaai06-248.php.
  * Zhang et al. (2021) Zhang, K., Yang, Z., and Başar, T.  _Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms”, bookTitle=”Handbook of Reinforcement Learning and Control_ , pp. 321–384.  Springer International Publishing, Cham, 2021.  ISBN 978-3-030-60990-0.  doi: 10.1007/978-3-030-60990-0˙12.  URL https://doi.org/10.1007/978-3-030-60990-0_12.

##  Appendix A Equilibria Properties

This section discusses two properties of approximate equilibria: when they
have full-support solutions and the minimum approximation parameter that will
permit the uniform distribution to be the solution.

###  A.1 Standard Matrix Form

Because the equilibria constraints are linear, it is possible to represent the
constraints in standard matrix form.

######  Lemma A.1.

The deviation gain functions, $A^{\text{CE}}_{p}(a^{\prime}_{p},a_{p},a_{-p})$
and $A^{\text{CCE}}_{p}(a^{\prime}_{p},a)$, can be expressed as sparse
matrices, $A^{\text{CE}}_{p}$ and $A^{\text{CCE}}_{p}$, with shapes
$[|\mathcal{A}_{p}|^{2},|\mathcal{A}|]$ and
$[|\mathcal{A}_{p}|,|\mathcal{A}|]$. These can be concatenated into a single
matrices $A^{\text{CE}}$ and $A^{\text{CCE}}$, with shapes
$[\sum_{p}|\mathcal{A}_{p}|^{2},|\mathcal{A}|]$ and
$[\sum_{p}|\mathcal{A}_{p}|,|\mathcal{A}|]$, such that when combined with a
flattened joint distribution vector, $\sigma$, the equilibria constraints can
be specified in standard form: $A^{\text{CE}}\sigma\leq\epsilon$ and
$A^{\text{CCE}}\sigma\leq\epsilon$.

###### Proof.

Let us temporarily consider $A^{\text{CE}}_{p}$ to be a tensor of shape
$[|\mathcal{A}_{p}|,|\mathcal{A}_{p}|,|\mathcal{A}_{1}|,...,|\mathcal{A}_{n}|]$.
Let us define:

$\displaystyle A^{\text{CE}}_{p}[a^{\prime}_{p},$ $\displaystyle
a^{r}_{p},a_{1},...,a_{p},....,a_{n}]=$
$\displaystyle\begin{cases}G(a^{\prime}_{p},a_{-p})-G(a_{p},a_{-p})&a^{r}_{p}=a_{p}\\\
0&\text{otherwise}\end{cases}$ (6)

By reshaping into $[|\mathcal{A}_{p}|^{2},|\mathcal{A}|]$ we can see by
inspection that this recovers the matrix that fits the criteria of the lemma.

Also, let us temporarily consider $A^{\text{CCE}}_{p}$ to be a tensor of shape
$[|\mathcal{A}_{p}|,|\mathcal{A}_{1}|,...,|\mathcal{A}_{n}|]$. Let us define:

$\displaystyle
A^{\text{CCE}}_{p}[a^{\prime}_{p},a_{1},...,a_{p},....,a_{n}]=G(a^{\prime}_{p},a_{-p})-G(a)$
(7)

By reshaping into $[|\mathcal{A}_{p}|,|\mathcal{A}|]$ we can see by inspection
that this recovers the matrix that fits the criteria of the lemma. ∎

###  A.2 Full Support Conditions

Approximate equilibria are useful because they permit full-support solutions.
Full-support solutions produce well-defined payoff ratings for all strategies.

######  Theorem A.2 (Approximate Full-Support Existence).

Using a positive $\epsilon$, $\epsilon$-NE, $\epsilon$-CE and $\epsilon$-CCE
will always contain a full-support solution in the feasible space for any
finite game with finite payoffs.

###### Proof.

Using the standard form matrix notation we can desribe the convex polytope of
feasible solutions is defined by the space defined by the halfspaces
$A\sigma\leq\epsilon$. It is known that for (C)CEs there always exists a
solution when $\epsilon=0$, however this solution is not necessarily full-
support. Starting from a solution when $\epsilon=0$, if we move probability
mass $\delta$ from one joint strategy to another with zero mass, this produces
a violation bounded by $\delta(\max(A)-\min(A))$. In the worst case we have to
do this for every joint strategy, $a\in\mathcal{A}$. Therefore an approximate
solution with $\epsilon$ will permit solutions with:

$\delta\geq\frac{\epsilon}{|\mathcal{A}|(\max(A)-\min(A))}$ (8)

Therefore there will exist a solution with probability mass $\delta>0$ if the
game is finite, $|\mathcal{A}|<\infty$, and has finite payoffs,
$|\max(A)-\min(A)|<\infty$. The proof for $\epsilon$-NE is similar but we move
mass from marginal strategies rather than joint strategies. ∎

We sometimes therefore use the notation $\epsilon=0^{+}$ when we want to find
a full-support solution close to the equilibrium. Some games have feasible
solutions even for negative values of approximation parameter, $\epsilon$. It
is therefore possible to have a full-support solution when $\epsilon<0$ for
some games.

######  Remark A.3 (Negative Approximate Full-Support Existence).

Using approximation parameters $\epsilon_{p}>\epsilon_{p}^{\min}~{}\forall p$
in $\epsilon$-CE and $\epsilon$-CCE will always contain a full-support
solution in the feasible space in any finite game with finite payoffs, where
$\epsilon_{p}^{\min}$ is any set of minimal $\epsilon_{p}$ which solves
$\arg\min_{\epsilon_{p}}A_{p}\sigma\leq\epsilon_{p}~{}\forall p$.

Furthermore, the maximum Shannon entropy is guaranteed to select such a full-
support solution if one exists.

######  Theorem A.4 ($\epsilon$-ME Full-Support Solution).

Using an $\epsilon>\epsilon^{\min}$, $\epsilon$-MECE and $\epsilon$-MECCE will
select full-support approximate equilibria (Ortiz et al., 2007).

###### Proof.

Noting the existence of a feasible full-support solution from Theorem A.2, we
only need to prove that the maximum entropy objective will select such a full-
support solution. The objective for the Shannon entropy is
$L=\sum_{a\in\mathcal{A}}-\sigma(a)\ln(\sigma(a))$, and its derivative is
$\frac{\partial L}{\partial\sigma(a)}=-(\ln(\sigma(a))+1)$, which is infinite
when the mass is zero, $\frac{\partial
L}{\partial\sigma(a)}|_{\sigma(a)=0}=\infty$ and finite when $\sigma(a)>0$.
Therefore, by considering the objective landscape, solutions that are not on
the surface of the probability simplex as selected. ∎

Other selection methods, like linear objectives and maximum Gini do not have
this property because they have finite gradient when $\sigma(a)=0$, and
therefore may not leave the boundary of the probability simplex.

###  A.3 Minimum Uniform Approximation

Another property of $\epsilon$-(C)CEs is that it is possible to determine the
minimum $\epsilon$ that will include the uniform distribution in the feasible
set just by examining the payoff tensor.

######  Theorem A.5 (Minimum Uniform $\epsilon$-CE and $\epsilon$-NE).

The uniform distribution is feasible for $\epsilon$-CE and $\epsilon$-NE when
using approximation parameter:

$\displaystyle\epsilon_{p}$ $\displaystyle\geq\epsilon_{p}^{\text{uni}}$
$\displaystyle=\max_{a^{\prime}_{p},a_{p}}\smashoperator[]{\sum_{a_{-p}\in\mathcal{A}_{-p}}^{}}\frac{1}{|\mathcal{A}|}A^{\text{CE}}_{p}(a^{\prime}_{p},a_{p},a_{-p})$
(9)
$\displaystyle=\frac{1}{|\mathcal{A}|}\left(\max_{a^{\prime}_{p}}\smashoperator[]{\sum_{a_{-p}\in\mathcal{A}_{-p}}^{}}G_{p}(a^{\prime}_{p},a_{-p})-\min_{a_{p}}\smashoperator[]{\sum_{a_{-p}\in\mathcal{A}_{-p}}^{}}G_{p}(a_{p},a_{-p})\right)$

###### Proof.

Consider the definition of the constraints of the $\epsilon$-CE (Equation (1))
and the $\epsilon$-NE (Equation (3)):

$\displaystyle\smashoperator[]{\sum_{a_{-p}\in\mathcal{A}_{-p}}^{}}\sigma(a_{p},a_{-p})A^{\text{CE}}_{p}(a^{\prime}_{p},a_{p},a_{-p})$
$\displaystyle\leq\epsilon_{p}~{}\forall a^{\prime}_{p}\neq
a_{p}\in\mathcal{A}_{p},\forall p$

We can ignore the additional condition that NE must also factorize because we
will substitute the joint distribution with the uniform distribution later,
which factorizes. Instead of considering all the constraints
$a^{\prime}_{p}\neq a_{p}\in\mathcal{A}_{p}$, equivalently, we only need to
consider the constraint with the maximum violation:

$\displaystyle\max_{a^{\prime}_{p},a_{p}}\smashoperator[]{\sum_{a_{-p}\in\mathcal{A}_{-p}}^{}}\sigma(a_{p},a_{-p})A^{\text{CE}}_{p}(a^{\prime}_{p},a_{p},a_{-p})$
$\displaystyle\leq\epsilon_{p}~{}\forall p$

We wish to find the minimum $\epsilon_{p}$ such that the uniform distribution
is a feasible solution. We can do this by substituting
$\sigma(a)=\frac{1}{|\mathcal{A}|}$:

$\displaystyle\max_{a^{\prime}_{p},a_{p}}\smashoperator[]{\sum_{a_{-p}\in\mathcal{A}_{-p}}^{}}\frac{1}{|\mathcal{A}|}A^{\text{CE}}_{p}(a^{\prime}_{p},a_{p},a_{-p})$
$\displaystyle\leq\epsilon_{p}~{}\forall p$

Finally, $\epsilon_{p}^{\text{uni}}$ can be defined in terms of only the
payoffs:

$\displaystyle\epsilon_{p}^{\text{uni}}$
$\displaystyle=\max_{a^{\prime}_{p},a_{p}}\smashoperator[]{\sum_{a_{-p}\in\mathcal{A}_{-p}}^{}}\frac{1}{|\mathcal{A}|}A^{\text{CE}}_{p}(a^{\prime}_{p},a_{p},a_{-p})$
$\displaystyle=\frac{1}{|\mathcal{A}|}\max_{a^{\prime}_{p},a_{p}}\smashoperator[]{\sum_{a_{-p}\in\mathcal{A}_{-p}}^{}}\left(G_{p}(a^{\prime}_{p},a_{-p})-G_{p}(a_{p},a_{-p})\right)$
$\displaystyle=\frac{1}{|\mathcal{A}|}\left(\max_{a^{\prime}_{p}}\smashoperator[]{\sum_{a_{-p}\in\mathcal{A}_{-p}}^{}}G_{p}(a^{\prime}_{p},a_{-p})-\min_{a_{p}}\smashoperator[]{\sum_{a_{-p}\in\mathcal{A}_{-p}}^{}}G_{p}(a_{p},a_{-p})\right)$

∎

######  Theorem A.6 (Minimum Uniform $\epsilon$-CCE).

The uniform distribution is feasible for $\epsilon$-CCE when using
approximation parameter:

$\displaystyle\epsilon_{p}$ $\displaystyle\geq\epsilon_{p}^{\text{uni}}$
$\displaystyle=\max_{a^{\prime}_{p}}\smashoperator[]{\sum_{a\in\mathcal{A}}^{}}\frac{1}{|\mathcal{A}|}A^{\text{CCE}}_{p}(a^{\prime}_{p},a)$
(10)
$\displaystyle=\frac{1}{|\mathcal{A}|}\left(|\mathcal{A}_{p}|\max_{a^{\prime}_{p}}\smashoperator[r]{\sum_{a_{-p}\in\mathcal{A}_{-p}}^{}}G_{p}(a^{\prime}_{p},a_{-p})-\smashoperator[]{\sum_{a\in\mathcal{A}}^{}}G_{p}(a)\right)$

###### Proof.

Similar to Theorem A.5. We arrive at:

$\displaystyle\epsilon_{p}^{\text{uni}}$
$\displaystyle=\max_{a^{\prime}_{p}}\smashoperator[]{\sum_{a_{-p}\in\mathcal{A}_{-p}}^{}}\frac{1}{|\mathcal{A}|}A^{\text{CCE}}_{p}(a^{\prime}_{p},a)$
$\displaystyle=\frac{1}{|\mathcal{A}|}\max_{a^{\prime}_{p}}\smashoperator[]{\sum_{a\in\mathcal{A}}^{}}\left(G_{p}(a^{\prime}_{p},a_{-p})-G_{p}(a)\right)$
$\displaystyle=\frac{1}{|\mathcal{A}|}\left(\max_{a^{\prime}_{p}}\smashoperator[]{\sum_{a\in\mathcal{A}}^{}}G_{p}(a^{\prime}_{p},a_{-p})-\smashoperator[]{\sum_{a\in\mathcal{A}}^{}}G_{p}(a)\right)$
$\displaystyle=\frac{1}{|\mathcal{A}|}\left(|\mathcal{A}_{p}|\max_{a^{\prime}_{p}}\smashoperator[r]{\sum_{a_{-p}\in\mathcal{A}_{-p}}^{}}G_{p}(a^{\prime}_{p},a_{-p})-\smashoperator[]{\sum_{a\in\mathcal{A}}^{}}G_{p}(a)\right)$

∎

##  Appendix B Justification and Intuition

A payoff can be arbitrarily mapped to a scalar for each strategy in a game to
achieve a rating. For a rating definition to be compelling one must motivate
why it is more interesting than other mappings.

The main text makes some intuitive arguments about why game theoretic
equilibrium methods are appropriate rating algorithms. Namely, that ratings
are defined under joint distributions in equilibrium, so no player has
incentive to unilaterally deviate from them. This is in contrast to the
uniform distribution which is rarely an equilibrium.

This section makes mathematical arguments to justify and build intuition
behind the equilibrium concepts and the ratings they define. To do this we
explore a number of properties each equilibrium concept possesses. The first
such property is _grouping_ , a game theoretic property that enforces
strategies that are strategic cycle with one another should get equal or
similar ratings. The second property that we consider is dominance of
strategies in terms of their payoffs translates to dominance of payoff ratings
too. Thirdly, we examine whether ratings are consistent when we repeat
strategies or are part of a symmetric game.

###  B.1 NE

Grouping. A curious property of the NE payoff rating (Nash Average (Balduzzi
et al., 2018)) is that all strategies with positive support have equal
rating999See Figure 1(d) for an example.. We call this property the _grouping
property_ , where strategies in strategic cycles together are grouped with
similar ratings despite perhaps having very different payoffs.

######  Theorem B.1 ($\epsilon$-NE Grouping).

Strategies for $0$-NE payoff ratings with positive support have equal payoff
rating. Strategies for $\epsilon$-NE payoff ratings with positive support have
ratings bounded by:

$\left|r^{\sigma}_{p}(a^{\prime}_{p})-r^{\sigma}_{p}(a_{p})\right|\leq\max\left[\frac{\epsilon_{p}}{\sigma(a_{p})},\frac{\epsilon_{p}}{\sigma(a^{\prime}_{p})}\right]$
(11)

###### Proof.

Consider the $\epsilon$-NE constraints (Equation 3) between strategies $a_{p}$
and $a^{\prime}_{p}$. First expand the definition of the deviation gain and
observe that the definitions of the NE payoff ratings appear directly in the
constraints.

$\displaystyle\quad\smashoperator[]{\sum_{a_{-p}\in\mathcal{A}_{-p}}^{}}\sigma(a_{p})\sigma(a_{-p})G_{p}(a^{\prime}_{p},a_{-p})$
$\displaystyle\leq\smashoperator[]{\sum_{a_{-p}\in\mathcal{A}_{-p}}^{}}\sigma(a_{p})\sigma(a_{-p})G_{p}(a_{p},a_{-p})+\epsilon_{p}$
$\displaystyle\quad\sigma(a_{p})\smashoperator[]{\sum_{a_{-p}\in\mathcal{A}_{-p}}^{}}\sigma(a_{-p}|a^{\prime}_{p})G_{p}(a^{\prime}_{p},a_{-p})$
$\displaystyle\leq\sigma(a_{p})\smashoperator[]{\sum_{a_{-p}\in\mathcal{A}_{-p}}^{}}\sigma(a_{-p}|a_{p})G_{p}(a_{p},a_{-p})+\epsilon_{p}$
$\displaystyle\quad\sigma(a_{p})r^{\sigma}_{p}(a^{\prime}_{p})\leq\sigma(a_{p})r^{\sigma}_{p}(a_{p})+\epsilon_{p}$
(12)

Therefore a strategy, $a_{p}$, has an $\epsilon$-approximate better rating
than another, $a^{\prime}_{p}$, if there is negative incentive to deviate from
strategy $a_{p}$ to $a^{\prime}_{p}$ under the NE distribution (assuming
$\sigma(a_{p})>0$).

$\displaystyle r^{\sigma}_{p}(a^{\prime}_{p})$ $\displaystyle\leq
r^{\sigma}_{p}(a_{p})+\frac{\epsilon_{p}}{\sigma(a_{p})}$ (13)

The opposite equation also applies.

$\displaystyle\quad\smashoperator[]{\sum_{a_{-p}\in\mathcal{A}_{-p}}^{}}\sigma(a^{\prime}_{p})\sigma(a_{-p})G_{p}(a_{p},a_{-p})$
$\displaystyle\leq\smashoperator[]{\sum_{a_{-p}\in\mathcal{A}_{-p}}^{}}\sigma(a^{\prime}_{p})\sigma(a_{-p})G_{p}(a^{\prime}_{p},a_{-p})+\epsilon$
$\displaystyle\quad\sigma(a^{\prime}_{p})\smashoperator[]{\sum_{a_{-p}\in\mathcal{A}_{-p}}^{}}\sigma(a_{-p}|a_{p})G_{p}(a_{p},a_{-p})$
$\displaystyle\leq\sigma(a^{\prime}_{p})\smashoperator[]{\sum_{a_{-p}\in\mathcal{A}_{-p}}^{}}\sigma(a_{-p}|a^{\prime}_{p})G_{p}(a^{\prime}_{p},a_{-p})+\epsilon$
$\displaystyle\quad\sigma(a^{\prime}_{p})r^{\sigma}_{p}(a_{p})\leq\sigma(a^{\prime}_{p})r^{\sigma}_{p}(a^{\prime}_{p})+\epsilon_{p}$
(14)

And, if there is support $\sigma(a^{\prime}_{p})>0$.

$\displaystyle r^{\sigma}_{p}(a_{p})$ $\displaystyle\leq
r^{\sigma}_{p}(a^{\prime}_{p})+\frac{\epsilon_{p}}{\sigma(a^{\prime}_{p})}$
(15)

Therefore, if both $a_{p}$ and $a^{\prime}_{p}$ have support, then Equation
(13) and Equation (15) can be combined:

$\displaystyle
r^{\sigma}_{p}(a_{p})-\frac{\epsilon_{p}}{\sigma(a^{\prime}_{p})}$
$\displaystyle\leq r^{\sigma}_{p}(a^{\prime}_{p})\leq
r^{\sigma}_{p}(a_{p})+\frac{\epsilon_{p}}{\sigma(a_{p})}$
$\displaystyle-\frac{\epsilon_{p}}{\sigma(a^{\prime}_{p})}$ $\displaystyle\leq
r^{\sigma}_{p}(a^{\prime}_{p})-r^{\sigma}_{p}(a_{p})\leq\frac{\epsilon_{p}}{\sigma(a_{p})}$

Therefore we have bounds:

$\displaystyle\left|r^{\sigma}_{p}(a^{\prime}_{p})-r^{\sigma}_{p}(a_{p})\right|\leq\max\left[\frac{\epsilon_{p}}{\sigma(a_{p})},\frac{\epsilon_{p}}{\sigma(a^{\prime}_{p})}\right]$

Therefore we can see that when $\epsilon=0$, $\sigma(a_{p})>0$,
$\sigma(a^{\prime}_{p})>0$, the payoff ratings will be equal:
$r^{\sigma}_{p}(a_{p})=r^{\sigma}_{p}(a^{\prime}_{p})$. ∎

This result is unsurprising for those familiar with NE: if there is a benefit
to deviating strategies the opponents will adjust their distribution to
compensate.

Dominance. It is also possible to make arguments around strategy dominance and
their resulting payoff rating.

######  Theorem B.2 (NE Weak Dominance).

If strategy $a_{p}$ weakly dominates $a^{\prime}_{p}$;
$G_{p}(a_{p},a_{-p})\geq G_{p}(a^{\prime}_{p},a_{-p})~{}\forall
a_{-p}\in\mathcal{A}_{-p}$, then $r^{\sigma}_{p}(a_{p})\geq
r^{\sigma}_{p}(a^{\prime}_{p})$. $\epsilon$-NEs are weakly dominated up to a
constant $\frac{\epsilon_{p}}{\sigma(a_{p})}$.

###### Proof.

We can see from Equation (13) that this property immediately follows from the
definition of NE. ∎

It is also possible to prove that strategies that have zero support have
payoff rating no better than those with support.

######  Theorem B.3 (NE Zero Support Bound).

If strategy $a^{\prime}_{p}$ has zero support, it has a NE payoff rating no
greater than a strategy $a_{p}$ with support. This is true for $\epsilon$-NEs
up to a constant $\frac{\epsilon_{p}}{\sigma(a_{p})}$.

###### Proof.

By examining Equation (14), note that if $\sigma(a^{\prime}_{p})=0$, there are
no constraints that $r^{\sigma}_{p}(a^{\prime}_{p})$ is greater than any other
strategy’s payoff rating. ∎

Consistency. When using the maximum entropy (ME) as an equilibrium selection
criterion we can also obtain important consistency properties. Note that there
properties are not generally true, even for unique or convex selection
criteria.

######  Theorem B.4 (Repeated Strategies).

When using $\epsilon$-MENE, repeated strategies have equal payoff rating
(Balduzzi et al., 2018).

###### Proof.

Let us consider the situation when strategy $a_{p}$ is equal to
$a^{\prime}_{p}$, $G_{p}(a_{p},a_{-p})=G_{p}(a^{\prime}_{p},a_{-p})~{}\forall
a_{-p}$. It is therefore clearly true that:

$\displaystyle\smashoperator[]{\sum_{a_{-p}\in\mathcal{A}_{-p}}^{}}\sigma(a_{p},a_{-p})G_{p}(a^{\prime}_{p},a_{-p})$
$\displaystyle=\smashoperator[]{\sum_{a_{-p}\in\mathcal{A}_{-p}}^{}}\sigma(a_{p},a_{-p})G_{p}(a_{p},a_{-p})$
$\displaystyle\smashoperator[]{\sum_{a_{-p}\in\mathcal{A}_{-p}}^{}}\sigma(a^{\prime}_{p},a_{-p})G_{p}(a^{\prime}_{p},a_{-p})$
$\displaystyle=\smashoperator[]{\sum_{a_{-p}\in\mathcal{A}_{-p}}^{}}\sigma(a^{\prime}_{p},a_{-p})G_{p}(a_{p},a_{-p})$

Therefore, in the absence of an objective, and only considering these two
strategies, the joint distribution is indifferent to how it spreads its mass
over these two strategies (provided it is a feasible solution). However, under
the maximum entropy (ME) objective, entropy is maximum when
$\sigma(a_{p},a_{-p})=\sigma(a^{\prime}_{p},a_{-p})$, and hence
$\sigma(a_{p}|a_{-p})=\sigma(a^{\prime}_{p}|a_{-p})$. Therefore, when
strategies are repeated their payoff ratings are also equal,
$r^{\sigma}_{p}(a_{p})=r^{\sigma}_{p}(a^{\prime}_{p})$. This remains true for
all values of $\epsilon_{p}$. ∎

In games that are symmetric across all $n$ players such as the $7$-player
meta-game explored in (Anthony et al., 2020), we desire that the ratings of
the strategies with respect to each player is the same. If not, even with a
potentially unique equilibrium solution to the game, we could be left with at
least $2$ and possibly $n$ distinct rankings given by the marginals of each of
the players. Here, we prove maximum entropy selection criterion can avoid
this.

######  Theorem B.5 (Symmetric Games).

When using $\epsilon$-MENE, where all players share the same value
approximation parameter $\epsilon_{p}=\epsilon$, players in symmetric games
have equal sets of payoff rating,
$r^{\sigma}_{1}(a_{1})=...=r^{\sigma}_{n}(a_{n})$.

###### Proof.

When a game is symmetric the strategies available to each player are
identical, $\mathcal{A}_{1}=...=\mathcal{A}_{n}$, and the payoffs are
transposed $G_{1}(a_{1},a_{-1})=...=G_{n}(a_{n},a_{-n})$. Writing the previous
equality as $G_{p}(a_{p},a_{-p})=G_{q}(a_{q},a_{-q})$ $\forall p,q$, it is
therefore clearly true that:

$\displaystyle\smashoperator[]{\sum_{a_{-p}\in\mathcal{A}_{-p}}^{}}\sigma(a_{p},a_{-p})G_{p}(a_{p},a_{-p})$
$\displaystyle=\smashoperator[]{\sum_{a_{-p}\in\mathcal{A}_{-p}}^{}}\sigma(a_{p},a_{-p})G_{q}(a_{q},a_{-q})$
$\displaystyle\smashoperator[]{\sum_{a_{-p}\in\mathcal{A}_{-p}}^{}}\sigma(a_{q},a_{-q})G_{p}(a_{p},a_{-p})$
$\displaystyle=\smashoperator[]{\sum_{a_{-p}\in\mathcal{A}_{-p}}^{}}\sigma(a_{q},a_{-q})G_{q}(a_{q},a_{-q})$

Therefore, in the absence of an objective, and only considering these two
players, the joint distribution is indifferent to how it spreads its mass over
each player’s strategies (provided it is a feasible solution). However, under
the maximum entropy (ME) objective, entropy is maximum when
$\sigma(a_{p},a_{-p})=\sigma(a_{q},a_{-q})$, and hence
$\sigma(a_{p}|a_{-p})=\sigma(a^{\prime}_{q}|a_{-q})$. Therefore, when the game
is symmetric, each player’s strategies are payoff ratings are also equal,
$r^{\sigma}_{p}(a_{p})=r^{\sigma}_{q}(a_{q})$. ∎

###  B.2 CE

Dominance.

######  Theorem B.6 (Weak Dominance).

When using $0$-MECE, weakly dominated strategies result in weakly dominated
payoff ratings.

###### Proof.

Consider the $\epsilon$-CE, (Equation 1) expanded, assuming $\sigma(a_{p})>0$.

$\displaystyle\quad\sigma(a_{p})\smashoperator[]{\sum_{a_{-p}\in\mathcal{A}_{-p}}^{}}\sigma(a_{-p}|a_{p})G_{p}(a^{\prime}_{p},a_{-p})$
$\displaystyle\leq\sigma(a_{p})\smashoperator[]{\sum_{a_{-p}\in\mathcal{A}_{-p}}^{}}\sigma(a_{-p}|a_{p})G_{p}(a_{p},a_{-p})+\epsilon_{p}$
$\displaystyle\quad\sigma(a_{p})\smashoperator[]{\sum_{a_{-p}\in\mathcal{A}_{-p}}^{}}\sigma(a_{-p}|a_{p})G_{p}(a^{\prime}_{p},a_{-p})\leq\sigma(a_{p})r^{\sigma}_{p}(a_{p})+\epsilon_{p}$
$\displaystyle\quad\smashoperator[]{\sum_{a_{-p}\in\mathcal{A}_{-p}}^{}}\sigma(a_{-p}|a_{p})G_{p}(a^{\prime}_{p},a_{-p})\leq
r^{\sigma}_{p}(a_{p})+\frac{\epsilon_{p}}{\sigma(a_{p})}$ (16)

If $a^{\prime}_{p}$ also has support, $\sigma(a^{\prime}_{p})>0$, then the
opposite equation also applies.

$\displaystyle\sigma(a^{\prime}_{p})\smashoperator[]{\sum_{a_{-p}\in\mathcal{A}_{-p}}^{}}\sigma(a_{-p}|a^{\prime}_{p})$
$\displaystyle G_{p}(a_{p},a_{-p})$
$\displaystyle\leq\sigma(a^{\prime}_{p})\smashoperator[]{\sum_{a_{-p}\in\mathcal{A}_{-p}}^{}}\sigma(a_{-p}|a^{\prime}_{p})$
$\displaystyle G_{p}(a^{\prime}_{p},a_{-p})+\epsilon_{p}$
$\displaystyle\sigma(a^{\prime}_{p})\smashoperator[]{\sum_{a_{-p}\in\mathcal{A}_{-p}}^{}}\sigma(a_{-p}|a^{\prime}_{p})G_{p}(a_{p},a_{-p})$
$\displaystyle\leq\sigma(a^{\prime}_{p})r^{\sigma}_{p}(a^{\prime}_{p})+\epsilon_{p}$
$\displaystyle\smashoperator[]{\sum_{a_{-p}\in\mathcal{A}_{-p}}^{}}\sigma(a_{-p}|a^{\prime}_{p})G_{p}(a_{p},a_{-p})$
$\displaystyle\leq
r^{\sigma}_{p}(a^{\prime}_{p})+\frac{\epsilon_{p}}{\sigma(a^{\prime}_{p})}$
(17)

Let us consider the situation when strategy $a_{p}$ weakly dominates
$a^{\prime}_{p}$, $G_{p}(a_{p},a_{-p})\geq
G_{p}(a^{\prime}_{p},a_{-p})~{}\forall a_{-p}$. If we add this as a lower
bound into Equation (17) we obtain this bound:

$\displaystyle
r^{\sigma}_{p}(a^{\prime}_{p})\leq\smashoperator[]{\sum_{a_{-p}\in\mathcal{A}_{-p}}^{}}\sigma(a_{-p}|a^{\prime}_{p})G_{p}(a_{p},a_{-p})$
$\displaystyle\leq
r^{\sigma}_{p}(a^{\prime}_{p})+\frac{\epsilon_{p}}{\sigma(a^{\prime}_{p})}$
(18)

By consider the limit when $\lim_{\epsilon_{p}\to 0}\eqref{eq:ce_squeeze}$, we
can squeeze the bound of payoff rating to an equality:

$\displaystyle\lim_{\epsilon_{p}\to 0}r^{\sigma}_{p}(a^{\prime}_{p})$
$\displaystyle=\sum_{a_{-p}\in\mathcal{A}_{-p}}\sigma(a_{-p}|a^{\prime}_{p})G_{p}(a_{p},a_{-p})$
(19)
$\displaystyle=\underbrace{\sum_{a_{-p}\in\mathcal{A}_{-p}}\sigma(a_{-p}|a^{\prime}_{p})G_{p}(a^{\prime}_{p},a_{-p})}_{r^{\sigma}_{p}(a^{\prime}_{p})}$

Therefore the marginals can only both be positive, $\sigma(a_{p})>0$ and
$\sigma(a^{\prime}_{p})>0$, if
$G_{p}(a_{p},a_{-p})=G_{p}(a^{\prime}_{p},a_{-p})$ for all $a_{-p}$ where
$\sigma(a_{-p}|a^{\prime}_{p})>0$101010Note that this immediately leads to a
contradiction if we had assumed strictly dominated strategies above because
$G_{p}(a_{p},a_{-p})>G_{p}(a^{\prime}_{p},a_{-p})$. Therefore when strategy
$a_{p}$ strictly dominates $a^{\prime}_{p}$, $\sigma(a^{\prime}_{p})=0$. It is
well understood that strictly dominated strategies receive no mass in CEs.,
when strategy $a_{p}$ weakly dominates $a^{\prime}_{p}$.

Let us assume that $r^{\sigma}_{p}(a_{p})<r^{\sigma}_{p}(a^{\prime}_{p})$, and
utilizing Equation (19).

$\displaystyle\smashoperator[]{\sum_{a_{-p}\in\mathcal{A}_{-p}}^{}}\sigma(a_{-p}|a_{p})G_{p}(a^{\prime}_{p},a_{-p})<\smashoperator[]{\sum_{a_{-p}\in\mathcal{A}_{-p}}^{}}\sigma(a_{-p}|a^{\prime}_{p})G_{p}(a^{\prime}_{p},a_{-p})$

This can only be true if, where mass is positive, does
$G_{p}(a_{p},a_{-p})=G_{p}(a^{\prime}_{p},a_{-p})$ and $\sigma(a_{-p}|a_{p})$
opts to put mass onto a lower valued elements compared to
$\sigma(a_{-p}|a^{\prime}_{p})$. This is possible under an arbitrary
equilibrium selection objectives. Consider when we use a maximum entropy CE,
however. In this scenario, if we are indifferent between $a_{p}$ and
$a^{\prime}_{p}$, the entropy maximizing term will spread mass equally over
$a_{p}$ and $a^{\prime}_{p}$. This will result in an equality between payoff
ratings, and is therefore a contradiction.

Therefore in $0$-MECEs, if strategy $a_{p}$ weakly dominates $a^{\prime}_{p}$,
the ratings are $r^{\sigma}_{p}(a_{p})=r^{\sigma}_{p}(a^{\prime}_{p})$, when
the strategies in fact have equal payoff, or $r^{\sigma}_{p}(a^{\prime}_{p})$
is undefined because $\sigma(a^{\prime}_{p})=0$. Because we define an
undefined rating to be worse than all defined ratings, weak dominance holds
for payoff ratings too $r^{\sigma}_{p}(a_{p})\geq
r^{\sigma}_{p}(a^{\prime}_{p})$. ∎

Consistency. We can obtain similar consistency proofs for CEs that follow the
same proofs are their NE counterparts.

######  Theorem B.7 (Repeated Strategies).

When using $\epsilon$-MECE, repeated strategies have equal payoff rating.

###### Proof.

See Theorem B.4. ∎

######  Theorem B.8 (Symmetric Games).

When using $\epsilon$-MECE, where all players share the same value
approximation parameter $\epsilon_{p}=\epsilon$, players in symmetric games
have equal sets of payoff rating,
$r^{\sigma}_{1}(a_{1})=...=r^{\sigma}_{n}(a_{n})$.

###### Proof.

See Theorem B.5. ∎

###  B.3 CCE

Consistency. We can obtain similar consistency proofs for CCEs, their proofs
are the the same for the NE case.

######  Theorem B.9 (Repeated Strategies).

When using $\epsilon$-MECCE, repeated strategies have equal payoff rating.

###### Proof.

See Theorem B.4. ∎

######  Theorem B.10 (Symmetric Games).

When using $\epsilon$-MECCE, where all players share the same value
approximation parameter $\epsilon_{p}=\epsilon$, players in symmetric games
have equal sets of payoff rating,
$r^{\sigma}_{1}(a_{1})=...=r^{\sigma}_{n}(a_{n})$.

###### Proof.

See Theorem B.5. ∎

##  Appendix C Implementation Considerations

There are two additional considerations that may need to be handled when
implementing game theoretic ratings algorithms: uncertain payoffs and repeated
strategies.

###  C.1 Uncertainty in Payoffs

Often the outcome of a game is stochastic and we may not be able to query the
exact expected return of a joint strategy. Instead, we may have to estimate
the expected return through sampling each element of the payoff. Furthermore,
there may be scenarios where elements of a payoff tensor are missing. There
has been significant work on estimating solution concepts in uncertain or
incomplete information settings (Rowland et al., 2019; Du et al., 2021; Rashid
et al., 2021). The work we present here does not offer involved solutions for
handling uncertain payoffs, but we will make one recommendation: when the
payoff is uncertain an appropriately large $\epsilon$ should be used. This is
because small changes in payoff can result in large changes in the equilibrium
set. Larger $\epsilon$ mitigates the size of those changes.

###  C.2 Repeated Strategy Problem

Table 2: Dwayne, Pen, Sword, Rock, Paper, Scissors (DPSRPS) symmetric, two-player, zero-sum game. Where Dyawne beats pen (dominance in arts), pen beats sword, sword beats Dwayne. When the first three strategies interact with the second three strategies they retain the usual properties of the RPS game resulting in those three quadrants having identical payoff. Note that the top left quadrant has a reversed cycle to the usual RPS game. We also define the sub-games DRPS, and RSP. | D | Pe | Sw | R | P | S
---|---|---|---|---|---|---
D |  $\frac{1}{2}$, $\frac{1}{2}$ |  $1$, $0$ |  $0$, $1$ |  $\frac{1}{2}$, $\frac{1}{2}$ |  $0$, $1$ |  $1$, $0$
Pe |  $0$, $1$ |  $\frac{1}{2}$, $\frac{1}{2}$ |  $1$, $0$ |  $1$, $0$ |  $\frac{1}{2}$, $\frac{1}{2}$ |  $0$, $1$
Sw |  $1$, $0$ |  $0$, $1$ |  $\frac{1}{2}$, $\frac{1}{2}$ |  $0$, $1$ |  $1$, $0$ |  $\frac{1}{2}$, $\frac{1}{2}$
R |  $\frac{1}{2}$, $\frac{1}{2}$ |  $0$, $1$ |  $1$, $0$ |  $\frac{1}{2}$, $\frac{1}{2}$ |  $0$, $1$ |  $1$, $0$
P |  $1$, $0$ |  $\frac{1}{2}$, $\frac{1}{2}$ |  $0$, $1$ |  $1$, $0$ |  $\frac{1}{2}$, $\frac{1}{2}$ |  $0$, $1$
S |  $0$, $1$ |  $1$, $0$ |  $\frac{1}{2}$, $\frac{1}{2}$ |  $0$, $1$ |  $1$, $0$ |  $\frac{1}{2}$, $\frac{1}{2}$

Consider the Rock, Paper, Scissors (RPS) game (Table 2). For RPS, each
strategy is clearly distinct as they have different payoffs. Now let us
consider a similar game Dwayne, Rock, Paper, Scissors (DRPS). In this case
strategies $D$ and $R$ have identical payoffs, but does that mean they are
repeated instances of the same strategy?

Strategies with the same payoffs are mathematically identical. The only
situation where one may want to differentiate between strategies with
identical payoffs is when one is in a sub-game regime: where we only know a
subset of the strategies of a full game. This scenario is common in EGTA, and
this problem arises in multiagent training algorithms like Double Oracle (DO)
(McMahan et al., 2003) and Policy-Space Response Oracles (PSRO) (Lanctot et
al., 2017). In this scenario strategies may become non-identical when
additional opponent strategies are added to the sub-game. For example,
consider the Dwayne, Pen, Sword, Rock, Paper, Scissors (DPWRPS) game (Table
2).

However, there is still additional information that can be attached to each
strategy to aid differentiation. For example it is common that strategies
represent policies from an extensive form game. In this case one could
differentiate strategies with the same payoffs in a sub-game by examining
their policies. Identical policies imply identical payoffs, but identical
payoffs do not imply identical policies.

A desirable property of rating algorithms is that they are invariant under
strategy repeats. An algorithm with this property is particularly useful when
rating sub-games where distinctly different strategies may appear to have the
same payoffs in the sub-game. For example, if you were studying a RPS
tournament and found that $50$% of participants played rock, you may come away
thinking that paper is the strongest strategy. However, while this may be the
case in this particular tournament, it does not paint an accurate portrayal of
the underlying RPS game, where each strategy is equally good and equally
exploitable. Payoff ratings derived from NEs are invariant to strategy repeats
(Balduzzi et al., 2018). (C)CEs and $\alpha$-Rank are not automatically
invariant to strategy repeats. Retaining this property for these other
solution concepts is advantageous.

This could be simply achieved by eliminating repeated strategies from a game.
When the payoffs are exactly known, this can be implemented by testing for
equality between all elements of a slice of a payoff tensor and eliminating
duplicate slices. When the payoffs are noisy estimates, we may need to use
_soft strategy elimination_ (Section D). After solving the remaining sub-game
after elimination, we can reconstruct a joint distribution for the
uneliminated game by spreading any mass equally over repeated strategies.

##  Appendix D Soft Strategy Elimination

When using approximate payoff tensors we may wish to use soft strategy
elimination to remove unwanted strategy repeats in the payoff tensor. This is
achieved with a similarity matrix.

###  D.1 Similarity Matrix

A square similarity matrix, $S_{p}(a_{p},a^{\prime}_{p})$, for each player
$p$, can be constructed from a similarity function between pairs of
strategies, $(a_{p},a^{\prime}_{p})$. A value of $1$ indicates the strategies
are equal, a value of $0$ means they are not equal. This function could depend
on the payoff estimates, $G_{p}$, and variance estimates, $V_{p}$.

$\displaystyle S_{p}(a_{p},a^{\prime}_{p})=\sum_{a_{-p}}f\bigl{(}$
$\displaystyle G(a_{p},a_{-p}),G(a_{p},a_{-p}),$ $\displaystyle
V(a_{p},a_{-p}),V(a_{p},a_{-p})\bigr{)}$ (20)

The main diagonal of the matrix is populated with ones. Some similarity
measures may result in a symmetric matrix, however this is not a requirement.

Similarity functions can be constructed in a number of ways, for example using
a norm or a divergence with an appropriate squashing function, or perhaps a
probabilistic approach such as the Hellinger distance. We consider the choice
of similarity metric a heuristic and don’t provide a theoretical solution
here. Good choices will depend on the specific application, we give some
example approaches in the examples section.

Typically the similarity matrix will be used by summing over the other
strategies resulting in a vector that captures how many times an strategy is
repeated.

$\displaystyle
s_{p}(a_{p})=\smashoperator[]{\sum_{a^{\prime}_{p}\in\mathcal{A}_{p}}^{}}S_{p}(a_{p},a^{\prime}_{p})$
(21)

###  D.2 Objective Function Modification

We then take the outer product of these counts to find a quantity of the same
dimensionality as $\sigma$.

$\displaystyle s(a)=s(a_{1},...,a_{n})=\otimes_{p}s_{p}(a_{p})$ (22)

This can then be incorporated into MG(C)CE by substituting
$\sum_{a}\sigma(a)^{2}$ with $\sum_{a}\frac{1}{s(a)}\sigma(a)^{2}$ or into
ME(C)CE substituting $\sum_{a}\sigma(a)\ln(\sigma(a))$ with
$\sum_{a}\frac{1}{s(a)}\sigma(a)\ln(\sigma(a))$.

Table 3: Summary of parameterizations of algorithms available under this general scheme. Of course many other combinations are possible. Rating | Joint | Selection | Approximation | Algorithm
---|---|---|---|---
PR | NE | ME | $\epsilon=0$ | Nash Average (Balduzzi et al., 2018)
MR |  $\alpha$-Rank | N/A | $\alpha$ |  $\alpha$-Rank (Omidshafiei et al., 2019)
PR | CCE | ME | $\epsilon=\epsilon^{\min+}$ |  $\epsilon^{\min+}$-MECCE
PR | CCE | ME | $\epsilon^{\min+}\leq\epsilon\leq\epsilon^{\text{uni}}$ |  $\frac{\epsilon}{\epsilon^{\text{uni}}}$-MECCE
PR | CE | ME | $\epsilon=\epsilon^{\min+}$ |  $\epsilon^{\min+}$-MECE
PR | CE | ME | $\epsilon^{\min}\epsilon\leq\epsilon\leq\epsilon^{\text{uni}}$ |  $\frac{\epsilon}{\epsilon^{\text{uni}}}$-MECE
PR | NE | LLE | $\lambda=\infty$ |  $\infty$-LLE
PR | NE | LLE | $\lambda$ |  $\lambda$-LLE

##  Appendix E Algorithms

Table 3 summarises parameterizations of prior art algorithms and the new
parameterizations suggested in this paper. $\alpha$-Rank uses the marginals of
the joint distribution to rate strategies, a technique we refer to as _mass
rating_ (MR).

##  Appendix F Experiments

This section provides additional experiments on standard and real data.

###  F.1 Standard Normal Form Games

In Section 5 we show the MECCE payoff ratings for several normal form games.
We omit ratings for the MECE because for games with only two strategies, the
$\epsilon$-MECE and $\epsilon$-MECCE joint distributions are equivalent.

######  Theorem F.1.

For N-player normal form games where each player has exactly two strategies,
$\epsilon$-CE and $\epsilon$-CCE are equivalent.

###### Proof.

Consider the CCE deviation gains for player $p$:

$\displaystyle A^{\text{CCE}}_{p}(a^{\prime}_{p},a)$
$\displaystyle=\smashoperator[]{\sum_{a\in\mathcal{A}}^{}}\left(G_{p}(a^{\prime}_{p},a_{-p})-G_{p}(a_{p},a_{-p})\right)$
$\displaystyle=|\mathcal{A}_{p}|\smashoperator[]{\sum_{a_{-p}\in\mathcal{A}_{-p}}^{}}G_{p}(a^{\prime}_{p},a_{-p})-\smashoperator[]{\sum_{a\in\mathcal{A}}^{}}G_{p}(a_{p},a_{-p})$

When there are two strategies, $a^{1}_{p}$ and $a^{2}_{p}$:

$\displaystyle A^{\text{CCE}}_{p}(a^{1}_{p},a)$
$\displaystyle=2\smashoperator[]{\sum_{a_{-p}\in\mathcal{A}_{-p}}^{}}G_{p}(a^{1}_{p},a_{-p})-\smashoperator[]{\sum_{\begin{subarray}{c}a_{p}\in\mathcal{A}_{p}\\\
a_{-p}\in\mathcal{A}_{-p}\end{subarray}}^{}}G_{p}(a_{p},a_{-p})$
$\displaystyle=\smashoperator[]{\sum_{a_{-p}\in\mathcal{A}_{-p}}^{}}G_{p}(a^{1}_{p},a_{-p})-\smashoperator[]{\sum_{a_{-p}\in\mathcal{A}_{-p}}^{}}G_{p}(a^{2}_{p},a_{-p})$
$\displaystyle=A^{\text{CE}}_{p}(a^{1}_{p},a^{2}_{p},a_{-p})$

The feasible space is fully determined by the constraints, thus concludes the
proof. ∎

###  F.2 Constant-Sum Two-Player Premier League Ratings

Consider the zero-sum win probability game (Figure 1). We can study how these
ratings change when we vary the normalised approximation parameter,
$\frac{\epsilon}{\epsilon^{\text{uni}}}$, for
$\frac{\epsilon}{\epsilon^{\text{uni}}}$-MECCE (Figure 7). When using
$\frac{\epsilon}{\epsilon^{\text{uni}}}=1$ the uniform distribution is
selected, and the payoff ratings are simply the mean performances against
other clubs. When $\frac{\epsilon}{\epsilon^{\text{uni}}}$ is reduced towards
zero, the rating becomes more game theoretic and the ratings change to reflect
this. In particular, Leicester, Crystal Palace, and Newcastle all climb in
rankings because they are in a weak cycle with Man City. Furthermore, the
marginal masses, $\sigma(a_{p})$, of many of the strategies tend to zero, with
only a handful of clubs maintaining positive mass.

###  F.3 General-Sum Two-Player Premier League Ratings

The general-sum points (each club plays each other twice and score $3$ points
for each win, $1$ for each draw and $0$ for each loss) game (Figure 5). This
game is considered because it is not purely competitive: coordination exists
because players would prefer mixing over two win-loss joint strategies ($1.5$
points each) rather than a single draw-draw joint strategy ($1$ point each).

We consider a particular NE equilibrium, the limiting logit equilibrium (LLE),
which has which has a factorizable joint distribution (Figure 5(d)). A key
drawback of factorizable distributions is that they cannot coordinate with
other players, and therefore miss out on opportunities to the value of the
game. We can see that LLE has the lowest value of the solutions concepts we
tested (Figure 5(l)), even lower than uniform, while CCE has the highest, as
the theory predicts. Therefore CCEs have the property that they can handle
both competitive and cooperative rating.

(a) $\alpha$-Rank $\sigma(a_{1},a_{2})$

(b) $0.01$-MECCE $\sigma(a_{1},a_{2})$

(c) $0.01$-MECE $\sigma(a_{1},a_{2})$

(d) LLE $\sigma(a_{1},a_{2})$

(e) $\alpha$-Rank $\sigma(a_{2}|a_{1})$

(f) $0.01$-MECCE $\sigma(a_{2}|a_{1})$

(g) $0.01$-MECE $\sigma(a_{2}|a_{1})$

(h) LLE $\sigma(a_{2}|a_{1})$

(i) P1 payoff, $G_{1}(a_{1},a_{2})$

(j) P2 payoff, $G_{1}(a_{1},a_{2})$

(k) Ratings, $r_{1}^{\sigma}(a_{1})$

(l) Values, $\sum_{a\in\mathcal{A}}G_{1}(a)\sigma(a)$

Figure 5: Symmetric, two-player, general-sum Premier League game where players
pick between clubs as strategies. The clubs are ordered according to their
average points (3 points for a win, 1 for a draw, 0 for a loss). The payoff
ratings have been scaled by a factor of $\frac{1}{6}$. The joint and
conditional distributions for the different ratings are shown for comparison.

(a) Payoff, $G(a_{1},a_{2},a_{3})$

(b) $\alpha$-Rank

(c) MECCE

(d) MECE

(e) Ratings

Figure 6: Three-player tennis games where the surface player chooses the court
surface the game is played on. Grass has the closest games so is favoured most
by the surface player. The distributions of all three solution concepts are
shown.

###  F.4 Three-Player ATP Tennis Ratings

Using data from 2000-2020 ATP Tennis tournaments we studied the ratings of
three competitors (Djokovic, Federer and Nadal) and the surfaces they play on
(Hard, Clay and Grass), resulting in a three-player game: surface vs
competitor vs competitor.

The surface a player competes on is a large factor of the game, however Elo,
the traditional method of rating players, ignores this dependency. Out of the
144 games between these competitors in the dataset we observed, 84 were on
hard, 48 were on clay and, 12 were on grass surfaces. A transitive rating
system, like Elo, is susceptible to this distribution and therefore favours
players who have a strong hard surface game.

We studied an imagined game (Figure 6(a)) where the surface player gets the
“win” if the match goes to tiebreak, shares half a point with the winning
player if there is a single set difference between the winning and losing
competitor, otherwise the winning competitor gets the win. Pairing between
competitors and themselves are given zero points. Intuitively, if the match is
sufficiently close, the surface “wins” because it is too difficult for the
competitors to break.

The grass surface results in the closest matches and therefore provides the
most points to the surface player, and therefore receives the majority of the
distribution mass. This means that the players are mainly evaluated according
to their performance on grass, of which Djokovic is the strongest (Figure
6(e)).

(a) Mass ratings when varying $\frac{\epsilon}{\epsilon^{\text{uni}}}$.

(b) Payoff ratings when varying $\frac{\epsilon}{\epsilon^{\text{uni}}}$.

Figure 7: Shows how $\frac{\epsilon}{\epsilon^{\text{uni}}}$-MECCE mass
(marginals of the joint) and payoff rating varies over normalized $\epsilon$
for two-player, zero-sum Premier League ratings. When
$\frac{\epsilon}{\epsilon^{\text{uni}}}=0^{+}$, $0^{+}$-MECCE payoff rating is
recovered, when $\frac{\epsilon}{\epsilon^{\text{uni}}}=1$, uniform payoff
rating is recovered. Because this game is two-player, zero-sum, the $0$-MECCE
is equal to $0$-MENE, which is the definition of Nash Average. Lower values of
$\frac{\epsilon}{\epsilon^{\text{uni}}}$ result in greater attention to cycles
in the payoff table. Some clubs see their rankings improved as
$\frac{\epsilon}{\epsilon^{\text{uni}}}$ is reduced; in particular Leicester,
Crystal Palace and Newcastle which draw with Man City.