In the Pareto-optimised crowd, be sure to know your place

by Stuart_Armstrong 9y7th Jan 201112 comments

4


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 u1 and u2, then you must pick a θ>0 and maximise u1+θu2 (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 θ12, θ23 and θ31, and seek to maximise u112u2, u223u3 and u331u1 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 θ12θ23θ31=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 (θ12), and from dollars to euros (θ23), then you know the exchange rate from euros to pounds (θ31=1/(θ12θ23)). 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 θ12θ23...θ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 u1+θu2 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 θ12, θ23 and θ31 as above. The utility outcomes for the three games (given by maximising u112u2, u223u3 and u331u1) will be designated o12=(x1,y2), o23=(x2,y3) and o31=(x3,y1), with the index corresponding to the players.

We now consider a change to the utilities by adding the vectors v12=(x12,y12), v23 and v31 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 x12+y31 (the change to player 1's utility) x23+y12 and x31+y23 all be positive. The second condition requires that o12+v12 is not to the right of the natural tangent line through o12. Since the normal to this tangent line is (1,θ12), this is equivalent with requiring that the dot product of v12 and (1,θ12) be negative, hence that x1212y12, x2323y23 and x3131y31 all be negative.

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

x12 ≤ -θ12(y12) ≤ θ12(x23) ≤ -θ12θ23(y23) ≤ θ12θ23(x31) ≤ -θ12θ23θ31(y31) ≤ θ12θ23θ31(x12)

Now if the change is actually going to be a Pareto-improvement, one of the inequalities will have to be a strict inequality, giving x12 < θ12θ23θ31(x12). This is obviously impossible when θ12θ23θ31 = 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 θ12θ23θ31. If θ12θ23θ31 > 1 (equivalent with T > 1), then the following vectors (strictly) obey all the above inequalities:

v12=(θ12θ23θ31 ε, -Tθ23θ31 ε), v23=(T2θ23θ31 ε, -T3θ31 ε), v31=(T4θ31ε, -T5ε).

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

v12=(-θ12θ23θ31 ε, Tθ23θ31 ε), v23=(-T2θ23θ31 ε, T3θ31 ε), v31=(-T4θ31ε, T5ε).

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 θ12θ23θ31=1. But it is possible to have θ12θ23θ31≠1 and be Pareto-optimal as long as the outcomes are on a corner. However, in these circumstances, there will always be values θ'12, θ'23 and θ'31, giving the same outcomes as θ12, θ23 and θ31 and with θ'12θ'23θ'31=1. This can be seen by replacing the corner with a series of limiting smooth curves.

4