the multi-objective case. However, the underlying proofs do not survive this generalization: while best response inequalities can be summed in single-objective cases, here, non-Pareto-dominances cannot. This issue is independent of the chosen efficiency measurement and motivates numerical approaches, as proposed in the next section.

Computation
===========

In this section, we provide algorithms for computing the set of pure-strategy Pareto-Nash equilibria and for computing the multi-objective coordination ratio.

Computing pure-strategy Pareto-Nash equilibria
----------------------------------------------

If the MO game is given in *normal form*, then it is made of the MO payoffs of every agent $i\in N$ on every action-profile $\bm{a}\in A$. Since there are $n\alpha^{n}$ such vectors, where recall that $n$ is the number of agents, $\alpha$ the number of actions per agent and $d$ the number of objectives, the length of this input is $L(n)=n\alpha^{n}d$. Then, enumeration of the action-profiles works efficiently with respect to length function $L$, using a simple argument similar to [@gottlob2005pure].

Given a MO game in normal form, computing the set of the best (resp. worst) equilibria outcomes ${\mbox{EFF}}[{\mathcal{E}}]$ (resp. ${\mbox{WST}}[{\mathcal{E}}]$) takes polynomial time $$O(n\alpha^{n+1}d+\alpha^{2n}d)\quad=\quad O(L^{2}).$$ Moreover, if $d=2$, this complexity is lowered to quasi-linear-time $$O(n\alpha^{n}\log_{2}(\alpha))=O(L\log_{2}(\alpha)).$$

provide compact representations of massive multi-agent games when the payoff functions 