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

  • 1
    $\begingroup$ Do you mean to find the entire set of Pareto efficient outcomes using an algorithm? $\endgroup$
    – Herr K.
    Feb 14 '19 at 3:57
  • $\begingroup$ @HerrK. Yes. An algorithm that will work for an $n$-player Prisoner's dilemma game, where $n\geq 2$. $\endgroup$
    – johnny09
    Feb 14 '19 at 18:01
  • $\begingroup$ 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 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 stackoverflow.com or cs.stackexchange.com $\endgroup$
    – Herr K.
    Feb 14 '19 at 19:35
  • $\begingroup$ @HerrK.Do you know any reference for this type of thing? Textbook or paper. I am more interested in the theoretical aspect. $\endgroup$
    – johnny09
    Feb 15 '19 at 5:35
  • $\begingroup$ What do you mean by "this type of thing"? $\endgroup$
    – Herr K.
    Feb 15 '19 at 17:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.