tldr: In a population playing independent two-player games, Pareto-optimal outcomes are only possible if there is an agreed universal scale of value relating each players' utility, and the players then acts to maximise the scaled sum of all utilities.

In a previous post, I showed that if you are about the play a bargaining game with someone when the game's rules are initially unknown, then the best plan is not to settle on a standard result like the Nash Bargaining Solution or the Kalai-Smorodinsky Bargaining Solution (see this post). Rather, it is to decide in advance how much your respective utilities are worth relative to each other, and then maximise their sum. Specifically, if you both have (representatives of) utility functions u₁ and u₂, then you must pick a θ>0 and maximise u₁+θu₂ (with certain extra measures to break ties). This result also applies if the players are to play a series of known independent games in sequence. But how does this extend to more than two players?

Consider the case where there are three players (named imaginatively 1, 2 and 3), and that they are going to pair off in each of the possible pairs (12, 23 and 31) and each play a game. The utility gains from each game are presumed to be independent. Then each of the pairs will choose factors θ₁₂, θ₂₃ and θ₃₁, and seek to maximise u₁+θ₁₂u₂, u₂+θ₂₃u₃ and u₃+θ₃₁u₁ respectively. Note here that I am neglecting tie-breaking and such; the formal definitions needed will be given in the proof section.

A very interesting situation comes up when θ₁₂θ₂₃θ₃₁=1. In that case, there is an universal scale of "worth" for each of the utilities: it's as if the three utilities are pounds, dollars and euros. Once you know the exchange rate from pounds to dollars (θ₁₂), and from dollars to euros (θ₂₃), then you know the exchange rate from euros to pounds (θ₃₁=1/(θ₁₂θ₂₃)). We'll call these situations transitive.

Ideally we'd want the outcomes to be Pareto-optimal for the three utilities. Then the major result is:

The outcome utilities are Pareto-optimal if and only if the θ are transitive.

What if there are not three, but hundreds, or thousands of players, playing games with each other? If we assume that the utilities derived from each game is independent, then we get a similar result: given a sequence of players 1, 2,..., n such that each plays a game with the next player and n and 1 also play a game, then we still get:

The outcome utilities are Pareto-optimal if and only if the θ are transitive (ie θ₁₂θ₂₃...θ_n-1nθ_n1=1).

What this means is the Pareto-optimal outcomes are only possible if there is a universal (linear) scale of value relating all the utilities of any player linked to another by direct or indirect trade links. The only important factor is the weight of your utility in the crowd. This result should be easy to extend to games with more than two players, but that's beyond the scope of this post.

The rest of this post is a proof of the result, and may be skipped by those not of a technical bent.

Proof:

Apologies if this result is known or trivial; I haven't seen if before myself.

Here, we will always assume that the set possible outcomes is convex (mixed solutions are always possible) and that the Pareto-optimal outcome set is smooth (no corners) and contains no straight line segments. What these conditions mean is that if O is the set of Pareto-optimal outcomes, then each point in O has a well defined tangent and normal vector. And further, the slope of the tangent never stays constant as we move around O. Because O is the upper-right boundary of a convex set, this means that each point in O is uniquely determined by the slope of its tangent vector - equivalently, by the slope of its normal vector. The normal vector is particularly useful, for the point in O that maximises the utility u₁+θu₂ is the point that has normal vector (1, θ). This means that each point in O is uniquely determined by the value of θ. This is illustrated in the following diagram. Here θ=2/3, the purple set is the set of possible outcomes, the blue lines are the sets of constant x+(2/3)y, and the red normal vector (1, 2/3) is drawn from the maximising outcome point (1, 2.5):

 

Now assume we have θ₁₂, θ₂₃ and θ₃₁ as above. The utility outcomes for the three games (given by maximising u₁+θ₁₂u₂, u₂+θ₂₃u₃ and u₃+θ₃₁u₁) will be designated o₁₂=(x₁,y₂), o₂₃=(x₂,y₃) and o₃₁=(x₃,y₁), with the index corresponding to the players.

We now consider a change to the utilities by adding the vectors v₁₂=(x₁₂,y₁₂), v₂₃ and v₃₁ to each of these outcomes. We want the changes to be Pareto-optimal, and to remain within the set of possible outcomes for each game. The first condition can be phrased as requiring that the changes to each utility be positive; i.e. that x₁₂+y₃₁ (the change to player 1's utility) x₂₃+y₁₂ and x₃₁+y₂₃ all be positive. The second condition requires that o₁₂+v₁₂ is not to the right of the natural tangent line through o₁₂. Since the normal to this tangent line is (1,θ₁₂), this is equivalent with requiring that the dot product of v12 and (1,θ₁₂) be negative, hence that x₁₂+θ₁₂y₁₂, x₂₃+θ₂₃y₂₃ and x₃₁+θ₃₁y₃₁ all be negative.

Then using all six inequalities above, we can see that:

x₁₂ ≤ -θ₁₂(y₁₂) ≤ θ₁₂(x₂₃) ≤ -θ₁₂θ₂₃(y₂₃) ≤ θ₁₂θ₂₃(x₃₁) ≤ -θ₁₂θ₂₃θ₃₁(y₃₁) ≤ θ₁₂θ₂₃θ₃₁(x₁₂)

Now if the change is actually going to be a Pareto-improvement, one of the inequalities will have to be a strict inequality, giving x₁₂ < θ₁₂θ₂₃θ₃₁(x₁₂). This is obviously impossible when θ₁₂θ₂₃θ₃₁ = 1, so in that circumstance, there cannot be any Pareto-improvements. This demonstrates half of the implication.

Now let T be the sixth root of θ₁₂θ₂₃θ₃₁. If θ₁₂θ₂₃θ₃₁ > 1 (equivalent with T > 1), then the following vectors (strictly) obey all the above inequalities:

v₁₂=(θ₁₂θ₂₃θ₃₁ ε, -Tθ₂₃θ₃₁ ε), v₂₃=(T²θ₂₃θ₃₁ ε, -T³θ₃₁ ε), v₃₁=(T⁴θ₃₁ε, -T⁵ε).

Since these obey the inequalities strictly and the outcome sets are smooth, for sufficiently small ε, these provide a Pareto optimal improvement. If θ₁₂θ₂₃θ₃₁ < 1 (equivalent with T < 1), then the following vectors work in the same way:

v₁₂=(-θ₁₂θ₂₃θ₃₁ ε, Tθ₂₃θ₃₁ ε), v₂₃=(-T²θ₂₃θ₃₁ ε, T³θ₃₁ ε), v₃₁=(-T⁴θ₃₁ε, T⁵ε).

This proof can be extended to n players in a similar fashion.

When the outcome sets contains straight line segments, we need a tie breaking system for cases when the "utility indifference lines" are parallel to these segments; apart from that, the result goes through. If the outcome sets contain corners, it remains true that there are no Pareto-optimal improvements when θ₁₂θ₂₃θ₃₁=1. But it is possible to have θ₁₂θ₂₃θ₃₁≠1 and be Pareto-optimal as long as the outcomes are on a corner. However, in these circumstances, there will always be values θ'₁₂, θ'₂₃ and θ'₃₁, giving the same outcomes as θ₁₂, θ₂₃ and θ₃₁ and with θ'₁₂θ'₂₃θ'₃₁=1. This can be seen by replacing the corner with a series of limiting smooth curves.