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.

Â