<p>Consider a game:</p>
<ul>
<li>Set of Players <span class="math-container">$= \{1,2\}$</span></li>
<li>Action Sets of the players: <span class="math-container">$\triangle_1\subseteq\mathbb{R}^n$</span> and <span class="math-container">$\triangle_2\subseteq\mathbb{R}^m$</span>. For Eg: In case of Prisoner's Dilemma, <span class="math-container">$\triangle_1=\{(p,1-p)|0\leq p\leq 1\}$</span>, where <span class="math-container">$p$</span> is the probability of co-operation.</li>
<li>Payoffs: <span class="math-container">$u_i:\triangle_1\times \triangle_2\rightarrow\mathbb{R}$</span> where <span class="math-container">$i\in\{1,2\}$</span></li>
</ul>
<p>We assume <span class="math-container">$u_i$</span>s are continuous.</p>
<p><strong>Definition 1.</strong> We can define an outcome <span class="math-container">$(p,q)\in \triangle_1\times \triangle_2$</span> to be <span class="math-container">$\epsilon -$</span> approximate Pareto efficient if there exists a Pareto efficient outcome <span class="math-container">$(p',q')$</span> in its <span class="math-container">$\epsilon-$</span> neighbourhood i.e. <span class="math-container">$(p',q')\in \triangle_1\times \triangle_2 \cap \mathcal{N}_{\epsilon}((p,q))$</span>, where <span class="math-container">$\mathcal{N}_{\epsilon}((p,q))$</span> is the <span class="math-container">$\epsilon-$</span> neighbourhood of <span class="math-container">$(p,q)$</span>.</p>
<p>Alternatively,</p>
<p><strong>Definition 2.</strong> We can define an outcome <span class="math-container">$(p,q)\in \triangle_1\times \triangle_2$</span> to be <span class="math-container">$\delta -$</span> approximate Pareto efficient if <span class="math-container">$\delta=\inf \{d((p,q),(p',q'))|(p',q')\in \text{Set of Pareto efficient Outcomes}\}$</span>, where <span class="math-container">$d$</span> is a metric on <span class="math-container">$\triangle_1\times \triangle_2$</span> and the Set of Pareto efficient Outcomes <span class="math-container">$\neq\emptyset$</span>.</p>
<p>You can refine the definition(s) to suit your needs.</p>

