---
abstract: 'In a multi-objective game, each individual’s payoff is a *vector-valued* function of everyone’s actions. Under such vectorial payoffs, Pareto-efficiency is used to formulate each individual’s best-response condition, inducing Pareto-Nash equilibria as the fundamental solution concept. In this work, we follow a classical game-theoretic agenda to study equilibria. Firstly, we show in several ways that numerous pure-strategy Pareto-Nash equilibria exist. Secondly, we propose a more consistent extension to mixed-strategy equilibria. Thirdly, we introduce a measurement of the efficiency of multiple objectives games, which purpose is to keep the information on each objective: the multi-objective coordination ratio. Finally, we provide algorithms that compute Pareto-Nash equilibria and that compute or approximate the multi-objective coordination ratio.'
author:
- Anisse Ismaili
bibliography:
- 'newMOG.bib'
title: 'On Existence, Mixtures, Computation and Efficiency in Multi-objective Games'
---

Introduction
============

Game theory and microeconomics assume that individuals evaluate outcomes into scalars. However, bounded rationality can hardly be modeled consistently by agents simply comparing scalars: *“The classical theory does not tolerate the incomparability of oranges and apples.”* [@simon1955behavioral]. Money is another case of scalarization of the values of outcomes. For instance, while ‘making money’ theoretically creates value [@adam1776inquiry], the tobacco industry making money and killing approximately six million people every year [@world2011report] is hardly a creation of value[^1]. In this work, we assume that agents evaluate outcomes over a finite set of distinct objectives[^2]; hence, agents have vectorial payoffs. For instance, in the case of tobacco consumers, this slightly more informative model would keep the information on these three objectives [@conover2014smoking]: smoking pleasure, cigarette cost and consequences on life expectancy. In literature, this model was called games with vectorial payoffs, multi-objective games or multi-criteria games; and several applications were considered (see e.g. [@zeleny1975games; @wierzbicki1995multiple]). Indeed, behaviors are less assumptively modeled by a partial preference: the Pareto-dominance. Using Pareto-efficiency in place of best-response condition induces Pareto-Nash (PN) equilibria as the solution concept for stability, without even assuming that individuals combine the objectives in a precise manner. Pareto-Nash equilibria encompass the outcomes, even under unknown, uncertain or inconsistent preferences.

This paper more particularly addresses two unexplored issues.(1) The algorithmic aspects of multi-objective games have never been studied. (2) Also, the efficiency of Pareto-Nash equilibria has never been a concern.

*Related literature on mixed-strategies and similar strategy spaces.* Games with vectorial payoffs, or multi-objective games, were firstly introduced in the late fifties by Blackwell and Shapley [@blackwell1956analog; @shapley1959equilibrium]. The former shows the existence of a mixed-strategy Pareto-Nash equilibrium in finite two-player zero-sum multi-objective games. The later generalizes this existence result to finite multi-objective games. Both use a definition of mixed-strategy Pareto-Nash equilibria that suffers an inconsistency: pure-strategy Pareto-Nash equilibria are not included in the set of mixed-strategy Nash equilibria (see Sec. \[sec:mixed\]). Nonetheless, there is an established literature on games with vector payoffs that uses this definition. Deep formal works generalized known existence results [@shapley1959equilibrium] to individual action-sets being compact convex subsets of a normed space [@wang1993existence]. Weak Pareto-Nash equilibria can be approximated [@morgan2005approximations]. *Works related to pure strategies and algorithms.* [@wierzbicki1995multiple] achieves to characterize the entire set of Pareto-Nash equilibria by mean of augmented Tchebycheff norms. However, the number of dimensions that parameterize these Tchebycheff norms is algorithmically prohibitive. [@patrone2007multicriteria] shows that a MO potential function guarantees that a Pareto-Nash equilibrium exists in finite MO games.

In Section 3, we show in three different settings that pure-strategy Pareto-Nash equilibria are guaranteed to exist, or very likely to be numerous. In Section 4, we show an inconsistency in the current concept of mixed-strategy PN equilibrium, and propose an extension to solve this flaw. In Section 5, in the fashion of the price of anarchy [@koutsoupias1999worst], we define a measurement of the worst-case efficiency of individualistic behaviors in games, compared to the optimum. In the multi-objective case, it is far from trivial, as worst-case equilibria and optima are not uniquely defined. In Section 6, we show how to compute the set of (worst) pure-strategy Pareto-Nash equilibria for several game structures, and provide algorithms to compute and approximate our multi-objective coordination ratio.[^3]

Preliminaries
=============

A *multi-objective game* (MO game, or MOG) is defined by the following tuple $\left(N,\{A^{i}\}_{i\in N},{{\mathcal{D}}},\{\bm{u}^{i}\}_{i\in N}\right)$:

-   The agents set is $N=\lbrace1,\ldots,n\rbrace$. Agent $i$ decides action $a^{i}$ in action-set $A^{i}$.

-   The shared list of objectives is denoted by ${{\mathcal{D}}}=\lbrace1,\ldots,d\rbrace$ and every agent $i\in N$ gets her payoff from function $\bm{u}^{i}:A=A^{1}\times\ldots\times A^{n}\rightarrow\mathbb{R}^{d}$ which maps every overall action to a *vector-valued* payoff; e.g., real $u_{k}^{i}(\bm{a})$ is the payoff of agent $i$ on objective $k$ for action-profile $\bm{a}=(a^{1},\ldots,a^{n})$.

![image](Figure1)

There are five shops (the nodes) in Ocean Shores: $N=\{1,\ldots,5\}$. Each shop/agent $i$ decides between two activities: $A^{i}=\{a^{i},b^{i}\}$; for instance: renting bikes or buggies, selling clams or fruit, etc. That is, agent $i$, in his payoff table $u^i$, decides row $a^{i}$ or $b^{i}$. The edges define neighborhoods around every agent. The payoff of each agent also depends on the actions of her neighbors, and is differentiated on two objectives ${{\mathcal{D}}}=\{1,2\}$ that it would hardly make sence to aggregate, for instance: sales revenue (to buy their daily lives) and the remaining natural resources (so that, in the future, their children could also live). (Here, the payoffs are random integers.)

In the subjective theory of value, every individual evaluates her endowment $(u_{1}^{i},\ldots,u_{d}^{i})$ however she wants based on an utility function $v^{i}:{\mathbb{R}^d}\rightarrow{\mathbb{R}}$. The theory of multi-objective games [@blackwell1956analog; @shapley1959equilibrium] aims at allowing for individuals that behave according to several unknown, uncertain, or inconsistent utility functions. These utility functions are reduced to their common denominator: the Pareto-dominance, as defined below. That vector $\bm{y}\in{\mathbb{R}^d}$ weakly-Pareto-dominates and respectively *Pareto-dominates* vector $\bm{x}\in{\mathbb{R}^d}$ is denoted and defined by: $$\begin{aligned}
\bm{y}{\succsim}\bm{x} & \Leftrightarrow & \forall k\in{{\mathcal{D}}},\quad  y_k\geq x_k,\\ 
\bm{y}{\succ}\bm{x} &\Leftrightarrow & \forall k\in{{\mathcal{D}}},\quad y_k\geq x_k\mbox{~~and~~}\exists k\in{{\mathcal{D}}}, y_k> x_k.\end{aligned}$$ For the preferences of individuals, given an adversary action-profile$\bm{a}^{-i}=(a^j\mid j\neq i)$, this defines a partial rationality on set$\bm{u}^{i}(A^{i},\bm{a}^{-i})=\{\bm{u}^{i}(b^{i},\bm{a}^{-i})\mid b^i\in A^i\}$, which is less assumptive than complete orders, since it does not presume any individual utility function $v^{i}:{\mathbb{R}}^{d}\rightarrow{\mathbb{R}}$. Formally, given a finite set of vectors $X\subseteq{\mathbb{R}^d}$, the set of *Pareto-efficient* vectors is defined as the following set of non-Pareto-dominated vectors: $${\mbox{EFF}}[X]=\{\bm{y}\in X~~|~~\forall \bm{x}\in X,\mbox{~not~}(\bm{x}{\succ}\bm{y})\}.$$ Since Pareto-dominance is a partial order, it induces a multiplicity of Pareto-efficient vectors. These are the best compromises between objectives. Similarly, let ${\mbox{WST}}[X]=\{\bm{y} \in X|\forall \bm{x}\in X,\mbox{not}(\bm{y}{\succ}\bm{x})\}$ denote the worst vectors.

In a multi-objective game, individuals behave according to the Pareto -dominance, inducing the solution concept *Pareto-Nash equilibrium* (${\mbox{PN}}$), formally defined as any action-profile $\bm{a}\in A$ such that for every agent $i\in N$: $$\bm{u}^{i}(a^{i},\bm{a}^{-i})\quad\in\quad{\mbox{EFF}}\left[\quad \{\bm{u}^{i}(b^{i},\bm{a}^{-i})\mid b^{i}\in A^{i}\}\quad\right].$$ We call these conditions *Pareto-efficient responses*. Let ${\mbox{PN}}\subseteq A$ denote the set of Pareto-Nash equilibria. For instance, in Figure 1, action-profile $(b^{1},b^{2},a^{3},b^{4},b^{5})$ is a PN equilibrium, since each action, given the adversary local action profile (column), is Pareto-efficient among the given agent’s two actions (rows). In this example, there are $13$ Pareto-Nash equilibria (depicted in Figure 2).

Such an encompassing solution concept provides the first phase for bounding the efficiency of games. It is well-known that individualistic behaviors can be far from the optimum/maximum in terms of utilitarian evaluation $u(\bm{a})=\sum_{i\in N}u^{i}(\bm{a})$. In single-objective games[^4], this inefficiency is measured by the *Coordination Ratio* $\mbox{CR}=\frac{\min[u(PN)]}{\max[u(A)]}$ [@koutsoupias1999worst], which is more commonly known as the *Price of Anarchy* [@roughgarden2009intrinsic]. However, in the multi-objective case, the utilitarian social welfare $\bm{u}(\bm{a})=\sum_{i\in N}\bm{u}^{i}(\bm{a})$ is a vector-valued function $\bm{u}:A\rightarrow{\mathbb{R}}^d$ with respect to $d$ objectives. To study the efficiency of Pareto-Nash equilibria, we introduce:

-   set of *equilibria outcomes* $\quad{\mathcal{E}}\quad=\quad\bm{u}({\mbox{PN}})\quad(\subset{\mathbb{R}^d}),$

-   set of *efficient outcomes* $\quad{\mathcal{F}}\quad=\quad{\mbox{EFF}}[\bm{u}(A)]\quad(\subset{\mathbb{R}^d})$.

![Biobjective set of utilitarian outcomes $\bm{u}(A)\subset{\mathbb{R}}^2$ in Ocean Shores.](Figure2.png)

 

The utilitarian outcomes are a set of vectors, depicted above. Worst case equilibria and optima are not uniquely defined. The ratio of set of equilibria outcomes ${\mathcal{E}}$ ($\Diamond$) to set of efficient outcomes ${\mathcal{F}}$ ($\times$) would be a ratio of sets, which remains undefined. It would be crucial that such a definition keeps information for every objective. E.g., we want to remember that a car pollutes, or that a cigarette kills, not just that it makes some economic agents happy.

Numerous pure strategy Pareto-Nash equilibria exist.
====================================================

This section demonstrates the existence of pure strategy Pareto-Nash equilibria. Firstly, we write how the existence results from single-objective (SO) games can be retrieved in MO games. Secondly, we generalize the equilibria existence results of single-objective potential games to multi-objective potential games. Thirdly, we show that on average, numerous Pareto-Nash equilibria exist.

Reductions from MO games to SO games
------------------------------------

In the literature, most rationalities are constructed by means of a utility function $v^{i}:{\mathbb{R}}^{d}\rightarrow{\mathbb{R}}$, which is monotonic with respect to the Pareto-dominance, that is: $$\begin{aligned}
\bm{x}{\succ}\bm{y} &\Rightarrow& v^{i}(\bm{x})> v^{i}(\bm{y})\end{aligned}$$ Such functions are called *Pareto-monotonic*. For instance, these include positive weighted sums, Cobb-Douglas utilities, and utility functions in general as assumed by the Arrow-Debreu theorem.

A straightforward consequence is that the set of Pareto-efficient vectors contains the optima of any Pareto-monotonic utility function. Formally, given a MOG $\Gamma$, from Pareto-monotonic utility functions $V=(v^{i}:{\mathbb{R}^d}\rightarrow{\mathbb{R}}|i\in N)$ the single-objective game $V\circ\Gamma=(N,\{A^{i}\}_{i\in N},\{v^{i}\circ \bm{u}^{i}\}_{i\in N})$ results from the given utilities, and one has: ${\mbox{PN}}(V\circ\Gamma)\subseteq{\mbox{PN}}(\Gamma).$ In other words, Pareto-Nash equilibria encompass the game’s outcome, regardless of the unknown preferences.

