0:00

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.

Â