Can we really do much together?
Cooperative games, Shapley values and resource allocation
Cooperation is always more powerful than the competition. -Bob Proctor
Nash equilibrium states that a game’s optimal outcome is when players do not deviate from the original strategy and think rationally about both themselves and the whole group. Now, once the players are in cooperation they demand maximum payoffs. It is easy to calculate their payoffs in a symmetric game as in symmetric games each player yields equal payoffs. But what about non-symmetric forced cooperative games? Are there still collisions among the playing parties in “so-called” cooperation?
Imagine you call a cab for going home from university. While waiting, you meet two friends Aaryan and Manas, who have to take the same route. Therefore, you “agree” to share the cab. After the journey, you are first to leave the cab with a current fare of Rs. 180. When Aaryan and Manas will reach their destinations the fare is going to be 250 and 330 respectively. What amount should you pay now? Should you play irrationally and pay Rs. 200 or should you rely on your bit rusty game theory skills?
The above situation is a real-life example of forced cooperation in a non-symmetric game. Players yield different payoffs but they have an optimal profit when working in a group only. This optimal resource allocation to different playing parties is called cost-sharing or profit-sharing which is a major concept in game theory. You must have heard of “I cut, you choose” problem. The problem is to divide a piece of cake among two kids such that both get satisfied. The optimal solution is that child A will cut the piece into two parts and child B will be the first one to choose among those pieces.
Solution for cake cutting problem with 3 kids for curious minds: https://www.youtube.com/watch?v=kaMKInkV7Vs&t=220s]
This technique compels child A to cut as evenly as possible so that he/she receives pieces with an equal cake. “I cut, you choose” is referenced in many pieces of literature regarding the division of the Balkans after WW2 or sharing of the Middle East. Even the United Nations Convention on the Law of the Sea applies a procedure similar to divide-and-choose for allocating areas in the ocean among countries. Cost-sharing problem is an extended version of “I cut, you choose” as there are more than two players and players may not have equal contributions in the coalition and hence, deserve unequal payoffs.
Problem with proportions and Socks game
When dividing payoffs or resources among the playing parties the first solution is to use proportions. But, is it an optimal solution? Lets take another problem to understand the anomaly.
Alice only has a left sock and Bob, has a right sock. Bob can sell his sock in the market for ₹ 1 and Alice can sell her sock for ₹ 2. But, if they come together and sell the pair of socks they can sell it for ₹ 10. Obviously, it is profitable to cooperate but, how should they share the money between them? From a layman’s perspective, the idea that strikes first is sharing the money proportional to the original prices when they were selling the items individually. So, Alice will get ₹ 6.67 and Bob will get ₹ 3.34. Fair, right?
But this allocation is incorrect. Why? Imagine Bob can sell his sock in the market for ₹ 0.1 only. Now he will get roughly ₹ 0.5 and Alice will get about ₹ 9.5. Bob has equal power in destroying the coalition and seeing his once market competitor receiving huge profit due to him will invoke him to disrupt the coalition. The proportional rule clearly fails as it does not consider the bargaining and contribution powers of the playing parties. This weakness of proportional rule gets more highlighted when there are multiple players in the market and not only maximum share but also optimal in accordance to other players.
Shapley vs Proportion and a Nobel Prize
Lloyd Shapley was a mathematician and economist and is considered to be one of the eminent contributors to game theory. He won the 2012 Nobel prize in Economics for his infamous Shapley values and “for the theory of stable allocations and the practice of market design.” Shapley values are most efficient as they take the bargaining and threatening power of cooperation parties under consideration and calculate the average of marginal contributions in all possible coalition combinations. Its importance can be seen in coalitions in elections, cost optimisation in a situation of confrontment, dividing the estate or resources etc. Mathematically, in a coalition with n players, S is the coalition of players and v(s) is the worth of the S coalition in the game, amount ith player gets is:
But the formula looks scary. Let’s try to use the concept of Shapley values in the socks game without going into the rigorous mathematics. In the game, if Alice and Bob come into a coalition the minimum profit they want is ₹ 2 and ₹ 1(Less than this is unprofitable). Let (A, B) represent the set of money divided among them after the selling of pair of socks. The two marginal contribution permutations will be (2,8) and (9,1). These two points are called threshold points. Now we will take the average of these individual payoffs which gives us ₹ 5.5 to Alice and ₹ 4.5 to Bob. Efficient and optimal!
An intuitive solution to the Cab problem
As we have sufficient knowledge of cooperative games and Shapley values, let’s solve the problem discussed at the beginning of the article. As the problem has 3 players and the order in which they pay the money does matter, we are gonna solve it in an intuitive way. When the cab reaches your destination, the fare till this point is ₹ 180 and should be shared among the three of you which will be 180/3=₹ 60. Next, the cab reaches Aaryan’s destination and this journey fare should only be divided between Aaryan and Manas only.
(250–180)/2=₹ 35.
So, the total amount Aaryan need to pay is 60+35=₹ 95. Finally, the last journey is to be completely paid for by Manas only as no one contributes to that journey’s fare except Manas.
(330–250)=₹ 80.
Manas’s total fare will be 60+35+80=₹ 175.
So the answer is: you, who leaves the cab first will pay ₹ 60, second Aaryan will pay ₹ 95 and finally Manas pays the sum of ₹ 175. 60+95+175=₹ 330. Not only intuitive but also optimal distribution. Else you can say “Ah, I ain’t carrying cash today, I will Paytm once I reach home!”
So what did we learn today? Cooperative games do not mean the players are not in any competition to get maximum profits. We can solve symmetric games using the proportion rule and for non-symmetric games such as the socks game or the cab fare problem: Shapley for the win!
That’s all for today! Stay tuned for more interesting insights on how Game Theory is controlling the world.
Author — Game Theory Enthusiast Naman Jain, The Indian Game Theory Society — Delhi Technological University
References:
- https://mindyourdecisions.com/blog/tag/shapley-value/
- http://www.coalitiontheory.net/research-areas/cooperative-game-theory
- The Complete Idiot’s Guide to Game Theory: The Fascinating Math Behind Decision-Making by Edward C. Rosenthal Ph.D. (Author)