Also, inclusion ${\mbox{PN}}(V\circ\Gamma)\subseteq{\mbox{PN}}(\Gamma)$ argues for the guaranteed existence of numerous PN equilibria in MO games, under the following assumptions:

1.  the structure of the SO game on every objective is the same,

2.  equilibria are guaranteed in that structure of SO game,

3.  and a positive linear combination of the MO game induces that SO game.

This remark is the canonical argument used in previous results (e.g. [@shapley1959equilibrium; @patrone2007multicriteria]).

Multi-objective potentials
--------------------------

We now explore potential games, as introduced for congestion games by Robert Rosenthal [@rosenthal1973class; @monderer1996potential] and recently generalized to MO games [@patrone2007multicriteria]. The existence of an MO potential function guarantees that at least one Pareto-Nash equilibrium exists [@patrone2007multicriteria]. We go further and completely characterize the set of PN equilibria.

An MO game $\Gamma=\left(N,\{A^{i}\}_{i\in N},{{\mathcal{D}}},\{\bm{u}^{i}\}_{i\in N}\right)$ admits *(exact) potential function* $\bm{\Phi}:A\rightarrow{\mathbb{R}}^{d}$ if and only if for every action-profile $\bm{a}\in A$, for every agent $i\in N$ and for every action $b^{i}\in A^{i}$, one has: $$\forall k\in{{\mathcal{D}}},\quad
\Phi_k(b^{i},\bm{a}^{-i})-\Phi_k(\bm{a})\quad=\quad u^{i}_k(b^{i},\bm{a}^{-i})-u^{i}_k(\bm{a}).$$

That is, function $\bm{\Phi}$ additively accumulates the vectorial values of each deviation.

Given a vector valued function $\bm{\Phi}:A\rightarrow{\mathbb{R}}^{d}$, let the set of *locally efficient* action-profiles ${\mbox{LOC}}(\bm{\Phi})$ be the set of action-profiles $\bm{a}\in A$ such that: $$\bm{\Phi}(\bm{a})\quad\in\quad{\mbox{EFF}}[\{\bm{\Phi}(b^{i},\bm{a}^{-i})\in{\mathbb{R}}^{d}\mid i\in N,b^{i}\in A^{i}\}].$$

Set ${\mbox{LOC}}(\bm{\Phi})$ corresponds to a generalization of local optima for function $\bm{\Phi}$, and is non-empty if sets $N$, ${{\mathcal{D}}}$ and $A$ are finite. Moreover, due to the loose requirement for local efficiency, set ${\mbox{LOC}}(\bm{\Phi})$ is likely to contain numerous action-profiles.

\[th:1\] Let $\Gamma=\left(N,\{A^{i}\}_{i\in N},{{\mathcal{D}}},\{\bm{u}^{i}\}_{i\in N}\right)$ be a *finite multi-objective game*[^5] that admits potential function $\bm{\Phi}$. Then, it holds that: $${\mbox{PN}}(\Gamma)\quad=\quad{\mbox{LOC}}(\bm{\Phi})\quad\neq\quad\emptyset.$$

This theorem completely characterizes the set of Pareto-Nash equilibria as the set of locally efficient action-profiles for function $\bm{\Phi}$, which is a non-empty set with numerous action-profiles. More generally, Theorem \[th:1\] also holds when sets $N$ and ${{\mathcal{D}}}$ are finite and sets $A^i$ are just compact.

Likelihood of equilibrium in random games
-----------------------------------------

Another manner to study whether a ${\mbox{PN}}$-equilibrium exists is to provide a probability distribution on a family of finite games and then discuss the probability of ${\mbox{PN}}$-equilibrium existence. A similar methodology was successfully applied [@goldberg1968probability; @dresher1970probability; @rinott2000number] to SO games in several settings where every SO payoff $u^{i}(\bm{a})$ is independently and identically distributed by a uniform distribution on continuous intervals $[0,1]$. At the heart of this subsection, let random variable $Z$ denote the number of pure Nash-equilibria action-profiles in the game. In the SO case, there is almost surely only one best response. However, when considering MO games, a main technical difference lies in the average number of “best responses” (or here, Pareto-efficient responses), which in most cases exceeds $1$, due to the surface-like shape of the Pareto-efficient set in ${\mathbb{R}}^{d}$, surface which is $(d-1)$ dimensional. Here, we assume a probability distribution ${\mathbb{P}}_{n,\alpha,\beta}$, that builds randomly the Pareto-efficient response tables of an $n$-agent normal form game with $\alpha$ actions-per-agent: for every agent $i$ and every adversary action-profile $\bm{a}^{-i}\in\prod_{j\neq i}A^{j}$, there is a fixed number $\beta:1<\beta\leq\alpha$ of Pareto-efficient responses, for the sake of simplicity.

Given numbers $n\geq2$ of agents, $\alpha\geq2$ of actions-per-agent and $\beta\leq\alpha$ of Pareto-efficient responses, based on probability distribution ${\mathbb{P}}_{n,\alpha,\beta}$, the number $Z$ of Pareto-Nash equilibria satisfies ${\mathbb{E}}[Z] = \beta^n$ and: $$\begin{aligned}
{\mathbb{P}}\left( (1-\gamma)\beta^n\leq {Z} \leq (1+\gamma)\beta^n \right) & \geq & 1 - \frac{1}{\gamma^2 \beta^{n}},\quad\forall\gamma\in(0,1). \end{aligned}$$

It argues for the existence of numerous Pareto-Nash equilibria when there are enough agents and efficient responses, and follows from the Bienaymé-Tchebychev inequality. For instance, (given $\gamma=1/2$) the probability that the number of Pareto-Nash equilibria $Z$ is between $(1/2)\beta^{n}$ and $(3/2)\beta^{n}$, is at least $1-4\beta^{-n}$, which for $\beta=2$ efficient responses and $n=5$ agents, gives ${\mathbb{P}}(16\leq Z\leq48)\geq7/8$.

