0:00

This video is going to define coalitional games, and explain what they're used for.

So, coalitional games, unlike the non cooperative games that we've talked about

so far, don't model individual agents taking actions. Instead, they think about

groups of agents acting together. So the idea is going to be that we think about a

set of agents and ask about what coalitions could form, what groups of

agents could choose to work together, and to do that we're going to define how well

each different group of agents is able to do for itself. Now, in particular, in a

coalitional game We're not going to think about, how the agents individually divides

the work up within the coalition, or how it is that they coordinate with each other

in order to form a coalition. We're going to take all of that as given, and instead,

just think about how the coalition does. All together what kinds of payoffs they're

able to achieve. We're going to begin by making an assumption that is called

transferable utility. What this assumption means is that it's possible for a

coalition to redistribute the value that it's able to achieve arbitrarily among

it's members. So, for example if the coalition is paid its value in money it

would be possible to divide up that money and make side payments among the members

in anyway. In general what this assumption amounts to is that we'll be able to assign

some single value as the payoff to a coalition and trust the rate can be

arbitrarily divided up among the members. , Under this assumption here's how we can

define a coalitional game. A coalitional game has two parts n and v. Where, as in

the previous models we've thought about before, n is just a finite set of players

and we'll again index this by i when we want to talk about individual players in

the set. And v kind of acts like our utility function for coalitionial game. It

says for every subset of the players S, so for every coalition 2 that could form, up

to and including all of the players in the game, what is the payoff V of S that the

coalition can achieve and this of course will allow the coalition to divide up

among its members. We'll make a normalizing assumption that the value of

the empty set is 0. There are two typical questions that we want to ask using

coalitional game theory, two kind of fundamental questions. The first is which

coalition makes sense to form, which coalition would like to form in this game?

And, secondly Once we know which coalition will form, how should the coalition divide

its payoff amongst all of the people in the coalition? Now we're not going to

spend very much effort thinking about the first question. It's usually going to be

the case that the answer is the so-called grand coalition which means everybody. So

usually All of the agents will agree to work together. However, sometimes in order

to guarantee that this would be true, we have to be careful about thinking about

how the coalition will divide its payoffs among its members. In particular, here's a

kind of game, that, that helps us to think about the first question. We say that a

coalitional game is superadditive. If for all pairs of coalitions S and T which are

both strict subsets of N. If the intersection between these 2 coalitions is

empty, which means these 2 coalitions involve entirely different sets of agents.

Then, if we make a new coalition, s union t, that combines these 2 coalitions

together. The value of this larger coalition is at least as big as the sum of

the values of the 2 coalitions independently. So, in other words. If I

make a bigger coalition out of two independent coalitions, the value of that

bigger coalition is always at least as big as the sum of the values that those two

independent coalitions were able to get on their own. This assumption makes sense if

it's possible for coalitions to always work without interfering with each other.

And this is often an assumption that we make in a coalitional game. Notice that

this super additivity assumption implies that the highest payout of all, at least

the weekly highe st payout of all is achieved by the grand coalition. So, when

we're thinking about a superadditive game, it's natural to think that the grand

coalition would want the So, in answer to the first of the questions that I talked

about before, we're going to tend to assume that the grand coalition forms. And

we're going to focus on this second question, of how the coalition ought to

divide its payoff. Now, it's reasonable to wonder what I mean when I say, how it

ought to divide its payoff. That kind of depends on what the coalition is trying to

achieve. And we're going to consider 2 different ways of answering that question.

The first is, how it ought to divide its payoff if what it's concerned with is

fairness. Secondly, we might, instead wonder about how it ought to divide its

payoff, if what it's concerned about is stability. By which we mean, everybody

would be willing to form the coalition rather than instead forming smaller

coalitions. Because they might be able to achieve higher value for themselves. And

we'll, we'll look at all of this in the videos that follow.