<p>I have started studying the Pareto efficiency notion in Game theory. The definition I am familiar with is this:</p>

<p>Strategy profile <span class="math-container">$\mathbf{s}$</span> Pareto dominates strategy <span class="math-container">$\mathbf{s}'$</span> if for all <span class="math-container">$i\in\mathcal{N}$</span>, <span class="math-container">$u_i(\mathbf{s})\geq u_i(\mathbf{s}')$</span>, and there exists some <span class="math-container">$j\in\mathcal{N}$</span> for which <span class="math-container">$u_j(\mathbf{s})&gt;u_j(\mathbf{s}')$</span>. Strategy profile <span class="math-container">$\mathbf{s}$</span> is Pareto optimal, or strictly Pareto efficient, if there does not exist another strategy profile <span class="math-container">$\mathbf{s}'\in S$</span> that Pareto dominates <span class="math-container">$\mathbf{s}$</span>.</p>

<p>I am interested in finite normal form games, for example, the <span class="math-container">$n$</span>-player Prisoner's dilemma. Clearly, for <span class="math-container">$n=2$</span> we have three Pareto outcomes and it's not too difficult to derive them.</p>

<p>But my concern is with a large number of players and non-constant utilities, how do we check the Pareto efficiency outcomes?</p>

<p>Is there a better, more efficient way to compute the efficiency of different outcomes of a game? Maybe the price of anarchy? I am not sure.</p>

<p>I'd appreciate any help or hint. Thank you</p>

CC BY-SA 4.0
2019-02-14T03:57:45.460Z
Do you mean to find the entire set of Pareto efficient outcomes using an algorithm?
Herr K.
CC BY-SA 4.0
2019-02-14T18:01:31.293Z
@HerrK. Yes. An algorithm that will work for an $n$-player Prisoner's dilemma game, where $n\geq 2$.
johnny09
CC BY-SA 4.0
2019-02-14T19:35:49.790Z
The Pareto set of *payoff profiles* is the "northeast" (in the 2-dimensional sense) boundary of the convex hull of all possible payoff profiles. Thus you should in principle be able to use a [convex hull algorithm](https://en.wikipedia.org/wiki/Convex_hull_algorithms) to map out such a set. But how exactly this can be done is way out of my league, as I'm not a computer scientist. You'd probably have better luck asking on https://stackoverflow.com/ or https://cs.stackexchange.com/
Herr K.
CC BY-SA 4.0
2019-02-15T05:35:52.397Z
@HerrK.Do you know any reference for this type of thing? Textbook or paper. I am more interested in the theoretical aspect.
johnny09
CC BY-SA 4.0
2019-02-15T17:59:41.633Z
What do you mean by "this type of thing"?
Herr K.
CC BY-SA 4.0
2019-02-15T23:24:29.120Z
@HerrK.Sorry, I meant a reference on how to theoretically/analytically derive the Pareto set of payoff profiles for the $n$-player prisoner's dilemma.
johnny09
CC BY-SA 4.0
2019-02-15T23:56:49.563Z
I can't think of any such references (especially for n-player PD) at the moment. But the Wikipedia article on Pareto efficiency does have a relevant section that you might find useful: https://en.wikipedia.org/wiki/Pareto_efficiency#Use_in_engineering_and_economics
Herr K.
<game-theory><pareto-efficiency>
Pareto Efficiency Outcomes in Games
johnny09
# Pareto Efficiency Outcomes in Games

(Asked by: username_0 on 2019-02-13)

I have started studying the Pareto efficiency notion in Game theory. The definition I am familiar with is this:

Strategy profile $\mathbf{s}$ Pareto dominates strategy $\mathbf{s}'$ if for all $i\in\mathcal{N}$, $u\_i(\mathbf{s})\geq u\_i(\mathbf{s}')$, and there exists some $j\in\mathcal{N}$ for which $u\_j(\mathbf{s})>u\_j(\mathbf{s}')$. Strategy profile $\mathbf{s}$ is Pareto optimal, or strictly Pareto efficient, if there does not exist another strategy profile $\mathbf{s}'\in S$ that Pareto dominates $\mathbf{s}$.

I am interested in finite normal form games, for example, the $n$-player Prisoner's dilemma. Clearly, for $n=2$ we have three Pareto outcomes and it's not too difficult to derive them.

But my concern is with a large number of players and non-constant utilities, how do we check the Pareto efficiency outcomes?

Is there a better, more efficient way to compute the efficiency of different outcomes of a game? Maybe the price of anarchy? I am not sure.

I'd appreciate any help or hint. Thank you

**Tags:** game-theory, pareto-efficiency
> **Comments:**
> **username_1**: Do you mean to find the entire set of Pareto efficient outcomes using an algorithm?  
> **username_0**: @HerrK. Yes. An algorithm that will work for an $n$-player Prisoner's dilemma game, where $n\geq 2$.  
> **username_1**: The Pareto set of *payoff profiles* is the "northeast" (in the 2-dimensional sense) boundary of the convex hull of all possible payoff profiles. Thus you should in principle be able to use a [convex hull algorithm](https://en.wikipedia.org/wiki/Convex_hull_algorithms) to map out such a set. But how exactly this can be done is way out of my league, as I'm not a computer scientist. You'd probably have better luck asking on https://stackoverflow.com/ or https://cs.stackexchange.com/  
> **username_0**: @HerrK.Do you know any reference for this type of thing? Textbook or paper. I am more interested in the theoretical aspect.  
> **username_1**: What do you mean by "this type of thing"?  
> **username_0**: @HerrK.Sorry, I meant a reference on how to theoretically/analytically derive the Pareto set of payoff profiles for the $n$-player prisoner's dilemma.  
> **username_1**: I can't think of any such references (especially for n-player PD) at the moment. But the Wikipedia article on Pareto efficiency does have a relevant section that you might find useful: https://en.wikipedia.org/wiki/Pareto_efficiency#Use_in_engineering_and_economics  

---

## 0 answers

