bounds as in Definitions \[def:under:covering\] and \[def:stick:covering\]. Equations (\[eq:approx:E\]) state that $(1+\varepsilon_1)^{-1}{\mathcal{E}}$ bounds below $E$ which bounds below ${\mathcal{E}}$. Equations (\[eq:approx:F\]) state that ${\mathcal{F}}$ bounds below $F$ which bounds below $(1+\varepsilon_2){\mathcal{F}}$. Crucially, whatever the sizes of ${\mathcal{E}}$ and ${\mathcal{F}}$, there exist such approximations $E$ and $F$ with respective sizes $O((1/\varepsilon_1)^{d-1})$ and $O((1/\varepsilon_2)^{d-1})$ [@papadimitriou2000approximability], yielding the approximation scheme below.

\[th:approx\] Given a compact MOG of representation length $L$, precisions $\varepsilon_1,\varepsilon_2>0$ and two algorithms to compute approximations $E$ of ${\mathcal{E}}$ and $F$ of ${\mathcal{F}}$ in the sense of Equations (\[eq:approx:E\]) and (\[eq:approx:F\]) that take time $\theta_{{\mathcal{E}}}(\varepsilon_1,L)$ and $\theta_{{\mathcal{F}}}(\varepsilon_2,L)$, one can approximate $R[{\mathcal{E}},{\mathcal{F}}]$ in the sense of Equation (\[eq:approx:R\]) in time $O\left(\theta_{{\mathcal{E}}}(\varepsilon_1,L) \quad+\quad \theta_{{\mathcal{F}}}(\varepsilon_2,L) \quad+\quad {(\varepsilon_1 \varepsilon_2)^{-(d-1)(2d-1)}}\right)$.

For MO graphical games, Phase 1 could be instantiated with approximate junction-tree algorithms on MO graphical models [@dubus2009multiobjective]. For MO symmetric action-graph games, in the same fashion, one could generalize existing algorithms [@jiang2007computing]. More generally, for the worst equilibria ${\mbox{WST}}[{\mathcal{E}}]$ and the efficient outcomes ${\mathcal{F}}$, one could also use meta-heuristics with experimental guarantees.

Conclusion: discussion and prospects
====================================

Along with equilibrium existence, potential functions also usually guarantee the convergence of best-response dynamics. This easily generalizes to dynamics where every deviation step is an individual Pareto-improvement. However, 