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.