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.