Consistent extension to mixed strategies {#sec:mixed}
========================================

To guarantee equilibrium existence by means of fixed-point theorems on compact sets [@vnmAndMorgenstern1944; @nash1950equilibrium], the finite action sets of every agent are expanded to include *mixed strategies*. That is: every agent $i$ decides a probability distribution $p^{i}$ in the set $\Delta(A^{i})$ of probability distributions over his action-set $A^{i}$. Each payoff function $\bm{u}^{i}$ is redefined to be the expected utility $$\begin{aligned}
\bm{u}^{i}(\bm{p}) &=& {\mathbb{E}}_{\bm{a}\sim\bm{p}}[\bm{u}^{i}(\bm{a})],\end{aligned}$$ under the mixed-strategy profile $\bm{p}=(p^{1},\ldots,p^{n})\in\prod_{i\in N}\Delta(A^{i})$. This defines a mixed-extension of the original game. The stability concept induced is called a mixed-strategy Nash equilibrium.

In MOGs, Pareto-Nash equilibria based on their original definition by Blackwell [@blackwell1956analog] and Shapley [@shapley1959equilibrium] (below) are those usually considered [@borm1988pareto; @corley1985games; @voorneveld1999potential; @zeleny1975games].

Given finite MO game $\Gamma=\left(N,\{A^{i}\}_{i\in N},\{{{\mathcal{D}}}\},\{\bm{u}^{i}\}_{i\in N}\right)$, a mixed-strategy profile $\bm{p}=(p^{1},\ldots,p^{n})\in\prod_{i\in N}\Delta(A^{i})$ is a mixed-strategy Pareto-Nash equilibrium if and only if it satisfies for every agent $i$: $$\bm{u}^{i}(p^{i},\bm{p}^{-i})\in{\mbox{EFF}}\left[\left\{ \bm{u}^{i}(q^{i},\bm{p}^{-i})\in{\mathbb{R}}^{d}\mid q^{i}\in\Delta(A^{i})\right\} \right]$$

The rational behind this first definition is the following. For every agent $i$, mixed-strategy $p^{i}\in\Delta(A^{i})$ acts as a convex-combination of set of vectorial payoffs $\bm{u}^{i}(A^{i},\bm{p}^{-i})$ and the best-response condition is replaced by the fact that mixed-strategy $p^{i}$ should have a Pareto-efficient evaluation $\bm{u}^{i}(p^{i},\bm{p}^{-i})$ among the elements of this convex set of evaluations $\{\bm{u}^{i}(q^{i},\bm{p}^{-i})\in{\mathbb{R}}^{d}\mid q^{i}\in\Delta(A^{i})\}$. That is, a mixed-strategy Pareto-Nash equilibrium is a pure-strategy Pareto-Nash equilibrium in finite game $\Gamma$’s mixed extension. However, as depicted in Figure \[fig:mix\], Definition 1 fails to fulfill two fundamental requirements:

1.  Pure-strategy equilibria must be included in mixed-strategy equilibria.

2.  Mixed-strategies also enable to model a risk-averse agent.

Figure 3 demonstrates these side effects.

To fulfill the two requirements, instead of efficient mixed actions, we consider mixtures of efficient pure-actions. As in Figure \[fig:mix\], it corrects both side effects.

Given a finite multi-objective game $\left(N,\{A^{i}\}_{i\in N},\{{{\mathcal{D}}}\},\{\bm{u}^{i}\}_{i\in N}\right)$, a mixed-strategy Pareto-Nash equilibrium is a mixed-strategy profile$\bm{p}=(p^{1},\ldots,p^{n})\in\prod_{i\in N}\Delta(A^{i})$, such that for every agent $i$ and action $a^{i}\in A^{i}$ if $a^{i}$ is played with positive probability $p^{i}(a^{i})>0$, then it holds that $$\bm{u}^{i}(a^{i},\bm{p}^{-i})\quad\in\quad{\mbox{EFF}}\left[\bm{u}^{i}(A^{i},\bm{p}^{-i})\right].$$

![Single-agent three-actions bi-objective game showing inconsistencies. (The coordinates correspond to the bi-objective valuation $(u_1,u_2)$.)[]{data-label="fig:mix"}](Figure3.png)

 

The three outcomes, $u(A)=\{(1,4),(2,2),(4,1)\}$, are depicted by black dots. With Def. 4, since the mixed outcomes are all convex-combinations of $\{(1,4),(2,2),(4,1)\}$, the Pareto-efficient mixed-strategies are here the convex-combinations of $\{(1,4),(4,1)\}$; and outcome $(2,2)$ is Pareto-dominated. Not every pure-strategy Pareto-Nash equilibrium is a mixed-strategy one, which is a severe inconsistency. Furthermore, since outcome $(2,2)$ is well balanced, it may also be decided with a non-null probability, e.g., if the agent’s utility is concave [@cobb1928theory], or if she is risk-averse [@kahneman1979prospect]. Our *revised* definition considers instead all the convex-combinations of the Pareto-efficient pure actions $\{(1,4),(2,2),(4,1)\}$.

This generalized definition connects in the single-objective case to a less know definition of Nash-equilibria (see [@papadimitriou2007agt], page 30, Theorem 2.1). In this alternative definition, each mixed strategy must be a mixture of pure-strategies that are best-responses. In other words, the support of each mixed strategy must be included in the set of pure-strategy best-responses. Furthermore, concerning existence, since this revised definition contains the former one, (which is guaranteed to exist) the new definition is guaranteed to exist too.

Multi-objective coordination ratio 
===================================

In the single-objective case, the coordination ratio measures the efficiency loss of equilibria compared to the optimum. In MO games, we claim that it is critical to study efficiency with respect to every objective. Even after the actions, the game analyst still has access to the vectorial payoffs. In this section, we follow the agenda outlined in the introduction, to define a *multi-objective coordination ratio* $\text{MO-CR}[{\mathcal{E}},{\mathcal{F}}]$ of the set of equilibria outcomes ${\mathcal{E}}$ to the set of efficient outcomes ${\mathcal{F}}$, that fills the critical purpose to keep information on each objective.

First, we state the list of desirable properties that we want the ratio to satisfy. For the purpose of having meaningful divisions and ratios, some vectors are positive in this section. Given vectors $\bm{\rho},\bm{y}\in{\mathbb{R}^d}$ and $\bm{z}\in{\mathbb{R}^d_{+}}$, vector $\bm{\rho}\star \bm{y}\in{\mathbb{R}^d}$ is defined by $\forall k\in{{\mathcal{D}}},(\bm{\rho}\star \bm{y})_{k}=\rho_{k}y_{k}$. Vector $\bm{y}/\bm{z}\in{\mathbb{R}^d}$ is defined by $\forall k\in{{\mathcal{D}}},(\bm{y}/\bm{z})_{k}=y_{k}/z_{k}$. Given vector $\bm{r}\in{\mathbb{R}^d}$ and set of vectors $Y$, set $\bm{r}\star Y$ is defined by $\{\bm{r}\star \bm{y}\in{\mathbb{R}^d_{+}}|\bm{y}\in Y\}$ and for $\bm{r}\in{\mathbb{R}^d_{+}}$, set $Y/\bm{r}$ is defined by $\lbrace \bm{y}/\bm{r}\in{\mathbb{R}^d}|\bm{y}\in Y\rbrace$. Given $\bm{x}\in{\mathbb{R}^d}$, cone ${\mathcal{C}}(\bm{x})$ denotes $\{\bm{y}\in{\mathbb{R}^d}~|~\bm{x}{\succsim}\bm{y}\}$, and given $X\subset{\mathbb{R}^d}$, cone-union ${\mathcal{C}}(X\text{)}$ is defined by $\cup_{\bm{x}\in X}{\mathcal{C}}(\bm{x})$. Vector $\bm{0}$ denotes a vector with $d$ zeros, and $\bm{1}$ denotes a vector with $d$ ones.

The first property that we require from $\mbox{MO-CR}[{\mathcal{E}},{\mathcal{F}}]$ is to be on a *multi-objective ratio scale*. Given ${\mathcal{E}},{\mathcal{F}}\subset{\mathbb{R}^d_{+}}$ and $\bm{r}\in{\mathbb{R}^d_{+}}$, the following shall hold. $$\begin{aligned}
\mbox{MO-CR}[{\mathcal{E}},{\mathcal{F}}] 
&\quad\subseteq& 
{\mathbb{R}^d}\label{eq:ratio:6}\\ 
\mbox{MO-CR}[\{\bm{0}\},{\mathcal{F}}] 
&\quad=& 
\{\bm{0}\}\label{eq:ratio:7}\\ 
\mbox{MO-CR}[\bm{r}\star{\mathcal{E}},{\mathcal{F}}] 
& \quad=& 
\bm{r}\star\mbox{MO-CR}[{\mathcal{E}},{\mathcal{F}}]\label{eq:ratio:8}\\ 
\mbox{MO-CR}[{\mathcal{E}},\bm{r}\star{\mathcal{F}}] 
& \quad=& 
\mbox{MO-CR}[{\mathcal{E}},{\mathcal{F}}]/\bm{r}\label{eq:ratio:9}\\ 
{\mathcal{E}}\subseteq{\mathcal{F}}& \quad\Leftrightarrow& 
\bm{1}\in \mbox{MO-CR}[{\mathcal{E}},{\mathcal{F}}]\label{eq:ratio:10} \end{aligned}$$ To fix these ideas one can think of $d=1$ and given two positive numbers $e,f$, to the properties of ratio $e/f$. Equation (\[eq:ratio:6\]) states that MO-CR is expressed in a multi-objective space. Equations (\[eq:ratio:7\]), (\[eq:ratio:8\]) and (\[eq:ratio:9\]) state that MO-CR is well-centered and sensitive on each objective to multiplications of outcomes, which is what we want. For instance, if ${\mathcal{E}}$ is three times better on objective $k$, then so is MO-CR. If there are two times more efficient opportunities in ${\mathcal{F}}$ on objective $k'$, then MO-CR is one half on objective $k'$. In other words, the efficiency of each objective independently reflects on MO-CR in a ratio-scale. Equation (\[eq:ratio:10\]) states that if all equilibria outcomes are efficient (i.e. ${\mathcal{E}}\subseteq{\mathcal{F}}$), then this amounts to $\bm{1}\in\text{MO-CR}[{\mathcal{E}},{\mathcal{F}}]$, i.e. the MO game is fully efficient.

These requirements rule out a set of first ideas. For instance, we can rule out comparisons of equilibria outcomes to ideal vector $\mathcal{I}=(\max_{z\in{\mathcal{F}}}\lbrace z_{k}\rbrace|k\in{{\mathcal{D}}})$ does not satisfy requirement (5) to have $\bm{1}\in\text{MO-CR}[{\mathcal{E}},{\mathcal{F}}]$ when ${\mathcal{E}}\subseteq{\mathcal{F}}$. By starting from a social welfare $f:{\mathbb{R}^d_{+}}\rightarrow{\mathbb{R}}_+$, taking ratio $\min f({\mathcal{E}})/\max f({\mathcal{F}})$, induces the same problem.

This measurement should also be non-dictatorial, in the sense that no point of view should be imposed on what the overall efficiency is: no prior choice must be done on the set of efficient outcomes. Formally, if two sets of efficient outcomes ${\mathcal{F}},{\mathcal{F}}'\subset{\mathbb{R}^d_{+}}$ differ even slightly, then this must reflect at least for some numerator set ${\mathcal{E}}$ onto ratio $\text{MO-CR}[{\mathcal{E}},{\mathcal{F}}]$. This amounts to a disjunction on efficient outcomes. Finally $\text{MO-CR}[{\mathcal{E}},{\mathcal{F}}]$ must provide guaranteed efficiency ratios that hold for every equilibrium outcome $\bm{y}\in{\mathcal{E}}$, which amounts to a conjunction on equilibria outcomes. The definition below follows from these requirements.

Firstly, the efficiency of *one* equilibrium $\bm{y}\in{\mathcal{E}}$ is quantified without prior choices on what efficient outcome should we compare it to, as required: $$\begin{aligned}
R[\bm{y},{\mathcal{F}}]\quad =\quad \bigcup_{\bm{z}\in{\mathcal{F}}}{\mathcal{C}}(\bm{y}/\bm{z}), \end{aligned}$$ The idea is that we do not take sides with any efficient outcome. Instead, we define with flexibility and without a dictatorship a disjunctive set of guaranteed efficiency ratios, which lets the differences between two sets of efficient outcomes ${\mathcal{F}},{\mathcal{F}}'\subset{\mathbb{R}^d_{+}}$ reflect onto ratio $\text{MO-CR}[{\mathcal{E}},{\mathcal{F}}]$.

Secondly, in MOGs, on average, there are many Pareto-Nash equilibria. An efficiency *guarantee* $\bm{\rho}\in{\mathbb{R}^d}$ should hold for every equilibrium outcome. It induces this conjunctive definition of the set of guaranteed vectorial ratios: $$\begin{aligned}
R[{\mathcal{E}},{\mathcal{F}}]\quad=\quad\bigcap_{\bm{y}\in{\mathcal{E}}} R[\bm{y},{\mathcal{F}}]. \end{aligned}$$

In fact, because of the conjunction on equilibria outcomes, the set $R[{\mathcal{E}},{\mathcal{F}}]$ only depends on sets ${\mbox{WST}}[{\mathcal{E}}]$ (instead of set ${\mathcal{E}}$) and ${\mathcal{F}}$.

Finally, if two bounds on efficiencies $\bm{\rho}$ and $\bm{\rho}'$ are such that $\bm{\rho}{\succ}\bm{\rho}'$ (e.g. the former guarantees fraction $\bm{\rho}=(0.75,0.75)$ of efficiency and the later fraction $\bm{\rho}'=(0.5,0.5)$), then $\bm{\rho}'$ brings no more information; hence, MO-CR is defined using ${\mbox{EFF}}$ on the guaranteed efficiency ratios $R[{\mbox{WST}}[{\mathcal{E}}],{\mathcal{F}}]$. These points are summed up in the following definition:

\[def:MOCR\] Given an MO game, vector $\bm{\rho}\in{\mathbb{R}^d}$ bounds its inefficiency (i.e. $\bm{\rho}\in R[{\mathcal{E}},{\mathcal{F}}]$) if and only if the following holds (see Fig. 4) : $$\forall \bm{y}\in{\mathcal{E}},\quad\exists \bm{z}\in{\mathcal{F}},\quad \bm{y}/\bm{z}{\succsim}\bm{\rho}.$$ The multi-objective coordination ratio $\text{MO-CR}[{\mathcal{E}},{\mathcal{F}}]$ is then defined as: $$\text{MO-CR}[{\mathcal{E}},{\mathcal{F}}]\quad=\quad{\mbox{EFF}}[R[{\mbox{WST}}[{\mathcal{E}}],{\mathcal{F}}]].$$

![Didactic depiction of a guaranteed vectorial ratio $\bm{\rho}$ from $\text{MO-CR}[{\mathcal{E}},{\mathcal{F}}]$.](Figure4)

 

The most famous results of the coordination ratio (or price of anarchy) are stated analytically on families of games, for instance on congestion games [@christodoulou2005price; @roughgarden2009intrinsic]. Such results would also be desirable in 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 of the agents only depend on a local subset of the agents [@kearns2001graphical]. Graphical games can be generalized in a straightforward manner to assuming vectorial payoffs. Formally, there is a support graph $G=(N,E)$ where each vertex represents an agent, and an agent $i$’s evaluation function only depends on the actions of the agents in his inner-neighbourhood ${\mathcal{N}}(i)=\{j\in N|(j,i)\in E\}$. That is $\bm{u}^i:A^{{\mathcal{N}}(i)}\rightarrow{\mathbb{R}}^d$ maps each local action-profile $\bm{a}^{{\mathcal{N}}(i)}\in A^{{\mathcal{N}}(i)}$ to a multi-objective payoff $\bm{u}^i(\bm{a}^{{\mathcal{N}}(i)})\in{\mathbb{R}}^d$.

An MOGG is a tuple $\left(G=(N,E), \{A^i\}_{i\in N}, {{\mathcal{D}}}, \{\bm{u}^i\}_{i\in N}\right)$. $N$ is the set of agents. $\{A^i\}_{i\in N}$ are their individual action-sets. ${{\mathcal{D}}}$ is the set of all objectives. Every function $\bm{u}^i:A^{{\mathcal{N}}(i)}\rightarrow{\mathbb{R}}^d$ is vector-valued, and its scope is vertex $i$’s neighborhood.

Figure 1 pictures a didactic instance of an MOGG. In the same manner as computing equilibria in graphical games was reduced to junction-tree algorithms [@daskalakis2006computing], it is also possible to exploit a generalized MO junction-tree algorithm [@dubus2009multiobjective; @gonzales2011decision]. However, even though this MO junction-tree algorithm is not in polynomial time (but rather pseudo-polynomial time), it still remains faster than browsing the Cartesian product of action-sets and is tractable on average, as experimented in the appendix. Symmetric games [@jiang2007computing] can also be generalized to MOGs:

In a *multi-objective symmetric game*, individual payoffs are not impacted by the agents’ identities. There is one sole action-set $A^{\ast}$ for every agent $i$. So, when deciding action $a^{\ast}\in A^{\ast}$, the multi-objective reward only depends on the number of agents that decided every action. Consequently, the game is not specified for every action-profile $\bm{a}\in A=\prod_{i\in N}A^{\ast}$ and every agent $i$, but rather for every action $a^{\ast}\in A^{\ast}$ and every *configuration* $c:A^{\ast}\rightarrow\mathbb{N}$, where number $c(a^{\ast})\in\mathbb{N}$ indicates the number of agents deciding action $a^{\ast}$. Therefore, the utility is given by a function $\bm{u}^{\ast}$ such that $\bm{u}^{\ast}(a^{\ast},c)\in{\mathbb{R}}^{d}$ is the payoff for deciding action $a^{\ast}$ when configuration $c$ occurs.

There is a number ${n+\alpha-1 \choose \alpha-1}$ of configurations[^6] to which the MO symmetric game associates MO vectors. As a consequence, generalizing to vectorial payoffs, the representation length is $L=\alpha{n+\alpha-1 \choose \alpha-1}d$, and when the numbers $\alpha$ and $d$ are fixed constant, length is $L(n)\in\Theta\left(\alpha n^{\alpha}d\right)$. Quite simply, for computing ${\mathcal{E}}$, ${\mbox{EFF}}[{\mathcal{E}}]$ and ${\mbox{WST}}[{\mathcal{E}}]$, configurations enumeration already takes polynomial time.

Given a multi-objective symmetric game with fixed $\alpha$,

-   computing ${\mbox{PN}}$ and ${\mathcal{E}}$ takes time $O(n^{\alpha}\alpha^{2}d)=O(L\alpha)$;

-   computing ${\mbox{EFF}}[{\mathcal{E}}]$ and ${\mbox{WST}}[{\mathcal{E}}]$ takes time $O(n^{2\alpha}d)=O(L^{2})$. If $d=2$, this lowers to $O(L(\alpha+\log_{}(L)))$.

Computing MO-CR
---------------

In this subsection, we address the problem of computing the set $\text{MO-CR}[{\mathcal{E}},{\mathcal{F}}]$, given sets of worst equilibria outcomes ${\mbox{WST}}[{\mathcal{E}}]$ and efficient outcomes ${\mathcal{F}}$. Algorithm 1 (below) computes such set. In the algorithm, set $D^{t}$ denotes a set of vectors. Given two vectors, $\bm{x},\bm{y}\in{\mathbb{R}^d_{+}}$, let $\bm{x}\wedge \bm{y}$ denote the vector defined by $\forall k\in{{\mathcal{D}}},~(\bm{x}\wedge \bm{y})_{k}=\min\{x_{k},y_{k}\}$, let $\bm{x}^{\bm{y}}\in{\mathbb{R}^d_{+}}$ be the vector defined by $\forall k\in{{\mathcal{D}}}, (\bm{x}^{\bm{y}})_k=(x_k)^{y_k}$, and recall that $\forall k\in{{\mathcal{D}}},~(\bm{x}/\bm{y})_{k}=x_{k}/y_{k}$.

 \
\[-1.5ex\] [**create** ]{} $D^1\leftarrow \{\bm{y}^1/\bm{z}\in{\mathbb{R}^d_{+}}~|~\bm{z}\in{\mathcal{F}}\}$\
$D^q$

Algorithm 1 outputs $\text{MO-CR}[{\mathcal{E}},{\mathcal{F}}]$ in poly-time $O((qm)^{2d-1}d),$ where $q=|{\mbox{WST}}[{\mathcal{E}}]|$ and $m=|{\mathcal{F}}|$ denote the size of the inputs, and $d$ is fixed.

Algorithm 1 calculates product $\cap_{\bm{y}\in{\mbox{WST}}[{\mathcal{E}}]}\cup_{\bm{z}\in{\mathcal{F}}}{\mathcal{C}}(\bm{y}/\bm{z})$, where there could be $m^q$ terms in the output. This set-algebra of cone-unions is compact.

A decisive corollary is that given an MO game with length $L$ that satisfies $q=O(\text{poly}(L))$, $m=O(\text{poly}(L))$ and both sets ${\mbox{WST}}[{\mathcal{E}}]$ and ${\mathcal{F}}$ are computable in time $O(\text{poly}(L))$, then one can compute $\text{MO-CR}$ in polynomial time $O(\text{poly}(L))$. For instance, it is the case with MO normal forms or MO symmetric games. So this approach is not intractable in the most basic cases.

Approximation of the MO-CR for MO compact representations
---------------------------------------------------------

Unfortunately, Algorithm 1 is not practical when the MO game has a compact form and cardinalities $q,m$ are exponentials with respect to the compact size of the game’s representation. For instance, this is the case for multi-objective graphical games. Theorem \[th:approx\] below answers this issue by taking only a small and approximate representation of sets ${\mbox{WST}}[{\mathcal{E}}]$ and ${\mathcal{F}}$, in order to output a guaranteed approximation of sets $\text{MO-CR}$ or $R[{\mbox{WST}}[{\mathcal{E}}],{\mathcal{F}}]$. This suggests the following general method:

1.  Given a compact MOG representation, compute quickly an approximation $E^{(\varepsilon)}$ of ${\mbox{WST}}[{\mathcal{E}}]$ and an approximation $F^{(\varepsilon')}$ of ${\mathcal{F}}$.

2.  Then, given $E^{(\varepsilon)}$ and $F^{(\varepsilon')}$, use Algorithm 1 to approximate the MO-CR.

For this general method to be implemented rigorously, we must specify the precise definitions of the two approximations required in input, for the desired output to be indeed some approximation of the MO-CR.

Firstly, let us specify the [output]{}. The ratios in $R[{\mbox{WST}}[{\mathcal{E}}],{\mathcal{F}}]$ must be represented, even approximately, but only by using valid ratios of efficiency, as below.

\[def:covering\] Given $R\subset{\mathbb{R}^d_{+}}$ and $\varepsilon>0$,    $R^{(\varepsilon)}\subset R$ is a $(1+\varepsilon)$-covering of $R$, if and only if: $$\forall \bm{\rho}\in R,\quad
\exists \bm{\rho}'\in R^{(\varepsilon)}:\quad
(1+\varepsilon)\bm{\rho}' {\succsim}\bm{\rho}$$

For instance, $R[{\mbox{WST}}[{\mathcal{E}}],{\mathcal{F}}]$ is $(1+0)$-covered by $\text{MO-CR}={\mbox{EFF}}[R[{\mbox{WST}}[{\mathcal{E}}],{\mathcal{F}}]]$. Denote $\bm{\varphi}:{\mathbb{R}^d_{+}}\rightarrow{\mathbb{N}^d}$ the discretization into the $(1+\varepsilon)$-logarithmic grid. Given a vector $\bm{x}\in{\mathbb{R}^d_{+}}$, $\bm{\varphi}(x)$ is defined by: $\forall k\in{{\mathcal{D}}},~~\varphi_k(x)=\lfloor\log_{(1+\varepsilon)}(x_k)\rfloor$. A typical implementation of $(1+\varepsilon)$-coverings are the logarithmic $(1+\varepsilon)$-coverings, which consist in taking one vector of $R$ in each reciprocal image of $\bm{\varphi}(R)$. That is, for each $\bm{l}\in\bm{\varphi}(R)$, take one $\bm{\rho}$ in $\bm{\varphi}^{-1}(\bm{l})$. The logarithmic grid is depicted in Fig. \[fig:mo:approx\].

Now we must specify rigorously what approximate representations $E^{(\varepsilon_1)}$ of set ${\mbox{WST}}[{\mathcal{E}}]$, and $F^{(\varepsilon_2)}$ of set ${\mathcal{F}}$ we should take in input, in order to guarantee that $R[E^{(\varepsilon_1)},F^{(\varepsilon_2)}]$ is an $(1+\varepsilon)$-covering of $R[{\mbox{WST}}[{\mathcal{E}}],{\mathcal{F}}]$. Definitions \[def:under:covering\] and \[def:stick:covering\] come from the need of specific approximate representations that will carry the guarantees to the approximate final output $R[E^{(\varepsilon_1)},F^{(\varepsilon_2)}]$.

\[def:under:covering\] Given $\varepsilon>0$, $E\subset{\mathbb{R}^d_{+}}$ and $E^{(\varepsilon)}\subset{\mathbb{R}^d_{+}}$, $E^{(\varepsilon)}$ $(1+\varepsilon)$-[under]{}-covers $E$ if and only if: $$\begin{aligned}
\forall \bm{y}\in E,~~
\exists \bm{y}'\in E^{(\varepsilon)} &:&
\bm{y}{\succsim}\bm{y}'\\
\text{and}~~~
\forall \bm{y}'\in E^{(\varepsilon)},~~
\exists \bm{y}\in E &:&
(1+\varepsilon)\bm{y}'{\succsim}\bm{y}\end{aligned}$$

The first condition states that $E^{(\varepsilon)}$ bounds $E$ from below. The second condition states that this lower bound is precise within a multiplicative $(1+\varepsilon)$. Given $E$, one can implement Definition \[def:under:covering\] by using the log-grid (see e.g. Fig. \[fig:mo:approx\]): $$E^{(\varepsilon)}\leftarrow{\mbox{WST}}\left[~~\left\{~\bm{e}^{\bm{l}}\in{\mathbb{R}^d_{+}}\mid \bm{l}\in\bm{\varphi}\left({\mbox{WST}}[{\mathcal{E}}]\right)\right\}~~\right]$$ where $\bm{\varphi}({\mbox{WST}}[{\mathcal{E}}])=\{\bm{\varphi}(\bm{y})\in{\mathbb{N}^d}\mid\bm{y}\in {\mbox{WST}}[{\mathcal{E}}]\}$, and given $\bm{l}\in{\mathbb{N}^d}$, the vector $\bm{e}^{\bm{l}}$ is defined by $(\bm{e}^{\bm{l}})_k=(1+\varepsilon)^{l_k}$. Now let us state what approximation is required on the set of efficient outcomes ${\mathcal{F}}$.

\[def:stick:covering\] Given $\varepsilon>0$, $F\subset{\mathbb{R}^d_{+}}$ and $F^{(\varepsilon)}\subset{\mathbb{R}^d_{+}}$, $F^{(\varepsilon)}$ $(1+\varepsilon)$-[stick]{}-covers $F$ if and only if: $$\begin{aligned}
\forall \bm{z}'\in F^{(\varepsilon)},~~
\exists \bm{z}\in F &:&
\bm{z}'{\succsim}\bm{z}\\
\text{and}~~~
\forall \bm{z}\in F,~~
\exists \bm{z}'\in F^{(\varepsilon)} &:&
(1+\varepsilon)\bm{z}{\succsim}\bm{z}'\end{aligned}$$

The first condition is easily satisfiable by $F^{(\varepsilon)}\subseteq F$. The second condition states that $F^{(\varepsilon)}$ sticks to $F$. Given $F$, one can implement Definition \[def:stick:covering\] as in Figure \[fig:mo:approx\]: Take one element of ${\mathcal{F}}$ per cell of the logarithmic grid, and then take ${\mbox{WST}}$ of this set of elements. Now we can state that with an approximate Phase 1, the precision transfers to Phase 2 in polynomial time, as follows.

![MO approximations, depictions of under and stick coverings[]{data-label="fig:mo:approx"}](art1/logGridphi.pdf)

 

$E^{(\varepsilon)}$ (the green dots below ${\mbox{WST}}[{\mathcal{E}}]$) is a $(1+\varepsilon)$-under-covering of set ${\mbox{WST}}[{\mathcal{E}}]$.\
$F^{(\varepsilon)}$ (the three red dots in ${\mathcal{F}}$) is a $(1+\varepsilon)$-stick-covering of the dark-red set ${\mathcal{F}}$.

\[lem:approx\] Given $\varepsilon_1,\varepsilon_2>0$ and approximations $E$ of ${\mathcal{E}}$ and $F$ of ${\mathcal{F}}$, if $$\begin{aligned}
\forall \bm{y}\in{\mathcal{E}}, \exists \bm{y}'\in E,\quad \bm{y}{\succsim}\bm{y}' &
\quad \text{and}\quad & 
\forall \bm{y}'\in E, \exists \bm{y}\in{\mathcal{E}},\quad (1+\varepsilon_1)\bm{y}'{\succsim}\bm{y}\label{eq:approx:E}\\
\forall \bm{z}'\in F, \exists \bm{z}\in{\mathcal{F}},\quad \bm{z}'{\succsim}\bm{z} &
\quad \text{and}\quad & 
\forall \bm{z}\in{\mathcal{F}}, \exists \bm{z}'\in F,\quad (1+\varepsilon_2)\bm{z}{\succsim}\bm{z}'\label{eq:approx:F}\end{aligned}$$ holds, then it follows that $R[E,F]\subseteq R[{\mathcal{E}},{\mathcal{F}}]$ and: $$\begin{aligned}
\forall \bm{\rho}\in R[{\mathcal{E}},{\mathcal{F}}],\quad \exists \bm{\rho}'\in R[E,F],\quad (1+\varepsilon_1)(1+\varepsilon_2)\bm{\rho}'{\succsim}\bm{\rho}\label{eq:approx:R}\end{aligned}$$

Equations (\[eq:approx:E\]) and (\[eq:approx:F\]) state approximation 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, when studying a dynamics based on a refinement of the Pareto-dominance, convergence is not always guaranteed.

Pareto-Nash equilibria, which encompass the possible outcomes of MO games, very likely exist. The precision of PN-equilibria inevitably relies on the uncertainty on preferences. A promising research path would be to linearly constrain the utility functions of agents. This would induce a polytope and would boil down to another MO game where every objective corresponds to an extreme point of the induced polytope. The efficiency of several multi-objective games could be analyzed by using the contributions in this paper.

Proof of Theorem 1
==================

Let $0_d\in{\mathbb{R}}^d$ denote the $d$-dimensional MO vector with $d$ zero components. Let $a\in A$ be an action-profile. To state that $a$ is a ${\mbox{PN}}$-equilibrium is equivalent to state that for every agent $i$ and every individual deviation $b^i\in A^i$, it holds that: $$u^i(b^i,a^{-i})
\quad\not{\succ}\quad
u^i(a)$$ From the definition of a potential $\Phi$, it is equivalent to state that, for every agent $i$ and every individual deviation $b^i\in A^i$, it holds that: $$\Phi(b^i,a^{-i})-\Phi(a)
\quad =\quad
u^i(b^i,a^{-i})-u^i(a)
\quad\not{\succ}\quad
0_d$$ That is, $\Phi(b^i,a^{-i})\not{\succ}\Phi(a)$, which means that $a\in{\mbox{LOC}}(\Phi)$.

Furthermore, the existence of local optima for the potential function generalizes to the MO case: The set of locally-Pareto-efficient action-profiles is necessarily non-empty, otherwise, given $t\in\mathbb{N}$, whatever the action-profile $a_{(t)}$, one could always find an action-profile $a_{(t+1)}$ in its neighbourhood of individual deviations, such that $\Phi(a_{(t+1)}){\succ}\Phi(a_{(t)})$. Therefore, one could build an infinite sequence $(a_{(t)})_{t\in\mathbb{N}}$ such that $\Phi(a_{(t+1)}){\succ}\Phi(a_{(t)})$; and since the Pareto-dominance ${\succ}$ is a strict partial order and $\Phi$ a (deterministic) function, one would have an infinite number of distinct action-profiles, contradicting the fact that $|A|\leq \alpha^n$ is finite.

Proof of Theorem 2
==================

We will denote by ${\mathbb{P}}_{n,\alpha,\pi}$ the probability distribution that draws a normal form game (SO or MO) with $n$ agents, $\alpha=\alpha^i=|A^i|$ actions-per-agent, and the payoffs $u^i(a)$ according to the distribution $\pi$ on ${\mathbb{R}}$ or ${\mathbb{R}}^d$. Also, according to ${\mathbb{P}}_{n,\alpha,\pi}$, given an agent $i$ and an action-profile $a=(a^i,a^{-i})$, let us denote by $X_{i,a}\in\{0,1\}$ the random variable (RV) which is equal to $1$ if and only if for agent $i$, the action $a^i$ is a best response (or efficient response) to the adversary action-profile $a^{-i}$. Given an action-profile $a$, let us denote by $Y_{a}=\min_{i\in N}\{X_{i,a}\}$ the binary RV which is equal to $1$ if and only if the action-profile $a$ is a PN equilibrium. Finally, let $Z=\sum_{a\in A} Y_{a}$ denote the number of pure Nash-equilibria action-profiles in the game. For simplicity, we may use the name of a binary random variable as a shorthand for the event that this RV equals $1$. Since for every agent $i$ and every adversary action-profile $a^{-i}$ there is (almost surely) only one best-response $b^i\in A^i$ in $u^i(A^i,a^{-i})$ (because payoffs are almost surely different), an IID uniform distribution on $[0,1]$ amounts to whatever IID distribution that will almost surely draw uniformly one single best-response in $u^i(A^i,a^{-i})$.

*Generalization to multi-objective.* While in the SO case, there is almost surely only one best-response, when considering MO games, the main technical difference lies in the average number of “best-responses” (or here, Pareto-efficient responses) which is in most cases greater than $1$, due to the $(d-1)$ dimensional surface-like shape of the Pareto-efficient set in ${\mathbb{R}}^d$. For instance, it can be shown that when drawing a number $\alpha$ of MO payoffs according to a uniform distribution on the simplex $\mathcal{S}_{{{\mathcal{D}}}}=\{u\in{\mathbb{R}}_+^d\mid \sum_{k\in{{\mathcal{D}}}}u_k\leq 1\}$, then by counting the vectors on the outer face, the number $\beta$ of Pareto-efficient vectors among the $\alpha$ vectors satisfies: $$\begin{aligned}
{\mathbb{E}}[\beta] & \quad \sim \quad &
\frac{d}{(d!)^{1/d}}~~\alpha^{\frac{d-1}{d}}
\quad\quad\quad\text{as}\quad
\alpha\rightarrow\infty
\label{eq:integfac}\end{aligned}$$ in the sense that the ratio of the left and right members of $\sim$ tends to $1$. As a consequence, on the simplex $\mathcal{S}_{{{\mathcal{D}}}}$, one quickly has a number of Pareto-efficient responses $\beta$ strictly greater than $1$ as the number of actions $\alpha$ grows. (The number of objectives $d$ is fixed.)

For the sake of simplicity, we then assume a probability distribution ${\mathbb{P}}_{n,\alpha,\beta}$, that builds randomly an $n$-agents normal form game with $\alpha$ actions-per-agent. For the sake of simplicity, for every agent $i$, and every adversary action-profile $a^{-i}\in\prod_{j\neq i} A^j$, there is a fixed number $\beta:1\leq\beta\leq\alpha$ of Pareto-efficient responses (supposedly, according to some vectorial payoffs $u^i(A^i,a^{-i})$ selected independently and uniformly at random in $A^i$). Recall that the number $\beta$ can be reasonably supposed greater than $1$ (see Equation \[eq:integfac\]).

[@bienayme1867] Recall that the Bienaymé-Tchebychev inequality states that for a random variable $Z$ with expectancy ${\mathbb{E}}[Z]$ and variance ${\text{Var}}[Z]$, for every parameter $\mu\in{\mathbb{R}}_+$ it holds that: $$\begin{aligned}
{\mathbb{P}}(|Z-{\mathbb{E}}[Z]|\geq \mu) &\leq & \frac{{\text{Var}}[Z]}{\mu}\end{aligned}$$ In simple words, a random variable is unlikely to spread more than its variance.

Let us now study the expectation of the number of PN-equilibria ${\mathbb{E}}_{n,\alpha,\beta}[Z]$. One has: $$\begin{aligned}
 {\mathbb{E}}_{n,\alpha,\beta}\left[Z\right]  &=&  {\mathbb{E}}_{n,\alpha,\beta}\left[\sum_{a\in A} Y_a \right] \label{eq14}\\ &=&  \sum_{a\in A} {\mathbb{E}}_{n,\alpha,\beta}\left[ Y_a \right] \label{eq15}\\ &=&  \sum_{a\in A} {\mathbb{E}}_{n,\alpha,\beta}\left[ \min_{i\in N} X_{i,a} \right] \label{eq16}\\ &=&  \sum_{a\in A} {\mathbb{P}}_{n,\alpha,\beta}\left(\wedge_{i\in N} \{X_{i,a}\} \right) \label{eq17}\\ &=&  \sum_{a\in A} \prod_{i\in N} {\mathbb{P}}_{n,\alpha,\beta}\left( X_{i,a} \right) \label{eq18}\\ &=&  \sum_{a\in A} \prod_{i\in N} \frac{\beta}{\alpha} \label{eq19} \\ &=&  \alpha^n (\beta/\alpha)^n \label{eq110}\\ &=& \beta^n \label{eq111} \end{aligned}$$ Equation (\[eq14\]) uses the definition of the RV $Z$. Equation (\[eq15\]) uses the linearity of expectation. Equation (\[eq16\]) uses the definition of the RV $Y_a$. Equation (\[eq17\]) formulates it as an event. Equation (\[eq18\]) uses the independence of payoffs between agents. Equation (\[eq19\]) uses the definition the probability ${\mathbb{P}}_{n,\alpha,\beta}$: uniform. Equation (\[eq110\]) uses that $|A|=\alpha^n$ and that $\prod_{i\in N}(\beta/\alpha)=(\beta/\alpha)^n$. Equation (\[eq111\]) concludes that: ${\mathbb{E}}[Z]=\beta^n$. Therefore, the number of PN-equilibria $Z$ is in expectation an exponential of basis $\beta$ with respect to the number of agents $n$. Let us now study the variance of the number of PN-equilibria $Z$: $$\begin{aligned}
  & &{\text{Var}}\left(Z\right) \\ &=& {\text{Var}}\left(\sum_{a\in A} Y_a \right)\label{eq:112}\\ &=& \sum_{a\in A} \sum_{b\in A} {\text{Cov}}(Y_a,Y_b)\label{eq:113}\\ &=& \sum_{a\in A} \sum_{b\in A} {\mathbb{E}}[Y_a Y_b] - {\mathbb{E}}[Y_a] {\mathbb{E}}[Y_b]\label{eq:114}\\ &=& \sum_{b\in A} \sum_{a\in A} \left(\prod_{i\in N}{\mathbb{P}}(X_{i,a} X_{i,b}) - \left(\frac{\beta}{\alpha}\right)^{2n}\right)\label{eq:115} \end{aligned}$$ Equation (\[eq:112\]) uses the definition of the RV $Z$. Equation (\[eq:113\]) is the variance of the sum of RVs $\sum_{a\in A} Y_a$. Equation (\[eq:114\]) uses the definition of the covariance ${\text{Cov}}(Y_a,Y_b)$. In Equation (\[eq:115\]) the first terms ${\mathbb{E}}[Y_a Y_b]=\prod_{i\in N}{\mathbb{P}}(X_{i,a} X_{i,b})$ result from the independences of payoffs between players. The second terms ${\mathbb{E}}[Y_a]{\mathbb{E}}[Y_b]=(\beta/\alpha)^{2n}$ result from the same calculus as for the expectation ${\mathbb{E}}[Z]$. Remark that by symmetry, all the $\alpha^n$ terms of the outer sum are equal. Fixing an action-profile $b\in A$, let us continue this calculus below: $$\begin{aligned}
 {\text{Var}}\left(Z\right) &=&  \alpha^n \sum_{a\in A} \left(\prod_{i\in N}{\mathbb{P}}(X_{i,a} X_{i,b}) - \left(\frac{\beta}{\alpha}\right)^{2n}\right)\label{eq:116} \end{aligned}$$Now, having fixed an action-profile $b\in A$, given an action-profile $a$ and an agent $i$, let us study the value of the probability ${\mathbb{P}}(X_{i,a}, X_{i,b})$. Remark that it will depend on whether the random variables $X_{i,a}$ and $X_{i,b}$ are independent or not:

-   If $a^{-i}\neq b^{-i}$, then the payoffs are independent, and one has the probability: $${\mathbb{P}}(X_{i,a}, X_{i,b})={\mathbb{P}}(X_{i,a}){\mathbb{P}}(X_{i,b})=(\beta/\alpha)^2$$

-   If $a^{-i}= b^{-i}$ with $a^i\neq b^i$, then the payoffs are dependent, and one has the probability: $${\mathbb{P}}(X_{i,a}, X_{i,b})={\mathbb{P}}(X_{i,a}~|~X_{i,b}) {\mathbb{P}}(X_{i,b})=\frac{(\beta-1)\beta}{\alpha^2}$$

-   Finally, if $a=b$, then ${\mathbb{P}}(X_{i,a}, X_{i,b})={\mathbb{P}}(X_{i,a})=\beta/\alpha$.

Now, (having fixed an action-profile $b\in A$) let us study the terms in the sum $\sum_{a\in A}$. Given an action-profile $a\in A$, one has:\
$\bullet$ If $a=b$, which occurs exactly once, then ${\mathbb{P}}(X_{i,a}, X_{i,b})=\beta/\alpha$, and the term $\prod\nolimits_{i\in N}{\mathbb{P}}(X_{i,a} X_{i,b}) - \left(\beta/\alpha\right)^{2n}$ equals $(\beta/\alpha)^n - \left(\beta/\alpha\right)^{2n}$.\
$\bullet$ If for some agent $i$, it holds that $a^{-i}= b^{-i}$ with $a^i\neq b^i$, then a distinct agent $j$ cannot satisfy $a^{-j}= b^{-j}$, because of $a^i\neq b^i$; hence the other agents (other than agent $i$) fall into the case of $a^{-j}\neq b^{-j}$. This occurs exactly $n(\alpha-1)$ times, and then while it holds that ${\mathbb{P}}(X_{i,a}, X_{i,b})=(\beta-1)\beta/\alpha^2$ for agent $i$, for the other agents $j$, it holds that ${\mathbb{P}}(X_{j,a}, X_{j,b})=(\beta/\alpha)^2$. Therefore, the term $\prod\nolimits_{i\in N}{\mathbb{P}}(X_{i,a} X_{i,b}) - \left(\beta/\alpha\right)^{2n}$ equals $((\beta-1)\beta/\alpha^2)(\beta/\alpha)^{2n-2} - \left(\beta/\alpha\right)^{2n}$, that is:\
$$\begin{aligned}
 \prod\nolimits_{i\in N}{\mathbb{P}}(X_{i,a} X_{i,b}) - \left(\beta/\alpha\right)^{2n} &=&  \frac {(\beta-1)\beta^{2n-1}-\beta^{2n}} {\alpha^{2n}}\\ &=& \frac {-\beta^{2n-1}} {\alpha^{2n}} \end{aligned}$$ $\bullet$ In the last case, if for every agent $i$, it holds that $a^{-i}\neq b^{-i}$, then the term cancels.\
To conclude, the variance of the number of Pareto-Nash equilibria is: $$\begin{aligned}
 &&{\text{Var}}\left(Z\right) \\ &=&  \alpha^n \sum_{a\in A} \left(\prod\nolimits_{i\in N}{\mathbb{P}}(X_{i,a} X_{i,b}) \quad-\quad \left(\beta/\alpha\right)^{2n}\right)\label{eq:117}\\ &=&  \alpha^n \left((\beta/\alpha)^n - (\beta/\alpha)^{2n}-n(\alpha-1)\beta^{2n-1}/ \alpha^{2n}\right)\label{eq:118}\\ &=& \beta^n \left( 1 - (\beta/\alpha)^n - n(\alpha-1)\beta^{n-1}/\alpha^{n}\right)\\ &=& \beta^n \left( 1 - \quad(\beta/\alpha)^n(1+n(\alpha-1)/\beta)\quad\right)\\ &\leq & \beta^n  \end{aligned}$$ To finish, since we have an expectation ${\mathbb{E}}[Z]=\beta^n$ and a variance ${\text{Var}}(Z)\leq\beta^n$, a straightforward use of the Bienaymé-Tchebychev inequality concludes that for any given number $\gamma\in(0,1)$, it holds that: $$\begin{aligned}
 {\mathbb{P}}(|Z-\beta^n|\leq \gamma \beta^n) &\geq & 1 - \frac{\beta^n}{\gamma^2 \beta^{2n}}\\ & = & 1 - \frac{1}{\gamma^2 \beta^{n}} \end{aligned}$$

Proofs concerning the properties of the multi-objective coordination ratio
==========================================================================

We show that Definition \[def:MOCR\] satisfies the following. Given ${\mathcal{E}},{\mathcal{F}}\subset{\mathbb{R}^d_{+}}$ and $\bm{r}\in{\mathbb{R}^d_{+}}$: $$\begin{aligned}
\mbox{MO-CR}[{\mathcal{E}},{\mathcal{F}}] 
&\quad\subseteq& 
{\mathbb{R}^d_{+}}\label{eq:ratio:6:bis}\\ 
\mbox{MO-CR}[\{\bm{0}\},{\mathcal{F}}] 
&\quad=& 
\{\bm{0}\}\label{eq:ratio:7:bis}\\ 
\mbox{MO-CR}[\bm{r}\star{\mathcal{E}},{\mathcal{F}}] 
& \quad=& 
\bm{r}\star\mbox{MO-CR}[{\mathcal{E}},{\mathcal{F}}]\label{eq:ratio:8:bis}\\ 
\mbox{MO-CR}[{\mathcal{E}},\bm{r}\star{\mathcal{F}}] 
& \quad=& 
\mbox{MO-CR}[{\mathcal{E}},{\mathcal{F}}]/\bm{r}\label{eq:ratio:9:bis}\\ 
{\mathcal{E}}\subseteq{\mathcal{F}}& \quad\Leftrightarrow& 
\bm{1}\in \mbox{MO-CR}[{\mathcal{E}},{\mathcal{F}}]\label{eq:ratio:10:bis} \end{aligned}$$

Property (\[eq:ratio:6:bis\])By definition, set $\mbox{MO-CR}[{\mathcal{E}},{\mathcal{F}}]$ is a set of vectors in ${\mathbb{R}^d}$.

Property (\[eq:ratio:7:bis\])If ${\mathcal{E}}=\{\bm{0}\}$, then the condition $\rho\in R[{\mathcal{E}},{\mathcal{F}}]$, which is $\forall \bm{y}\in{\mathcal{E}},$ $\quad\exists \bm{z}\in{\mathcal{F}},$ $\bm{y}/\bm{z}{\succsim}\bm{\rho}$, rewrites $\bm{0}{\succsim}\bm{\rho}$. Then ${\mbox{EFF}}[{\mathcal{C}}(\bm{0})]=\{\bm{0}\}$.

Property (\[eq:ratio:8:bis\])We just need to show that $R[\bm{r}\star{\mathcal{E}},{\mathcal{F}}]=\bm{r}\star R[{\mathcal{E}},{\mathcal{F}}]$. Condition $\rho\in R[\bm{r}\star{\mathcal{E}},{\mathcal{F}}]$ rewrites into $\forall \bm{y}\in{\mathcal{E}},\quad\exists \bm{z}\in{\mathcal{F}},\quad \bm{r}\star\bm{y}/\bm{z}{\succsim}\bm{\rho}$. Then one has $\rho\in \bm{r}\star R[{\mathcal{E}},{\mathcal{F}}]$. The converse also holds by a similar argument.

Property (\[eq:ratio:9:bis\])Similarly, one can show that $R[{\mathcal{E}},\bm{r}\star{\mathcal{F}}]=R[{\mathcal{E}},{\mathcal{F}}]/\bm{r}$.

Property (\[eq:ratio:10:bis\])First, note that since ${\mathcal{F}}$ dominates ${\mathcal{E}}$, it is not possible to have $\bm{\rho}{\succ}\bm{1}$ in $R[{\mathcal{E}},{\mathcal{F}}]$. Second, for every $\bm{y}\in{\mathcal{E}}$, one can then take $z=y$, and since $\bm{1}/\bm{1}{\succsim}\bm{1}$, one has $\bm{1}\in R[{\mathcal{E}},{\mathcal{F}}]$. One can also show that if ${\mathcal{E}}\not\subseteq{\mathcal{F}}$ then $\bm{1}\not\in \mbox{MO-CR}[{\mathcal{E}},{\mathcal{F}}]$.

Proof of Theorem 3
==================

The computation of the best equilibria outcomes ${\mbox{EFF}}[{\mathcal{E}}]$ can be achieved by (1) computing the PN equilibria ${\mbox{PN}}\subseteq A$, then (2) computing the equilibria outcomes ${\mathcal{E}}=u({\mbox{PN}})\subseteq {\mathbb{R}}^d$ and finally (3) computing the best equilibria outcomes ${\mbox{EFF}}[{\mathcal{E}}]\subseteq{\mathcal{E}}$ (or the worst ones ${\mbox{WST}}[{\mathcal{E}}]\subseteq{\mathcal{E}}$).

\(1) For this purpose, for every agent $i\in N$ and each adversary action profile $a^{-i}\in A^{-i}$, one has to compute which individual actions give a Pareto-efficient evaluation in $u^i(A^i,a^{-i})$ (which takes time $O(\alpha^2d)$, or if $d=2$ then $O(\alpha\log_2(\alpha))$), in order to mark which action-profiles can be a PN equilibrium from $i$’s point of view. Hence, computing ${\mbox{PN}}$ takes time $O(n \alpha^{n-1} \alpha^2 d)$ (or if $d=2$ $O(n \alpha^{n} \log_2(\alpha) )$). In the worst case, ${\mbox{PN}}=A$ hence $|{\mbox{PN}}|=O(\alpha^n)$.

Then, (2) computing the image through total-utilitarianism ${\mathcal{E}}=u({\mbox{PN}})$ requires for each $a\in {\mbox{PN}}$ the addition of $n$ vectors, in time $nd|{\mbox{PN}}|=O(n\alpha^n d)$.

\(3) Finally, the computation of ${\mbox{EFF}}[{\mathcal{E}}]$ given ${\mathcal{E}}$ takes time $O(|{\mathcal{E}}|^2 d)=O(\alpha^{2n} d)$; and the same holds for ${\mbox{WST}}[{\mathcal{E}}]$. To sum up, the computation of ${\mbox{EFF}}[{\mathcal{E}}]$ (or of ${\mbox{WST}}[{\mathcal{E}}]$) takes time $O(n \alpha^{n+1} d + \alpha^{2n} d)$. If $d=2$, this significantly lowers to $O(n\alpha^n \log_2(\alpha))$, by using a data structure (e.g. an AVL tree) that orders vectors according to the first objective and does comparisons on the second objective.

Proof of Theorem 4
==================

Since the game is symmetric, every configuration $c$ represents an equivalence class in the set of action-profiles $A$; hence, a set of configurations represents a subset of the action-profiles. Therefore, in order to compute the set of Pareto-Nash equilibria ${\mbox{PN}}\subseteq A$, a set of configurations is an acceptable output and even a more compact one. The problem to decide if a given configuration $c$ is a (pure-strategy) Pareto-Nash equilibrium is easy: one only has to test for every action $a^\ast\in A^\ast$ such that[^7] $c(a^\ast)\geq 1$, if that action is a Pareto-efficient individual decision. An individual deviation to another action $b^\ast\in A^\ast$ induces the configuration $c'$ obtained from the configuration $c$ by subtracting 1 from the number $c(a^\ast)$ and adding 1 to the number $c(b^\ast)$ of agents deciding the action $b^\ast$. Therefore, testing if a configuration $c$ is a ${\mbox{PN}}$ equilibrium takes time $O(\alpha^2 d)$. As a consequence, the computation of the set of ${\mbox{PN}}$ equilibria takes times $O(n^\alpha \alpha^2 d)$, that is poly-time $O(L\alpha)$. Also, computing an utilitarian evaluation $u(c)=\sum_{a^\ast\in A^\ast}c(a^\ast)u^{\ast}(a^\ast,c)\in{\mathbb{R}}^d$ requires $O(\alpha)$ multiplications and additions; hence computing the set of equilibria outcomes ${\mathcal{E}}=u({\mbox{PN}})$ (starting from the set ${\mbox{PN}}$ which size is $O(L)$) also takes poly-time $O(L\alpha)$. Since the number of equilibria outcomes is bounded by the number of configurations, it follows that computing the sets of best and worst equilibria ${\mbox{EFF}}[{\mathcal{E}}]$ and ${\mbox{WST}}[{\mathcal{E}}]$ takes time $O(n^{2\alpha} d)$, that is poly-time $O(L^2)$.

Proof of Theorem 5
==================

In order to compute $\text{MO-CR}={\mbox{EFF}}[R[{\mbox{WST}}[{\mathcal{E}}],{\mathcal{F}}]]$, let us study the structure of $\bigcap_{y\in{\mbox{WST}}[{\mathcal{E}}]}\bigcup_{z\in{\mathcal{F}}}{\mathcal{C}}(y/z)$, by restricting a set-algebra to the following objects:

\[def:coneunion\] For set of vectors $X\subseteq{\mathbb{R}^d_{+}}$, Cone-Union ${\mathcal{C}}(X)$ is: $${\mathcal{C}}(X) \quad=\quad\bigcup_{x\in X}{\mathcal{C}}(x) \quad=\quad\{y\in{\mathbb{R}^d_{+}}~~|~~ \exists x\in X, x{\succsim}y\}$$ Let ${\mathcal{C}}$ denote the set of all cone-unions of ${\mathbb{R}^d_{+}}$.

To define an algebra on ${\mathcal{C}}$, one can supply ${\mathcal{C}}$ with $\cup$ and $\cap$.

\[prop:algebra\] \
Given two descriptions of cone-unions $X^1,X^2\subseteq{\mathbb{R}^d_{+}}$, we have: $${\mathcal{C}}(X^1)\cup{\mathcal{C}}(X^2)\quad=\quad{\mathcal{C}}( X^1\cup X^2 )$$ Given two descriptions of cones $x^1,x^2\in{\mathbb{R}^d_{+}}$, we have: $${\mathcal{C}}(x^1)\cap{\mathcal{C}}(x^2)\quad=\quad{\mathcal{C}}(x^1\wedge x^2)$$ where $x^1\wedge x^2\in{\mathbb{R}^d_{+}}$ is: $\forall k\in{{\mathcal{D}}}, (x^1\wedge x^2)_k=\min\{x^1_k,x^2_k\}$.\
Given two descriptions of cone-unions $X^1,X^2\subseteq{\mathbb{R}^d_{+}}$, we have: $$\begin{aligned}
 {\mathcal{C}}(X^1)\cap{\mathcal{C}}(X^2) &=&\left(\cup_{x^1\in X^1}{\mathcal{C}}(x^1)\right)\cap\left(\cup_{x^2\in X^2}{\mathcal{C}}(x^2)\right)\\ &=&\bigcup_{(x^1,x^2)\in X^1\times X^2}{\mathcal{C}}(x^1)\cap{\mathcal{C}}(x^2)\\ &=&\bigcup_{(x^1,x^2)\in X^1\times X^2}{\mathcal{C}}(x^1\wedge x^2)\\ &=&{\mathcal{C}}( X^1\wedge X^2 ) \end{aligned}$$ where $X^1\wedge X^2=\{x^1\wedge x^2~|~x^1\in X^1,~x^2\in X^2\}\subseteq{\mathbb{R}^d_{+}}$.\
Therefore, $({\mathcal{C}},\cup,\cap)$ is stable, and then is a set-algebra.

The three properties derive from set calculus.

The main consequence of Lemma \[prop:algebra\] is that $R[{\mbox{WST}}[{\mathcal{E}}],{\mathcal{F}}]=\cap_{y\in{\mbox{WST}}[{\mathcal{E}}]}\cup_{z\in{\mathcal{F}}}{\mathcal{C}}(y/z)$ is a cone-union. Moreover, one can do the expansion for $\cap_{y\in{\mbox{WST}}[{\mathcal{E}}]}\cup_{z\in{\mathcal{F}}}{\mathcal{C}}(y/z)$ within the cone-unions, using expansions.

\[rk:app:cone\] For a finite set $X\subseteq{\mathbb{R}^d_{+}}$, we have: ${\mathcal{C}}(X)={\mathcal{C}}({\mbox{EFF}}[X])$.

Firstly, we prove ${\mathcal{C}}(X)\subseteq{\mathcal{C}}({\mbox{EFF}}[X])$. If $y\in{\mathcal{C}}(X)$, then there exists $x\in X$ such that $x{\succsim}y$. There are two cases, $x\in{\mbox{EFF}}[X]$ and $x\not\in{\mbox{EFF}}[X]$. If $x\in{\mbox{EFF}}[X]$, then $y\in{\mathcal{C}}({\mbox{EFF}}[X])$, by definition of a cone-union. Otherwise, if $x\not\in{\mbox{EFF}}[X]$, then there exists $z\in X$ such that $z{\succ}x$. And since $X$ is finite, we can find such a $z$ in ${\mbox{EFF}}[X]$, by iteratively taking $z'{\succ}z$ and $z\leftarrow z'$, until $z'\in{\mbox{EFF}}[X]$, which will happen because $X$ is finite and ${\succ}$ is transitive and irreflexive. Hence, there exists $z\in{\mbox{EFF}}[X]$ such that $z{\succ}x{\succsim}y$ and then $z{\succ}y$. Consequently, $y\in{\mathcal{C}}({\mbox{EFF}}[X])$, by definition of a cone-union. Conversely, $Y\subseteq X\Rightarrow {\mathcal{C}}(Y)\subseteq{\mathcal{C}}(X)$ proves ${\mathcal{C}}({\mbox{EFF}}[X])\subseteq{\mathcal{C}}(X)$.

As a consequence of Remark \[rk:app:cone\], for $x\in{\mathbb{R}^d_{+}}$, a simple cone ${\mathcal{C}}(x)$ is fully described by its apex $x$. The main consequence of this remark is that ${\mathcal{C}}(X)$ can be fully described and represented by ${\mbox{EFF}}[X]$. For instance, since $R[{\mbox{WST}}[{\mathcal{E}}],{\mathcal{F}}]$ is a cone-union (thanks to Lemma \[prop:algebra\]), and since $\text{MO-CR}={\mbox{EFF}}[R[{\mbox{WST}}[{\mathcal{E}}],{\mathcal{F}}]]$ (by definition of the MO-CR), then $R[{\mbox{WST}}[{\mathcal{E}}],{\mathcal{F}}]$ is fully represented (as a cone-union) by the MO-CR, which means that $R[{\mbox{WST}}[{\mathcal{E}}],{\mathcal{F}}]={\mathcal{C}}(\text{MO-CR})$.\
Recall that $q=|{\mbox{WST}}[{\mathcal{E}}]|$ and $m=|{\mathcal{F}}|$. In this subsection, we also denote ${\mbox{WST}}[{\mathcal{E}}]=\{y^1,\ldots,y^q\}$ and ${\mathcal{F}}=\{z^1,\ldots,z^m\}$. Let ${\mathcal{A}}_q^m$ denote the set of functions $\pi$ from $\{1,\ldots,q\}$ to $\{1,\ldots,m\}$. (We have: $|{\mathcal{A}}_q^m|=m^q$.)

 \
Given ${\mbox{WST}}[{\mathcal{E}}]=\{y^1,\ldots,y^q\}$ and ${\mathcal{F}}=\{z^1,\ldots,z^m\}$, we have: $$R[{\mbox{WST}}[{\mathcal{E}}],{\mathcal{F}}]=\bigcup_{\pi\in{\mathcal{A}}_q^m}\bigcap_{t=1}^{q} {\mathcal{C}}(y^t / z^{\pi(t)})$$ and therefore: $$\text{MO-CR}[{\mathcal{E}},{\mathcal{F}}]\quad=\quad{\mbox{EFF}}\left[\left\{\bigwedge\nolimits_{t=1}^{q}y^t / z^{\pi(t)}~~|~~\pi\in{\mathcal{A}}_q^m\right\}\right]$$

For the first statement, just think of an expansion. We write down $$R[{\mbox{WST}}[{\mathcal{E}}],{\mathcal{F}}]=\cap_{y\in{\mbox{WST}}[{\mathcal{E}}]}\cup_{z\in{\mathcal{F}}}{\mathcal{C}}(y/z)$$ into the layers just below. There is one layer per $y^t$ in ${\mbox{WST}}[{\mathcal{E}}]=\{y^1,\ldots,y^t,\ldots,y^q\}$: $$\begin{array}{ccccccccccl} & ( & {\mathcal{C}}(\frac{y^1}{z^1}) & \cup & {\mathcal{C}}(\frac{y^1}{z^2}) & \cup & \ldots & \cup & {\mathcal{C}}(\frac{y^1}{z^m})& )&\text{layer 1}\\ \bigcap & ( & {\mathcal{C}}(\frac{y^2}{z^1}) & \cup & {\mathcal{C}}(\frac{y^2}{z^2}) & \cup & \ldots & \cup & {\mathcal{C}}(\frac{y^2}{z^m})& )&\text{layer 2}\\ &&&&&\vdots\\ \bigcap & ( & {\mathcal{C}}(\frac{y^q}{z^1}) & \cup & {\mathcal{C}}(\frac{y^q}{z^2}) & \cup & \ldots & \cup & {\mathcal{C}}(\frac{y^q}{z^m})& )&\text{layer q} \end{array}$$ Imagine the simple cones ${\mathcal{C}}(\frac{y^t}{z^{\pi(t)}})$ as vertices and imagine edges going from each vertex of layer $t$ to each vertex of the next layer $(t+1)$. Let the function $\pi:\{1,\ldots,q\}\rightarrow\{1,\ldots,m\}$ denote a path from layer $1$ to layer $q$, where $\pi(t)$ is the vertex chosen in layer $t$. The expansion into a union outputs as many intersection-terms as paths from the first layer to the last one. Consequently, in the result of the expansion into an union, each term is an intersection $\bigcap_{t=1}^{q} {\mathcal{C}}(y^t / z^{\pi(t)})$. Then one has: $$\begin{aligned}
 R[{\mbox{WST}}[{\mathcal{E}}],{\mathcal{F}}] &=&\bigcup_{\pi\in{\mathcal{A}}_q^m}\bigcap_{t=1}^{q} {\mathcal{C}}(y^t / z^{\pi(t)})\\ &=&\bigcup_{\pi\in{\mathcal{A}}_q^m} {\mathcal{C}}\left(\bigwedge_{t=1}^{q} y^t / z^{\pi(t)}\right)\\ &=&{\mathcal{C}}\left(\left\{\bigwedge\limits_{t=1}^{q}y^t / z^{\pi(t)}~~|~~\pi\in{\mathcal{A}}_q^m\right\}\right) \end{aligned}$$ The second statement results from the first statement, Lemma \[prop:algebra\] and Remark \[rk:app:cone\]. That $R[{\mbox{WST}}[{\mathcal{E}}],{\mathcal{F}}]={\mathcal{C}}(\text{MO-CR})$ and then ${\mbox{EFF}}[R[{\mbox{WST}}[{\mathcal{E}}],{\mathcal{F}}]]=\text{MO-CR}$ (from Remark 1) concludes the proof.

Ultimately, this proves the **correctness** of Algorithm 1 for the computation of MO-CR, given ${\mbox{WST}}[{\mathcal{E}}]=\{y^1,\ldots,y^q\}$ and ${\mathcal{F}}=\{z^1,\ldots,z^m\}$. It consists in the iterative expansion/construction of the intersection $R[{\mbox{WST}}[{\mathcal{E}}],{\mathcal{F}}]$, which can be seen as dynamic programming on the paths of the layer graph. For $k\in\{1,\ldots,q\}$, we denote $D^t$ the description of the cone-union corresponding to the intersection: $${\mathcal{C}}(D^t)=\cap_{l=1}^{t} \cup_{z\in{\mathcal{F}}} {\mathcal{C}}(y^l/z)$$ Recursively, for $t>1$, ${\mathcal{C}}(D^t)={\mathcal{C}}(D^{t-1})~\cap~(\cup_{z\in{\mathcal{F}}}~{\mathcal{C}}(y^{t}/z))$. From Lemma \[prop:algebra\], Remark \[rk:app:cone\] and Corollary 1, in order to construct, we then have to iterate the following: $$D^t={\mbox{EFF}}[\{\rho ~\wedge~ (y^t/z)~~|~~\rho\in D^{t-1},~~z\in{\mathcal{F}}\}]$$ We now proceed with the **time complexity** of Algorithm 1. At first glance, since there are $m^q$ paths in the layer graph, then there are $O(m^q)$ elements in MO-CR. Fortunately, they are much less, because we have:

 \
\[th:mopoa:poly\] Given a MOG and denoting $d=|{{\mathcal{D}}}|$, $q=|{\mbox{WST}}[{\mathcal{E}}]|$ and $m=|{\mathcal{F}}|$, we have: $$|\text{MO-CR}|\leq (qm)^{d-1}$$

Given $\rho\in\text{MO-CR}$, for some $\pi\in{\mathcal{A}}_q^m$, we have $\rho=\bigwedge\nolimits_{t=1}^{q}y^t / z^{\pi(t)}$, and then $\forall k\in{{\mathcal{D}}}, \rho_k=\min_{t=1\ldots q}\{y^t_k / z^{\pi(t)}_k\}$. Therefore, $\rho_k$ is exactly realized by the $k$th component of at least one cone apex $y^t / z^{\pi(t)}$ in the layer graph (that is a vertex in the layer-graph above). Consequently, there are at most as many possible values for the $k$th component of $\rho$, as the number of vertices in the layer graph, that is $qm$. This holds for the $d$ components of $\rho$; hence there are at most $(qm)^d$ vectors in MO-CR. More precisely, by Lemma \[lem:eff\] (below), since MO-CR is an efficient set, then there are at most $(qm)^{d-1}$ vectors in MO-CR.

\[lem:eff\] Let $Y\subseteq{\mathbb{R}^d_{+}}$ be a set of vectors, with at most $M$ values on each component: $$|~{\mbox{EFF}}[Y]~|\leq M^{d-1}$$

For instance, in ${\mathbb{R}}^2_+$, considering the $M\times M$ grid in the plane, there is at most one Pareto-efficient vector per column, hence $|{\mbox{EFF}}[Y]|\leq M$. Think of each vector as having one and $d-1$ components. Fixing these last components, a single-objective optimization problem on the first objective occurs. Hence there is one optimum. Furthermore, there are at most $M^{d-1}$ valuations realized on the $d-1$ other components. If you fix the $d-1$ last components, there is at most one Pareto-efficient vector: it maximizes the first component.

In Algorithm 1, there are $\Theta(q)$ steps. At each step $t$, from Theorem \[th:mopoa:poly\], we know that $|D^{t-1}|\leq (qm)^{d-1}$. Hence, $|\{\rho ~\wedge~ (y^t/z)~~|~~\rho\in D^{t-1},~~z\in{\mathcal{F}}\}|\leq q^{d-1} m^d$, and the computation of the efficient set $D^t$ requires time $O((q^{d-1} m^d)^2 d)$. Ultimately, Algorithm 1 takes $q$ steps and then time $O(q (q^{d-1} m^d)(qm)^{d-1} d)=O((qm)^{2d-1}d)$. If $d=2$, this lowers to $O((q m)^2\log_2(q m))$, by using a data structure (e.g. an AVL tree) that orders vectors according to the first objective and does comparisons on the second objective.

Proof of Lemma 1
================

This proof simply consists in chaining the quantifiers in the definitions, that have been carefully chosen to prove the result.

\(1) First, let us show $R[E,F]\subseteq R[{\mbox{WST}}[{\mathcal{E}}],{\mathcal{F}}]$. Let $\rho'$ be a ratio of $R[E,F]$ and let us show that: $$\forall y\in {\mbox{WST}}[{\mathcal{E}}],~~ \exists z\in {\mathcal{F}},~~ \text{ s.t.: } y{\succsim}\rho'\star z$$ Take $y\in{\mbox{WST}}[{\mathcal{E}}]$. From the first condition, there is a $y'\in E$ such that $y{\succsim}y'$. From MO-CR, there is a $z'$ such that $y'{\succsim}\rho'\star z'$. From the third condition on $z'$, there exists $z\in{\mathcal{F}}$ such that $z'{\succsim}z$. Recap: $y{\succsim}y'{\succsim}\rho'\star z'{\succsim}\rho'\star z$.

\(2) Then, let $\rho$ be a ratio of $R[{\mbox{WST}}[{\mathcal{E}}],{\mathcal{F}}]$, and let us show that$\rho'=(1+\varepsilon_1)^{-1}(1+\varepsilon_2)^{-1}\rho$   is in $R[E,F]$, that is: $$\forall y'\in E,~~ \exists z'\in F,~~ (1+\varepsilon_1) y'{\succsim}(1+\varepsilon_2)^{-1} \rho\star z'$$ Take an element $y'$ of $E$. From the second condition, there is $y\in{\mbox{WST}}[{\mathcal{E}}]$ such that $(1+\varepsilon_1)y'{\succsim}y$. From MO-CR, there is $z\in{\mathcal{F}}$ such that $y{\succsim}\rho\star z$. From the fourth condition on $z$, there exists $z'\in F$ s.t. $z{\succsim}(1+\varepsilon_2)^{-1} z'$. Recap: $(1+\varepsilon_1)y'{\succsim}y{\succsim}\rho\star z{\succsim}(1+\varepsilon_2)^{-1} \rho\star z'$.

Proof of Theorem 6
==================

Applying Algorithm 1 on $E$ and $F$ outputs an $((1+\varepsilon_1)(1+\varepsilon_2))$-covering of $R({\mbox{WST}}[{\mathcal{E}}],{\mathcal{F}})$. Moreover, since we have $|E|=O((1/\varepsilon_1)^{d-1})$ and $|F|=O((1/\varepsilon_2)^{d-1})$, Algorithm 1 takes time $O\left(d/(\varepsilon_1\varepsilon_2)^{(d-1)(2d-1)}\right)$.

Experiments
===========

Experiments were conducted to assess the practicality of our polynomial time and approximation algorithms. We used C++STL on a Linux laptop equipped with CPUs at 1.40Ghz. We fixed $|A^i|=2$ actions per agent. For each parameter-values, we averaged the measures over 5 random instances[^8]. The evaluations $u^{i}_k(a^{\mathcal{N}(i)})$ are drawn uniformly and independently in $|[1,16]|$. In Table 1 (for MOGs) we have $\mathcal{N}(i)=N$. In Table 2 (for MO graphical games), the games were drawn on grid graphs with dimensions $n=n_1\times n_2$, in order to experiment various treewidths[^9]. We chose $n_2\in\{1,2,3\}$ for the interaction-graph’s width, which corresponds to the treewidths $\mathcal{T}\in\{2,4,6\}$.

Computational measures on MO normal forms
-----------------------------------------

In Table \[tab:mog\], we experiment Algorithm 1 on MO games. Table 1’s notations are: $d$ for the number of objectives; $n$ for the number of agents; T(P1) for the cpu-time (seconds) of Phase 1: computing ${\mbox{WST}}[{\mathcal{E}}]$ and ${\mathcal{F}}$; $m=|{\mathcal{F}}|$ and $q=|{\mbox{WST}}[{\mathcal{E}}]|$; T(P2) for the cpu-time (seconds) of Phase 2: computing MO-CR given ${\mbox{WST}}[{\mathcal{E}}]$ and ${\mathcal{F}}$; and finally, (in order to assess the practicality of the algorithm’s output) the size of the resulting MO-CR.

$\begin{array}{c|ccc|ccc|ccc}                                                                               &           \multicolumn{3}{c|}{d=2}            &           \multicolumn{3}{c|}{d=3}            &           \multicolumn{3}{c}{d=4}         \\ \hline                                                                            n  &   4   &   8   &   12  &   4   &   8   &   12  &   4   &   8   &   12  \\ \hline                                                                            T(P1)  &   0.00    &   0.08    &   2.40    &   0.00    &   0.07    &   2.45    &   0.00    &   0.08    &   2.44    \\ m    &   4.2 &   5.6 &   8.2 &   5.4 &   17.8    &   41.2    &   7.2 &   36.4    &   105.8   \\ q    &   2.2 &   4   &   5.8 &   4.4 &   9.8 &   30.2    &   8   &   37.8    &   82.6    \\ \hline T(P2) &   0.00    &   0.00    &   0.00    &   0.00    &   0.01    &   0.20    &   0.00    &   0.48    &   30.85   \\ \#\text{MO-CR}   &   3.4 &   4.6 &   6   &   3.2 &   22.8    &   31.8    &   13.6    &   44.4    &   154.8   \\ \hline                                                                            
\end{array} $\

*Observations.* Recall that the normal form is a representation of size $\Theta(n\alpha^n d)$. For instance, for $d=3$, Phase 1, and $n=4,8,12$, the instance to read is made of $192$, $6144$ and $147456$ scalars. The cpu-time cost of Phase 1 depends directly on the size of this input. For $d\leq 3$, Algorithm 1 costs nothing, compared to Phase 1. For $d\geq 4$, we begin to perceive the explosion of Algorithm 1 (Phase 2), while $m,q\simeq 100$. This indicates a practical intractability for $d\geq 4$. Recall that the cost of Algorithm 1 (Phase 2) for $d=4$ is $O((mq)^7)$.

Computational measures on MO graphical games
--------------------------------------------

In Table 2, we experiment the approximation scheme on MO graphical games. After Phase 1, we take smaller representations of ${\mbox{WST}}[{\mathcal{E}}]$ and ${\mathcal{F}}$: a $(1+\varepsilon_1)$-under-covering of ${\mbox{WST}}[{\mathcal{E}}]$ with $\varepsilon_1=6.5\%$, and a $(1+\varepsilon_2)$-stick-covering of ${\mathcal{F}}$ with $\varepsilon_2=3.5\%$, all in order to ensure a $(1+\varepsilon)$-covering of MO-CR, with $\varepsilon\simeq 6.5\%+3.5\%=10\%$ (thanks to Theorem 6). Table 2’s notations are the same as Table 1’s, and we add: $n_2$ for the width of the interaction graph; $m_{\varepsilon}$ for the resulting size (after a proper rounding) of the representation of ${\mathcal{F}}$; and $q_{\varepsilon}$ for the resulting size (after a proper rounding) of the representation of ${\mbox{WST}}[{\mathcal{E}}]$.

$\begin{array}{c|ccc|ccc|ccc}                                                                               &   \multicolumn{9}{c}{d=2}                                                                 \\
 \hline                                                                             &   \multicolumn{3}{c|}{n_2=1}                  &   \multicolumn{3}{c|}{n_2=2}                  &   \multicolumn{3}{c}{n_2=3}                   \\
  \hline                                                                             n  &   60  &   120 &   180 &   60  &   120 &   180 &   60  &   120 &   180 \\
   \hline                                                                            T(P1)  &   0   &   3   &   13  &   1   &   11  &   43  &   4   &   37  &   159 \\ m    &   92  &   212 &   347 &   76  &   186 &   316 &   65  &   174 &   300 \\ q    &   47  &   120 &   217 &   49  &   134 &   222 &   46  &   134 &   228 \\ \hline                                                                            m_{\varepsilon}    &   5   &   5   &   4.6 &   5.6 &   5   &   4.4 &   4.6 &   4.8 &   5   \\ q_{\varepsilon}  &   7.4 &   7.4 &   7   &   7.6 &   7.4 &   7.2 &   7   &   7.4 &   7.6 \\ \hline                                                                            T(P2)  &   0.00    &   0.00    &   0.00    &   0.00    &   0.00    &   0.00    &   0.00    &   0.00    &   0.00    \\ \#\text{MO-CR}   &   3.8 &   2.6 &   3.6 &   3.4 &   3.4 &   3   &   3.6 &   2.4 &   3   \\ \hline                                                                            \multicolumn{10}{c}{}\\                                                                                &   \multicolumn{9}{c}{d=3}                                                                 \\ \hline                                                                               &   \multicolumn{3}{c|}{n_2=1}                  &   \multicolumn{3}{c|}{n_2=2}                  &   \multicolumn{3}{c}{n_2=3}                   \\ \hline                                                                            n  &   12  &   24  &   36  &   12  &   24  &   36  &   12  &   24  &   36  \\ \hline                                                                            T(P1)  &   0   &   1   &   8   &   0   &   2   &   15  &   0   &   4   &   40  \\ m    &   42  &   263 &   777 &   44  &   249 &   596 &   49  &   190 &   474 \\ q    &   27  &   236 &   645 &   31  &   143 &   506 &   38  &   159 &   448 \\ \hline                                                                            m_{\varepsilon}    &   15.6    &   19.8    &   22.8    &   16.8    &   27.4    &   26.6    &   17.8    &   22  &   25.2    \\ q_{\varepsilon}  &   24.8    &   45.8    &   53.2    &   26.2    &   59.2    &   63  &   27.8    &   45.2    &   53  \\ \hline                                                                            T(P2)  &   0.01    &   0.02    &   0.03    &   0.01    &   0.05    &   0.06    &   0.01    &   0.03    &   0.06    \\ \#\text{MO-CR}   &   15.6    &   13.4    &   12.8    &   8.8 &   11.8    &   14.4    &   12.4    &   15  &   12.8    \\ \hline                                                                            
\end{array}$\

*Observations.* As seen in Table 1 when $m,q\simeq 100$, computing MO-CR would be experimentally intractable, if done directly on ${\mbox{WST}}[{\mathcal{E}}]$ and ${\mathcal{F}}$. Fortunately, thanks to the approximation scheme, Algorithm 1 costs almost nothing on the smaller representations of ${\mbox{WST}}[{\mathcal{E}}]$ and ${\mathcal{F}}$, compared to computation of Phase 1.

A raw example of MO-CR
----------------------

![MO-CR of one MOG with $n=7$ agents, $d=2$ objectives, $\alpha=3$ actions-per-agent, and independent evaluations drawn uniformly in $\{1,\ldots,100\}$](exampleXP.pdf)

The white part corresponds to the set of guaranteed ratios of efficiency\
$\rho\in R[{\mathcal{E}},{\mathcal{F}}]\cap [0,1]^d$ and the dark-blue part to $\rho\notin R[{\mathcal{E}},{\mathcal{F}}]$. Recall that if $\rho\in R[{\mathcal{E}},{\mathcal{F}}]$, then $\rho$ guarantees that for each equilibrium-outcome $y\in{\mathcal{E}}$, there exists an efficient-outcome $z^{(y)}$ such that $y {\succsim}\rho\star z^{(y)}$. Conversely, if $\rho\notin R[{\mathcal{E}},{\mathcal{F}}]$, then there exists an *in-efficient* equilibrium $y\in{\mathcal{E}}$, that is: such that whatever $z\in{\mathcal{F}}$, the guarantee $y {\succsim}\rho\star z^{(y)}$ does *not* hold. In other words, for each $\rho\in R[{\mathcal{E}},{\mathcal{F}}]$, it holds that each equilibrium has at least $\rho$ times some efficiency.

[^1]: Tobacco consumers are free to value and choose cigarettes how it pleases them. However, is value the same when they inhale, as when they die suffocating?

[^2]: It is a backtrack from the subjective theory of value, which typically aggregates values on each objective/commodity into a single scalar by using an utility function.

[^3]: For the proofs, see the long paper:

[^4]: In the single-objective case, Pareto-Nash and Nash equilibria coincide.

[^5]: In a finite multi-objective game, sets $N$, $\{A^{i}\}_{i\in N}$ and ${{\mathcal{D}}}$ are finite.

[^6]: To enumerate the number of ways to distribute number $n$ of symmetric agents into $\alpha$ parts, one enumerates the ways to choose $\alpha-1$ “separators” in $n+\alpha-1$ elements.

[^7]: That is such that the action $a^\ast$ is decided by someone.

[^8]: Though only 5 random instances does not sound like much, the measures of cpu-time were already stable

[^9]: For a formal definition of the treewidth, the reader may refer to [@dechter1989tree; @jensen1994influence] or [@ismaili2016computational].
