Monday, 22 June 2015

Nash bargaining solution

Following the tragic death of John Nash in May I thought it would be good to explain some of his main contributions to game theory. Where better to start than the Nash bargaining solution. This is surely one of the most beautiful results in game theory and was completely unprecedented. All the more remarkable that Nash came up with the idea at the start of his graduate studies!
         The Nash solution is a 'solution' to a two-person bargaining problem. To illustrate, suppose we have Adam and Beth bargaining over how to split some surplus. If they fail to reach agreement they get payoffs €a and €b respectively. The pair (a, b) is called the disagreement point. If they agree then they can achieve any pair of payoffs within some set F of feasible payoff points. I'll give some examples later. For the problem to be interesting we need there to be some point (A, B) in F such that A > a and B > b. In other words Adam and Beth should be able to gain from agreeing.
          The solution is a pair of payoffs (A*, B*) that Adam and Beth should agree on. Nash gave a list of axioms he suggested that a solution should satisfy. Informally, these are: 
 
(1) Pareto efficiency: There must be no feasible point that would make both Adam and Beth better off.
 
(2) Individual rationality: Adam and Beth must do at least as well as the disagreement point.
 
(3) Scale invariance: If we do a linear transformation of payoffs, e.g. converting Adam's payoff from euros to dollars, then the solution merely needs to be transformed as well. In other words, the solution is 'the same' whether we use euros, dollars, roubles or anything else. 
 
(4) Symmetry: If Adam and Beth have symmetrical bargaining positions they should get the same payoff.
 
(5) Independence of irrelevant alternatives: If we eliminate some feasible points that were not a solution then the solution should stay the same.
 
Nash showed that there is a unique solution that satisfies all these five axioms. The solution is to find the pair A* and B* that maximize the Nash product (A - a)(B - b). This is a remarkably succinct result. It is also easy to apply. A beautiful theorem! To understand the result better we need to delve into the proof.
            Consider, first, a very simple example. Suppose that Adam and Beth are bargaining over how to split €100. If they disagree they each get €0. The feasible set is the blue triangle in the figure below. What is the solution? The Pareto efficiency axiom requires A* + B* = 100. The symmetry axiom requires A* = B*. Only one point satisfies both these axioms and that is A* = B* = €50. To see if this is the Nash product we need to maximize AB. Plugging in B = 100 - A we get A(100 - A). Maximizing this we respect to A does indeed give A* = 50 as desired.


          Given the symmetry of the first example there is nothing particularly controversial or exciting about the solution that Adam and Beth should split things equally. So, let us consider a slightly more complex example. Suppose that there are 100 tokens up for grabs. Any token given to Beth is worth €1 and a token given to Adam is worth €2. Also, suppose that if they disagree Beth gets €10 and Adam gets €30. The figure below depicts this scenario.




         Things are now asymmetric. What shall we do? We can apply the scale invariance axiom to convert the bargaining problem into one that is symmetric. It is necessary to solve some simple equations to do so. I'll illustrate with one possibility. Suppose for Beth, given any amount €B, we take off 10 and then multiply by 4/3. For Adam we take off 30 and then multiple by 2/3. Do this and we obtain the bargaining problem depicted below. This problem is symmetric and very similar to the first example. (The only difference is that negative payoffs are now possible meaning that we need to apply individual rationality).


            This new bargaining problem has a unique point satisfying Pareto efficiency and symmetry. Namely, €50 each. This means that to satisfy Pareto efficiency, symmetry and scale invariance the original problem must also have a unique solution. Moreover, we just need to reverse the scaling to find the answer. Doing so we get €105 for Adam and €47.50 for Beth. You can check that this maximizes the Nash product as desired.
           Consider a final example depicted below. This is similar to the first example except that Adam cannot get more than €40. No amount of scaling is going to make this example symmetric. So, we need a new trick. 
         Suppose we scale the respective payoffs as follows. For Beth we multiply any amount €B by 15/12 and for Adam we multiply any amount by 5/6. Then we obtain the bargaining problem depicted below. It may not be immediately clear that this has helped much. We can, however, apply independence of irrelevant alternatives. In particular, consider our first example of splitting €100 (orange dotted line). The feasible set of the current bargaining problem is a subset of the split €100 problem. Moreover, the €50 each solution to the split €100 problem is in the feasible set of this new problem. 

             So, in order to satisfy Pareto efficiency, symmetry, scale invariance and independence of irrelevant alternatives there must be a unique solution to the original problem. The solution of the split €100 bargaining problem is, of course, €50 each. Scaling this back to the original problem we get a solution of €40 for Adam and €60 for Beth. You can again check this is consistent with maximizing the Nash product.
            This last example shows that the solution of any bargaining problem can, with the use of scale invariance and independence of irrelevant alternatives, be equated with the solution of a symmetric bargaining problem. And a symmetric bargaining problem has an obvious solution. Herein lies the beauty of Nash's bargaining solution.
             The Nash solution has stood the test of time and remains in common use. Many, however, have questioned the independence of irrelevant alternatives axiom. In our third example, for instance, we might ask whether Beth could hope to do better than €60 given her strong bargaining position. The experimental evidence, I would say, is largely supportive of the axiom Nash proposed. That though is a topic for another time. 

No comments:

Post a Comment