This video is about the coalitional game theory solution concept called the core. Recall that the Shapley value told us about how to divide the coalition's value fairly among all of its members. In this video We instead want to think about whether the agents would be willing to form the grand coalition, as compared to forming smaller coalitions that might give all of their members greater value than they're able to achieve in the grand coalition. Let's begin by looking at an example which we're going to call the voting game. We're going to think about a parliament that consists of four political parties which we'll call A, B, C and D. Each of these parties have a different number of seats in the parliament. 45 seats, 25, 15 and 15 respectively. The parties have to vote to decide whether to pass a spending bill of a 100 million dollars and also to decide amongst themselves how to divide that spending between the parties. It's necessary to get a majority which is to say fifty one votes in order to pass any legislation and of course if the bill doesn't pass, then there will be no money for any of the parties to spend. Let's begin by thinking about the Shapley values in this case. I, I'll tell you what the answer is in a second, but you may want to pause the video here and work out for yourself what the Shapley values are in this situation. So, these are the Shapley values here. I won't show you how we did the calculation. Notice in particular, That even though, B and C and D have different numbers of votes, they end up getting the same value in the Shapley value. The question that I want to focus on today, is whether any sub-coalition can gain, by defecting from the grand coalition? Again I'll invite you to pause and think about that before I give you the answer. So the answer is that a sub-coalition can gain, in particular, A and B together could form a sub-coalition which would do better than the grand coalition and Being paid according to the Shopley values. So, A and B by themselves have en ough votes to pass the legislation without the help of C and D and if they were to divide the 100 million amongst themselves, for example 75, 25, then they would each get more than they got Under the Shapley value division, and they would still pass the legislation. So, this goes to show that while the Shapley values may be fair, they don't necessarily give the right incentives to all of the different parties to want to actually join the grand coalition and so, instead, we should look for different ways that the parties could divide the payments so that they would be willing to form the grand coalition So that's the question that we're going to think about in this video. Under what payment divisions would the agents be willing to form the grand coalition? And the answer as we'll see is that they would be willing to do so if the payment the profile belongs to a set which we'll call the core. Here's how we define the core. So, we're going to think about a given payment vector, that's going to be an assignment of a certain amount of value to each of the different members of the coalition. And we're going to say that the core, that this payment vector is in the core of a coalitional game. If and only if the following condition is true. For every coalition that could form and which is a subset or equal to the grand coalition. So every subset of the grand coalition, it's the case that for all agents in that subset. if we sum across all of the agents in that subset, excuse me. The amount of payoff that the payoff vector says that we give to each of those agents I in the subset. That sum is at least as much as the value that the agents would have gotten as a coalition if they had deviated, and instead, formed that subset S. So, kind of intuitively, what we're guaranteing here is that the sum of the payoffs to all of the agents in any subcoalition, is at least as much as they could earn if they actually did go off and form that subcoalition. And you can see in the voting game that's what we saw Wasn't ach ieved. That the amount that we were paying a and b under the shoply value payments wasn't as much as they could have gone off and gone, gotten on their own. So if there doesn't exist any sub coalition where the agent's could have gotten more on their own then our pay affecter is in the court. And intuitively this is like Nash equilibrium. Because what we're saying is the agents don't have any profitable deviations. It isn't the case that any subcoalition could deviate away from the grand coalition, and end up with higher payment for themselves. The way it's different from Nash equilibrium is we're thinking about groups of agents jointly deviating. So. In, in a sense it's a stronger notion than a Nash Equilibrium. We don't think only about unilateral deviations here. So, any time a solution concept is introduced to you, there are two questions that you should wonder about. The first is whether the solution concept always returns something. Analogously remember Pure strategy Nash equilibrium doesn't always exist. Mixed strategy equilibrium does always exist. So we might wonder, if the core always nonempty? Does it always suggest at least one payment profile to us? Secondly, we might wonder, is the core always unique? When it does return something to us does it always return one thing, does it make a sharp recommendation, or might it return multiple things? Well first of all, is the core always nonempty? the answer here unfortunately is no. So there are some games in which, there aren't any stable payments, that can be allocated to the agents. And we can see this already in the voting game. So, the set of minimal coalitions that are able to pass the legislation are A B, A C, A D, and B C D. All of these subsets of the agents have enough votes to pass the legislation. Now we can Just looking at these sets reason that there isn't any way of dividing the payments that would be stable, for all sub coalitions. In particular we can see that if the sum of the payoffs to the parties in b c and d ends up being less than a hundred, then this set of agents has reason to deviate and form this coalition, where they can then Divide the full hundred million amongst themselves. However, if B, C and D get the entire payoff of a hundred million, then A can form a coalition with any one of B, C or D, which would be sufficient And it could do this with which ever of the of B, C, and D is getting paid the least under whatever payment profile we're assuming is adequate for B, C, D. And best that we can see is there is always some sub-coalition that can profitaly deviate from any. Payment profile that, that we propose, and that means that the core is empty for this game. The second thing we might wonder is, in cases where the core is not empty, is it unique? And again, here the news is bad. Because, no, the core is not always unique. So now let's consider changing teh voting game, so that we require an 80 % majority, instead of a 51% majority. It's now the case that the winning coalitions are these 2 coalitions, these are the only coalitions that are able to obtain 80% majority, the, the only minimal coalitions And it's now the case that a and b are a required in all winning coalitions. And this means that any complete distribution of the $100 million between just a and b is going to belong to the core because there's no way that c and d, even if they're not paid anything can go off and form some As different coalition that would pay them more. And so, the grand coalition is stable as long as a and b get paid everything. Now let me give you a few more definitions so I can say some more positive things about the core. First let me define a simple game. I'll say that a game is simple if it's the case that, for all coalitions, the value of the, the coalition is either zero or 1. And notice that our voting game is a simple game. And the reason is that we either produce 100 million dollars. Or 0, depending on whether we get a majority or not. And so, we can scale those payoffs where 1 is 100 million dollars and 0 is 0 and we can then encode this as a simple game. My 2nd definition is of a veto player and I'll say that a player i has a veto if The value of all coalitions that don't involve i is 0. So in other words the participation of i in a coalition is necessary if the coalition is going to produce any value at all. Putting these 2 things together it's possible to show that. In a simple game, the core is empty exactly when there is no veto player. And that's precisely what we saw in our voting game example already. We had no veto player. in the case where we needed a 51 percent majority. Because there was a coalition that didn't involve a. On the other hand, the core was empty, in that case. on the other hand, if there are veto players, the core consists of all of those payoff vectors where the nonveto players get zero and the payoff is divided among the veto players. And, again, we saw that in our voting game example here where we had the 80 percent majority required. Where a and b were both veto players. I want to say 1 more positive thing about the core. And to do that, I'm going to illustrate, another coalitional game example. So this is called the airport game. In this example, there are several different cities in the same geographical area that need access to airports and the different cities are different sizes and so they need to be able to accommodate different sized airplanes. They have to decide between each building their own airport or building a regional Airport and sharing the cost of building the regional airport amongst all the cities. If they build the regional airport it's cost is going to depend on the largest plane that has to be accomondated. So, whichever city in the coalition that builds a regional airport Needs the biggest aircraft is going to set the size of the airport for everybody. Otherwise, everyone just builds their own airport. So we'll model this as a coalitional game as follows, and, as of course, the set of cities And the value of each coalition is ba sically the amount of work that was avoided as compared to having all of the airports built individually for each city. So, more specifically, the value of a coalition is the sum of the cost of building runways for every city in S Minus the cost of the biggest runway which is the one that actually has to be built for the regional airport. Well I'll define a convex game as follows, a game is convex If, for all, coalitions that are strict subsets of n, the value of the union of those subsets, of those two different coalitions, is at least as big As the value that the first can achieve by itself plus the amount the second could achieve by itself minus the amount that the coalition in common between these two can achieve for itself. So notice that we, we already talked about superadditivity. this is a stronger assumption because superadditivity assumed that s and t had an empty intersection. Whereas here we're allowing them to have an intersection and we're, we're just subtracting the value of its intersection. So, so this speaks about also cases in which s and t. Do have 1 or more agents in common. Nevertheless, convex games are, are relatively common and the Airport games is an example of a convex game. So the reason I mentioned convex games is to say some nice things about the core. And here are, are 2 kind of positive theorems about the core. First of all, in the case of convex games, the core always is nonempty. So, there's always at least some way of dividing payments between all of the agents to support the grand coalition and in a way where no subset of the agents would be willing to deviate in order to, to benefit themselves Secondly, even better, the Shopley value is in the core for convex games and so that means that for these particular games, dividing the value of the grand coalitoin in a way that is stable and dividing the value of the grand coalition in a way that is fair are not goals that are at odds with each other. So in these games, it's possible to do both.
