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.