CC BY-SA 4.0
2023-06-01T09:08:32.873Z
Sounds good, thanks! Is there any reference where these or similar definitions are used?
Erel Segal-Halevi
CC BY-SA 4.0
2023-06-01T09:17:31.760Z
No, I don't think so, and if there are some, I am not aware of it. Let me know if you want to discuss these further; I'll be happy to discuss them.
Amit
CC BY-SA 4.0
2023-06-01T15:05:11.463Z
So, intuitively, an outcome is approximately-Pareto-optimal if it is near a Pareto-optimal outcome. What do you think of the following alternative definition: "an outcome is approximately-Pareto-optimal if it is not Pareto-dominated by a faraway outcome". Formally: "an outcome $(p,q)$ is $\epsilon$-Pareto-optimal if there is no outcome outside its $\epsilon$-neighborhood which Pareto-dominates $(p,q)$." Is it stronger/weaker than your definition?
Erel Segal-Halevi
CC BY-SA 4.0
2023-06-02T02:25:07.780Z
Yes, that's right. An outcome is approximately-Pareto-optimal if it is near a Pareto-optimal outcome and continuity of $u_i$s guarantees that.
Amit
CC BY-SA 4.0
2023-06-02T02:34:12.327Z
For comparing the two definitions, let me call them: Def - old: An outcome $(p,q)$ is $\epsilon-$Pareto-optimal if there is exists a Pareto optimal allocation in its $\epsilon-$ neighbourhood. Def - new: An outcome $(p,q)$ is $\epsilon-$Pareto-optimal if there is no outcome outside its $\epsilon-$ neighbourhood which Pareto-dominates $(p,q)$.
Amit
CC BY-SA 4.0
2023-06-02T02:43:08.783Z
Consider a single player game with $u:\mathbb{R}\rightarrow\mathbb{R}$ defined as $u(x)=-|x-10|$. There is only one Pareto optimal outcome in this game which is $x=10$. Now $8$ is $\epsilon-$ Pareto optimal according to the old definition for all $\epsilon>2$, but $8$ is $\epsilon-$ Pareto optimal according to the new definition for all $\epsilon \geq 4$.
Amit
CC BY-SA 4.0
2023-06-02T02:52:46.340Z
Consider another example of a single player game with $u:\mathbb{R}\rightarrow\mathbb{R}$ defined as $u(x)=\max(\min(1,0.5-x),\frac{1}{1+e^{-x}})$. There are infinitely-many Pareto optimal outcomes in this game which is represented by the set $\{x\in\mathbb{R}|x\leq -0.5\}$. Now $0$ is $\epsilon-$ Pareto optimal according to the old definition for all $\epsilon>0.5$, but $0$ is not $\epsilon-$ Pareto optimal according to the new definition for any $\epsilon>0$.
Amit
CC BY-SA 4.0
2023-06-02T10:42:46.590Z
So the old definition does not imply the new one. Does the new definition imply the old one?
Erel Segal-Halevi
CC BY-SA 4.0
2023-06-02T11:58:20.783Z
No. Consider another example of a single player game with $u: (0,10)\rightarrow \mathbb{R}$ defined as $u(x)=x$. In this game, no Pareto optimal outcome exist. Therefore, no outcome is $\epsilon-$ Pareto optimal according to the old definition for any $\epsilon > 0$. However, each of the outcomes $x\in(0,10)$ is $\epsilon-$ Pareto optimal according to the new definition for any $\epsilon \geq 10-x$.
Amit
CC BY-SA 4.0
2023-06-02T12:01:59.780Z
OK, this is because the domain of $u$ is not compact. What if we consider only compact domains?
Erel Segal-Halevi
CC BY-SA 4.0
2023-06-02T12:50:19.720Z
Then in a finite player environment with everyone having a compact action set and continuous $u_i$, the Pareto optimal outcome exist, so every outcome will always be $\epsilon-$ Pareto optimal for some according to the the old definition. Also every allocation will be $\epsilon-$ Pareto optimal for some $\epsilon > 0$ according to the the new definition because the domain is compact and therefore bounded, so an open neighbourhood of $\epsilon > 0$ large enough will cover the whole space and the condition for the new definition will hold trivially.
Amit
CC BY-SA 4.0
2023-06-02T12:55:37.593Z
I think a plausible question in this environment where we have $u$ continuous with compact domain could be to compare these two sets for each outcome $x$, $E_O(x) = \{\epsilon \in \mathbb{R}_{++}|x \text{ is }  \epsilon-\text{Pareto optimal according to the old definition}\}$ and $E_N(x) = \{\epsilon \in \mathbb{R}_{++}|x \text{ is }  \epsilon-\text{Pareto optimal according to the new definition}\}$
Amit
CC BY-SA 4.0
2023-06-02T15:53:17.110Z
Yes, this makes sense. I will think about it.
Erel Segal-Halevi
CC BY-SA 4.0
2023-06-04T08:12:31.473Z
*Claim.* If the space of outcomes is compact and the utilities are continuous, then for every $\epsilon>0$, any $\epsilon$-optimal outcome by the new definition is also $\epsilon$-optimal by the old definition. *Proof.* Let $(p,q)$ be $\epsilon$-optimal outcome by the new definition. If it is Pareto-optimal, then it is clearly $\epsilon$-optimal by the old definition, so we are done. Otherwise, -->
Erel Segal-Halevi
CC BY-SA 4.0
2023-06-04T08:14:19.783Z
--> Otherwise, let $(p',q')$ be an outcome that maximizes the sum of utilities, subject to the constraint that each agent's utility is at least as high as in $(p,q)$. So $(p',q')$ is Pareto-optimal, and it dominates $(p,q)$. By the new definition, $(p',q')$ cannot be outside the $\epsilon$-neighborhood of $(p,q)$ - so it must be inside this neighborhood. Therefore, $(p,q)$ is $\epsilon$-optimal by the odl definition.
Erel Segal-Halevi
CC BY-SA 4.0
2023-06-04T16:14:47.743Z
Looks neat. Such a $(p',q')$ exists because sum of utilities is continuous, and the constraint set will be a closed subset of a compact set, and hence it is also compact. So that means for each outcome $x$, it is the case that $E_N(x)\subseteq E_O(x)$.
Amit
CC BY-SA 4.0
2023-05-31T18:30:30.553Z
2023-06-01T08:40:54.123Z
2023-06-01T08:40:54.123Z
Amit
<p>Pareto-efficiency is a very important property, but in some cases it cannot be attained (for example, when agents play a game such as the Prisonner's Dilemma). In such cases, it can be useful to measure how far the outcome is from being Pareto-efficient.</p>
<p>A simple measure of approximate Pareto-efficiency (which I found e.g. <a href="https://link.springer.com/chapter/10.1007/978-3-319-71924-5_18" rel="nofollow noreferrer">here</a> and <a href="https://link.springer.com/chapter/10.1007/978-3-642-16170-4_7" rel="nofollow noreferrer">here</a>) uses a multiplicative factor: an outcome is <span class="math-container">$r$</span>-approximately-efficient if there is no alternate outcome in which each agent’s utility increases by a factor of at least <span class="math-container">$r$</span>.
However, this measure assumes that agents have cardinal utility functions. In economics, it is usually assumed that agents' utility functions are just representations of preference relations. In particular, applying a monotone transformation to a utility function leads to a different function that represents the same preferences. If we apply a monotone transformation to a utility function (even a simple one such as adding or subtracting 1), the multiplicative approximation ratio changes.</p>
<p>MY QUESTION: what is a notion of approximate Pareto-efficiency, which is meaningful even when agents have ordinal preferences?</p>

CC BY-SA 4.0
2023-05-31T17:08:59.943Z
I doubt that there is a useful context-independent generalization. For an approach that uses the structure of commodity spaces, take a look at Debreu's 1951 paper "The Coefficient of Resource Utilization."
Michael Greinecker
<theory><pareto-efficiency>
Approximate Pareto efficiency with ordinal preferences
Erel Segal-Halevi
# Approximate Pareto efficiency with ordinal preferences

(Asked by: username_0 on 2023-05-31)

Pareto-efficiency is a very important property, but in some cases it cannot be attained (for example, when agents play a game such as the Prisonner's Dilemma). In such cases, it can be useful to measure how far the outcome is from being Pareto-efficient.

A simple measure of approximate Pareto-efficiency (which I found e.g. [here](https://link.springer.com/chapter/10.1007/978-3-319-71924-5_18) and [here](https://link.springer.com/chapter/10.1007/978-3-642-16170-4_7)) uses a multiplicative factor: an outcome is $r$-approximately-efficient if there is no alternate outcome in which each agent’s utility increases by a factor of at least $r$.
However, this measure assumes that agents have cardinal utility functions. In economics, it is usually assumed that agents' utility functions are just representations of preference relations. In particular, applying a monotone transformation to a utility function leads to a different function that represents the same preferences. If we apply a monotone transformation to a utility function (even a simple one such as adding or subtracting 1), the multiplicative approximation ratio changes.

MY QUESTION: what is a notion of approximate Pareto-efficiency, which is meaningful even when agents have ordinal preferences?

**Tags:** theory, pareto-efficiency
> **Comments:**
> **username_1**: I doubt that there is a useful context-independent generalization. For an approach that uses the structure of commodity spaces, take a look at Debreu's 1951 paper "The Coefficient of Resource Utilization."  

---

## 1 answers

### Answer by username_2 on 2023-05-31. Score: 4 | Accepted answer

Consider a game:

* Set of Players $= \{1,2\}$
* Action Sets of the players: $\triangle\_1\subseteq\mathbb{R}^n$ and $\triangle\_2\subseteq\mathbb{R}^m$. For Eg: In case of Prisoner's Dilemma, $\triangle\_1=\{(p,1-p)|0\leq p\leq 1\}$, where $p$ is the probability of co-operation.
* Payoffs: $u\_i:\triangle\_1\times \triangle\_2\rightarrow\mathbb{R}$ where $i\in\{1,2\}$

We assume $u\_i$s are continuous.

**Definition 1.** We can define an outcome $(p,q)\in \triangle\_1\times \triangle\_2$ to be $\epsilon -$ approximate Pareto efficient if there exists a Pareto efficient outcome $(p',q')$ in its $\epsilon-$ neighbourhood i.e. $(p',q')\in \triangle\_1\times \triangle\_2 \cap \mathcal{N}\_{\epsilon}((p,q))$, where $\mathcal{N}\_{\epsilon}((p,q))$ is the $\epsilon-$ neighbourhood of $(p,q)$.

Alternatively,

**Definition 2.** We can define an outcome $(p,q)\in \triangle\_1\times \triangle\_2$ to be $\delta -$ approximate Pareto efficient if $\delta=\inf \{d((p,q),(p',q'))|(p',q')\in \text{Set of Pareto efficient Outcomes}\}$, where $d$ is a metric on $\triangle\_1\times \triangle\_2$ and the Set of Pareto efficient Outcomes $\neq\emptyset$.

You can refine the definition(s) to suit your needs.

> **Comments:**
> **username_0**: Sounds good, thanks! Is there any reference where these or similar definitions are used?  
> **username_2**: No, I don't think so, and if there are some, I am not aware of it. Let me know if you want to discuss these further; I'll be happy to discuss them.  
> **username_0**: So, intuitively, an outcome is approximately-Pareto-optimal if it is near a Pareto-optimal outcome. What do you think of the following alternative definition: "an outcome is approximately-Pareto-optimal if it is not Pareto-dominated by a faraway outcome". Formally: "an outcome $(p,q)$ is $\epsilon$-Pareto-optimal if there is no outcome outside its $\epsilon$-neighborhood which Pareto-dominates $(p,q)$." Is it stronger/weaker than your definition?  
> **username_2**: Yes, that's right. An outcome is approximately-Pareto-optimal if it is near a Pareto-optimal outcome and continuity of $u_i$s guarantees that.  
> **username_2**: For comparing the two definitions, let me call them: Def - old: An outcome $(p,q)$ is $\epsilon-$Pareto-optimal if there is exists a Pareto optimal allocation in its $\epsilon-$ neighbourhood. Def - new: An outcome $(p,q)$ is $\epsilon-$Pareto-optimal if there is no outcome outside its $\epsilon-$ neighbourhood which Pareto-dominates $(p,q)$.  
> **username_2**: Consider a single player game with $u:\mathbb{R}\rightarrow\mathbb{R}$ defined as $u(x)=-|x-10|$. There is only one Pareto optimal outcome in this game which is $x=10$. Now $8$ is $\epsilon-$ Pareto optimal according to the old definition for all $\epsilon>2$, but $8$ is $\epsilon-$ Pareto optimal according to the new definition for all $\epsilon \geq 4$.  
> **username_2**: Consider another example of a single player game with $u:\mathbb{R}\rightarrow\mathbb{R}$ defined as $u(x)=\max(\min(1,0.5-x),\frac{1}{1+e^{-x}})$. There are infinitely-many Pareto optimal outcomes in this game which is represented by the set $\{x\in\mathbb{R}|x\leq -0.5\}$. Now $0$ is $\epsilon-$ Pareto optimal according to the old definition for all $\epsilon>0.5$, but $0$ is not $\epsilon-$ Pareto optimal according to the new definition for any $\epsilon>0$.  
> **username_0**: So the old definition does not imply the new one. Does the new definition imply the old one?  
> **username_2**: No. Consider another example of a single player game with $u: (0,10)\rightarrow \mathbb{R}$ defined as $u(x)=x$. In this game, no Pareto optimal outcome exist. Therefore, no outcome is $\epsilon-$ Pareto optimal according to the old definition for any $\epsilon > 0$. However, each of the outcomes $x\in(0,10)$ is $\epsilon-$ Pareto optimal according to the new definition for any $\epsilon \geq 10-x$.  
> **username_0**: OK, this is because the domain of $u$ is not compact. What if we consider only compact domains?  
> **username_2**: Then in a finite player environment with everyone having a compact action set and continuous $u_i$, the Pareto optimal outcome exist, so every outcome will always be $\epsilon-$ Pareto optimal for some according to the the old definition. Also every allocation will be $\epsilon-$ Pareto optimal for some $\epsilon > 0$ according to the the new definition because the domain is compact and therefore bounded, so an open neighbourhood of $\epsilon > 0$ large enough will cover the whole space and the condition for the new definition will hold trivially.  
> **username_2**: I think a plausible question in this environment where we have $u$ continuous with compact domain could be to compare these two sets for each outcome $x$, $E_O(x) = \{\epsilon \in \mathbb{R}_{++}|x \text{ is }  \epsilon-\text{Pareto optimal according to the old definition}\}$ and $E_N(x) = \{\epsilon \in \mathbb{R}_{++}|x \text{ is }  \epsilon-\text{Pareto optimal according to the new definition}\}$  
> **username_0**: Yes, this makes sense. I will think about it.  
> **username_0**: *Claim.* If the space of outcomes is compact and the utilities are continuous, then for every $\epsilon>0$, any $\epsilon$-optimal outcome by the new definition is also $\epsilon$-optimal by the old definition. *Proof.* Let $(p,q)$ be $\epsilon$-optimal outcome by the new definition. If it is Pareto-optimal, then it is clearly $\epsilon$-optimal by the old definition, so we are done. Otherwise, -->  
> **username_0**: --> Otherwise, let $(p',q')$ be an outcome that maximizes the sum of utilities, subject to the constraint that each agent's utility is at least as high as in $(p,q)$. So $(p',q')$ is Pareto-optimal, and it dominates $(p,q)$. By the new definition, $(p',q')$ cannot be outside the $\epsilon$-neighborhood of $(p,q)$ - so it must be inside this neighborhood. Therefore, $(p,q)$ is $\epsilon$-optimal by the odl definition.  
> **username_2**: Looks neat. Such a $(p',q')$ exists because sum of utilities is continuous, and the constraint set will be a closed subset of a compact set, and hence it is also compact. So that means for each outcome $x$, it is the case that $E_N(x)\subseteq E_O(x)$.  

---

