Cooperative Games and Non-Cooperative Games

• Non-cooperative games
Agents make decisions on their own without coordinating with other players outside of the game.
This feature is illustrated by the fact that whenever we want to find an equilibrium, we check that there is no unilateral deviation
(i.e. deviation by a single player).
• Cooperative game
Agents can take decisions collectively.

Set-Up of Cooperative Games

• Components in a cooperative game (there is no universally agreed components)
Players N={1, ..., n}
‣ Coalitions (we consider exclusive groups of players in this lecture): each player can belong to only one group at a time.
‣ Coalition structure: partition of N (there can be many coalition structures as N can be divided in many ways).
Set of actions (actions that coalitions can take)
‣ Actions are attributed to coalitions instead of players. Players get together and choose the action that is the best for their
coalition.
Preferences
‣ Preferences are defined at the level of the agents. Each agent will have preferences defined on the profiles of actions.
‣ We may derive the preferences of a group of agents.
• Core
Cooperative games have many solution concepts or solution notions. We focus on one of them, which is core. A core of a game is
a set of actions of a grand coalition (i.e. the coalition of all the players in the game; denoted by a_N) that satisfies the following
property: there exist no coalition S and action a_S that can be taken by that coalition such that for all players in coalition S, this
action a_S is preferred to the action a_N. Mathematically,

‣ denotes the preferences of player i. Player i in coalition S prefers the action a_S (of which he is a member) to the action
a_N (i.e. the action of the grand coalition).

Note that when we were introducing the components of a cooperative game, we said that agents are going to have preferences over
profiles of actions. If we use this definition to describe a core, we would need to know the actions taken by all the coalitions, not only
coalition S and N. However, we are comparing a_S and a_N only because in cases where we are going to apply this definition, the
wellbeing of agent i will depend only on what his coalition decides to do and will not direct depend on what other coalitions decide to
do. Thus, we can use the definition of core above. Note that this is not without loss of generality.

The idea behind core is the following. The grand coalition get together and decide what they are going to do. A subgroup of agents may
want to leave the grand coalition if they can do better on their own. The grand coalition need to take this into account and make sure
that it offer members terms that are better than what they can get on their own. All the actions that satisfy this criterion are going to be
in the core of the game. We can refer to them as reasonable predictions in the game.

Example 1: Games in Characteristic Form

Consider a collection of agents who can form profitable partnership. Agents can get together in groups where the groups can produce a
resource, which has a value. In order to produce, agents have to be part of an exclusive group. This means that if we have a set of
players, then we want to discuss the petition of the set of the players and this petition is going to represent the coalition structure. The
question is how to form the groups and how are agents going to divide the output of the groups between themselves?

Suppose that there are n players. For every subset of N, denoted by S, the value of that subset is the value that the players in group S
form.

An action taken by S is

The length of the vector is equal to the cardinality (i.e. the number of elements in a set) of set S. The vector must satisfy the following
condition: the action that can be taken by S is to divide the value of the group in some way between the members of the group and the
actions taken by each player must be positive. The assumption that x_i ≥ 0 is not a general assumption. It is possible to have games in
which some players make payments to others instead of receiving some value of the partnership. We do not consider this possibility in
this example.
If we apply the definition of action to the grand coalition, we are basically dividing the value attached to the grand coalition, that is, to all
the participants in the game.

The core in this world is

The value attached to the subset S if everyone follows the action taken by the grand coalition.

An action taken by the grand coalition is a vector of N components. The action needs to satisfy two conditions:
1. The sum of all players’ actions sum up to the value attached to the grand coalition.
2. There exists no group and no action such that agent can split off and be better on their own.
Consider S, which is a subset of N. Summing up what the agents in coalition S can get under the action x gives the amount of
resources that is dedicated to S in the case in which x is played. Agents in S would want to split off if the value of the coalition,
denoted by v(S), is greater than the sum computed when x is played, i.e.
The inequality highlighted in yellow needs to be true for all the coalitions S.
Note that we are not interested in how some members may want to form another group and do better on their own. We are only
interested in whether such a deviation exists.

It is possible to have singleton coalitions (i.e. coalitions that consist of only one player) and such a coalition will have a value attached to it
(i.e. the value that this single player can get on his own). This means that for the action x to be in the core, the value that the single player
gets in the grand coalition needs to be greater than the value that he can get on his own. This gives the lower bound on what the person
can get in the grand coalition. It follows that we can change the assumption x_i ≥ 0 to the condition x_i ≥ (the value that player i can get
on his own). Thus, if everyone can get a value greater than zero on his own, then the condition x_i ≥ 0 would not be of concern.

Example: Two Players N = {1, 2}

Suppose that the values are

This game somewhat resembles the Rubenstain bargaining game, where the two players had to split one dollar. However, in the
Rubenstain game is a sequential bargaining game. When one person makes an offer, the other can accept or reject, then they swap
positions and there is a cost of delay (i.e. discount the future payoffs if the players do not agree immediately). In the cooperative game,
we are not interested in the actions taken by a single player and therefore we can get rid of all the structure of bargaining. We are
interested in what kind of actions would agents take as a grand coalition such that smaller coalitions cannot disturb that action profile.

The core in this game is

Any division such that nobody subsidizes nobody (i.e. both players do not receive anything negative) is going to be in the core.

Suppose that the values change to

The core is

The answer is the same as above except that the minimum value that each player get in the core needs to be greater than the new
minimum (i.e. 0.3 for player 1 and 0.6 for player 2).

Suppose that the values are

The core is

Player 1 and 2 will not form a partnership because they can earn more on the own. Specifically, the joint payoff on their own is 1.1, which
is greater than the value of the grand coalition. Thus, there is no outcome in the core. In some sense, a coalition structure in which
players stay on their own is something that resembles a core because there is no coalition that can do better. We can modify the
definition of the core such that we do not restrict the attention to the actions of the grand coalition. Alternatively, we can modify the
definition of this game and require that the value of the grand coalition is the value of partnership or the sum of values of smaller
coalitions that nest inside the partnership, depending on which value is greater. This would allow the core to contain some outcome.
Example: Three Players N = {1, 2, 3}
With more players, we need to define more values. We introduce some simplification by assuming that the value of singleton coalition is
one for all such coalitions. Mathematically,

Values of subset and the grand coalition are

Players can deviate from the grand coalition in two ways: 1. leave on individually, 2. talk to each other and split off with another agent.
Note that the coalition 13 and the coalition 12 have one participant in common. Both coalitions can choose to split off. The grand
coalition need to take both coalitions into account as the same time, even though they cannot split off at the same time (because player
1 is in both coalitions). Nevertheless, because both threats are possible in principle, the grand coalition need to consider both threats.

The core in this game is

We need to make sure that all smaller coalitions cannot threaten to break the grand coalition. We can find all vectors x that satisfy the
seven conditions by drawing the following diagram.

The vector x has three dimensions. However, since we only have two degrees of freedom (i.e. if x_1 and x_2 are defined, then x_3 is also
defined by condition 1), we can draw the vector x on the two dimensional plane.

Steps
1. By condition 5, everything below the line x_1 = 1 cannot be a part of the core.
2. By condition 6, everything to the left of the line x_2 = 1 cannot be a part of the core.
3. By condition 7, the sum of x_1 and x_2 must be equal to or less than 9. We can draw a line that passes through x_1 = 0 and x_2 = 9.
4. Draw a line for x_1 + x_2 = 5 (i.e. the line passes through the points (0, 5) and (5, 0).
5. Rewrite condition 2 as x_1 + 10 - x_1 - x_2 ≥ 4 —> x_2 ≤ 6. Draw a vertical line that passes through the point (6, 0).
6. Rewrite condition 3 as x_2 + 10 - x_1 - x_2 ≥ 3 —> x_1 ≤ 7. Draw a horizontal line that passes through the point (0, 7).

Any combination of (x_1, x_2) within the shaded area along with x_3 derived from condition 1 gives a vector that is in the core. The core
for this problem is not empty. We can easily generate an empty core by increasing the value of the smaller coalitions. By doing this, we
shift the lines in the graph and shrink the shaded area. If we increase the value of the smaller coalitions far enough, the shaded area
would collapse into nothing.

Intuitively, for agents to stay as part of the grand coalition, they have to divide resource in a way such that no one would want to split off.
If we increase the value of splitting off, then at a certain point, there will be no enough resources in the grand coalition to award
everyone for their loyalty to the grand coalition. The the core would become empty.
General Case
In general (i.e. with N players), it is difficult to check whether the core is an empty set of not. However, we can do check that easily in the
special case in which everything is symmetric. Suppose that the value of the coalition depends on the size of the coalition and not on the
identifies of the players. This means that if we have N = 3, the values of the coalitions would look like the following:

The core is

We can check whether the core is empty of not because the diagram is going to look symmetric:

If we increase a and b in a way such that the set shrinks, then the last element that is going to disappear from this set is the center of the
set. This is the point at which every agent gets exactly the same payoff. This means that the last element in the core that would disappear
is

Then, the question of whether the core is empty or not is equivalent to the question of whether this element is in the core or not. This is
because if this element is not in the core, then nothing else can be in the core. We can substitute the number 10/3 into the six
inequalities and get the answer to the questions. If a ≤ 20/3 and b ≤ 10/3, then the core is going to contain some element. If every
inequality is violated, then there is no solution to the problem.

Example 2: Allocation of Objects

Set up
Consider a set of N players and a set of M objects, i.e. N = {1, ..., n} and M = {1, ..., m}. The set of agents want to own these objects and
we are in a uni-demand setting in which each agent can own at most one object. These agents have preferences over the objectives (i.e.
each agent ranks to object). We assume that each agent in this world have strict preferences over the M objects (i.e. they are never
indifferent between two objects). Strict preference of agent i over the set M is denoted by

Practical Implication
Think of the agents as families and the objects as social housing. The task is to allocate the houses to the agents. When allocating houses,
we do not charge any money and we want to come up with the allocation that will turn out to be envy free (i.e. the families would not
want to switch with each other).

The problem we are trying to solve is how to match the elements in set N with the elements in set M. An requirement is that once we
match the objects to the agents, the agents would not want to trade with each other (i.e. no secondary market). This is a cooperative
game because saying that agents would not want to trade means that agents would not want to form smaller coalitions where they can
rearrange the initial matching.

Allocating objects to agents is the described by the concept of matching. In this world, matching is a function that maps agents into
houses. We enrich the set of houses with another element, element zero (i.e. no house).

The function takes the name of the agent as an input and product a output that says which house the agent is assigned to. An output of
zero means that the agent is not allocated to any house. The property of the matching is that for any two agents who are allocated some
items, these two agents receive different items (note that it is allowed for both agents to receive no house).
In the context of this model, we are going to look at matchings that are within the core and matchings that are not in the core.

A matching can be represented by a bipartite graph, where agents and objects are on the two sides of the
graph. Allocation is represented by a line that connects a certain object with a particular agent. We are
allowed to leave some agents and/or objects unconnected. This suggests that some agents may not receive
any house and some houses may be left unassigned. An requirement is that each node in the graph has a
degree of at most one. This means that the line that goes from each of the degree is unique. We cannot have
an agent owning two houses or one house being allocated to two agents. This de nes matching in this world.

Core
For a coalition S, μ(S) is the set of houses that are assigned to agents in S by the matching μ. If j is an element of the set μ(S), then we can
find an agent in coalition S who is assigned the house j.

The matching μ is in the core if there exist no coalition S that is a subset of N such that we can take all the houses that are assigned to
agents in S by μ (i.e. μ(S)) and find a matching μ’ for the problem S, μ(S) (i.e. the set of agents and the set of houses assigned) such that
for every agent in S, μ(S) is worse than μ’(S).

In other words, for whatever coalition we take, that coalition cannot reallocate the houses within the coalition in such a way that everyone
is better off. If this is the case, then μ is in the core.

Solution
An algorithm that delivers all the element in the core is called serial dictatorship:
1. Rank the agents in some order.
2. Let the first agent in the ranking pick his favorite object (from the available objects).
3. Assign the chosen object to that agent and remove that object from the list of available objects.
4. Continue to the next agent on the ranking and repeat step 2 to 4. Repeat the process until we run out of agents of objects. If N = M,
then all agents would get an item.

E.g.

The resulting outcome is a matching because during the procedure, we assign at most one object to each agent and no two agents can
select the same object. This is because when a particular agent makes his choice, all objects that have been chosen in the previous
rounds of the algorithm are not available. Thus, in the outcome, there is at most one object per agent and at most one agent per object.

The matching is in the core.

Proof by contradiction:
Suppose that the matching generated by the algorithm is not in the core. This means that we can find an coalition of agents that can get
together and exchange the houses they got during the algorithm. All agents in the coalition are better off by reshuffling. Suppose that
we have found such a coalition and players with * are in this coalition.
When agents 1, 3, and 4 form a coalition, they will have houses 3, 5, and m. They need to reassign the houses in such a way that all three
of them are better off. However, this is impossible. Inside the coalition, we cannot make agent 1 better off because agent 1 is above
agent 3 and 4, meaning that when he was choosing the house, he chose house 3 but not houses 5 and m which are also available. It
follows that agent 1 likes house 3 more than houses 5 and m. Moreover, since agents have strict preferences, agent 1 likes house 3
strictly better than houses 5 and m. Therefore, it is impossible to make agent 1 better off. We arrive at a contradiction.

The general set up for the argument is the following. We can pick a coalition S and find the agent who has the highest ranking in that
coalition. When this agent was choosing the object in the course of the algorithm, he could have chosen any other houses that now
belong to the coalition because those houses were available by the definition of the algorithm. Since this agent did not choose them, he
would be worse off if one of those houses is now offered to him. Therefore, coalition S cannot improve the wellbeing of all participants in
the coalition and the original matching must be in the core.

A desirable property of the algorithm is that it always generates a matching that is in the core. Moreover, the converse statement is also
true: for any matching in the core of this program, we can find a serial dictatorship algorithm that generates this matching. This means
that if we want to implement matchings in the core, we can just restrict our attention to this class of algorithm. The only thing that
distinguish one serial dictatorship algorithm from another is the ranking of the agents. So the statement means that for any matching in
the core, we can find a ranking of agents such that if we fit this ranking into a serial dictatorship, we can get the matching in the core
from which we started.
Proof:
Consider the following matching which is in the core.

Name the agents by letters such that we can assign numbers to agents that represent their ranks in the ranking. We need to assign
numbers in such a way that if we treat those numbers as ranking and run the serial dictatorship algorithm using this ranking, we can get
exactly the allocation of objects. Can we achieve this?

To show that we can, we need to prove the following lemma: if μ is in the core, then there exists an agent i such that μ(i) is agent i’s
favorite object. Mathematically,

This means that for every matching in the core, we can always find at least one agent who receives his favorite object in that matching.

Proof by contradiction:
Suppose that the lemma is not true, i.e. if we take a matching in the core, then for every agent in the problem, the object that is assigned
to the agent in that matching is not his favorite object, i.e.

We can then ask each agent to point to the agent who has his favorite object in the matching μ and this is represented by the diagram
below. By assumption, every agent does not have his favorite object and thus every agent will point to someone else (i.e. every letter has
a outgoing arrow). Then, we claim that in the diagram, we can find a cycle. For example, in this diagram, the cycle is g —> d —> c —> b
—> g (i.e. yellow line). Moreover, this cycle has a length of more than one, meaning that it is going to visit multiple agents on the way.
This is a graph theoretic result. If we have a graph and each node has exactly one outgoing arrow, then there always exists a cycle. If the
arrow for an agent goes somewhere but that agent (i.e. the arrow does not point to the agent himself), then the cycle is going to have a
length of more than one. In our cases, the cycle says that g’s favorite object belongs to d, whose favorite object belongs to c, whose
favorite object belongs to b, and whose favorite object belongs to g. This means that if they for their houses and trade along the cycle,
they would all become better off. If this is the case, μ cannot be in the core and we arrive at a contradiction. Therefore, it must be the
case that at least one agent has his favorite object among all.
The fact that one agent would point to himself would break the construction of the arrows and the cycle above. The only cycle would be
the agent who points to himself. However, since this cycle has a length of one, we cannot trade along the cycle and the agent simply gets
his own house. The lemma says that we can always find an agent who has his favorite house. It is useful for constructing the ranking of the
agents because we can says that since such an agent exist, we can assign a ranking of one to this agent.

Suppose that in the matching, c selects house 2 and house 2 is his favorite house of all the houses in this universe. Then, we can assign c
a ranking of 1. We do this because house 2 is c’s favorite. Thus, if we start running the algorithm, he is going to be the first agent who
gets to choose because he is ranked first and he will always choose house 2. Then, in the next step, we erase the pair (c, 2) from the list.

Erasing the matched paid (c, 2) would result in a new matching with fewer agents and fewer houses. If the previous matching is in the
core, the new matching would also satisfy the condition of being in a core. Then, we can apply the lemma again. Specifically, we can find
an agent that has his favorite house out of the available houses. Suppose that this agent is d, then we can assign d a ranking of 2 and let
him choose his favorite house from the available options. We can then erase the second matched pair and continue the process until we
run out of objects or agents. Since we are looking at the agents in this case, we would run out of agents. Once we run out of agents, we
would have each agent been assigned a number and we can use this ranking to restore the matching. Essentially, we are applying the
serial dictatorship algorithm backward to restore the ranking and we can then run it forward to show that we get the same matching.

The core of the lemma is that if agents point to their favorite houses, then a cycle would necessarily exist. The idea is called top trading
cycles. This idea has value on its own. We can use this idea to formulate an algorithm that would result in a core matching in another
problem.

Property of This Model

The core in this model is equivalent to the notion of Pareto efficiency. The definition of a Pareto efficient matching is that we cannot find
a way to reshuffle the matching such that everyone is weakly better off and some agents are stictly better off. This, together with the fact
that all agents have strict preferences over the objects, give us the definition of the core. The notion of Pareto efficiency and the notion
of the core have things in common in many models. The only way to break the two apart is to introduce something peculiar, such as weak
preferences or indifferences over the objects.

Example 3: Allocation of Objects with Endowments

Consider a set of N players and a set of M objects, i.e. N = {1, ..., n} and M = {1, ..., m}. The objects are pre-assigned to the agents (we
can think of the pre-assigned objects as agents’ endowments) using a matching μ_0. In other words, μ_0 is the initial matching of objects
to agents.

Practical Implication
We can think of the endowments are property rights. When agents enter the game, they already have some property rights over the
objects. The question is how can we reassign these objects such that everyone agrees with the reassignment.

We can about think of the N players as patients and the objects as donor organs (e.g. exchange of the kidney transplant). All agents
require kidney transplants and each agent has a friend who is willing to donate a kidney. The initial kidney is assigned by the initial
matching μ_0 to the patients. The problem is that some agents’ initial kidneys are not compatible. We can try to achieve full medical
compatibility by reassigning the kidneys.

Core
A matching μ is in the core if we cannot find a coalition S such that there exists a matching μ’ for the problem S, μ_0(S) (i.e. the set of
agents in S and the set of objects that coalition S is endowed with) where μ‘ can make everyone in S better off compared to μ. The
definition of a core in this game is the same as before but with one difference, that is, μ is replaced by μ_0 in one part of the definition.
Solution
An algorithm that delivers all the element in the core is called top trading cycle:
1. Ask all agents to point to their favorite object.
2. Find all cycles and trade along the cycle.
3. Remove agents who have traded (once an agent has traded, his allocation is the final object that he receives).
5. Repeat steps 1 to 3.

As shown before, there is always a cycle when each player has at least one outgoing arrow.

Without loss of generality (WLOG), we are going to assume that μ_0(i) = i. This is WLOG because
it is just a matter of naming the objects. This is a convenient way to name objects.

Each of the seven players has an endowment assigned by the matching μ_0.

Round 1:
• The only cycle is 2 —> 2.
• We erase 2 from the picture so that agent 4 cannot point to 2 anymore.

Round 2:
• Everyone excepts for agent 4 stick with their original arrow. Agent 4 needs to point to his next favorite item because his favorite object
is not available anymore. Suppose agent 4 points to 5.
• In this round, the cycle is 4 —> 5 —> 7 —> 4. Let these agents trade along the cycle.

Round 3:
• Agent 3 points to his favorite object within the available set of objects.
• In this round, the cycle is 1 —> 3 —> 6 —> 1. Let these agents trade along the cycle and everyone leaves.

We obtain the matching once we run out of agents. At each round of the algorithm, we can find a cycle. This follows from the graph
theoretic result mentioned before. This means that in every round, we necessarily can eliminate some agents. As long as there is a finite
number of agents, the algorithm is going to finish in finitely many rounds.

We claim that the resulting matching is in the core. We have show that the serial dictatorship algorithm generates matchings in the core.
TTC results in core allocation for the same reason. Theorem: a top trading cycle (TTC) algorithm always result in a core allocation.
Proof by contradiction:
Suppose that we find a coalition that can reshuffle objects such that everyone in the coalition becomes better off. Note that the coalition
reshuffles the initial endowment. For example, let agents 1, 3, and 4 be in the coalition S. We cannot improve the wellbeing of agent 4.
When agent 4 pointed to object 5, everything allocated in the previous round (i.e. object 2 in this case), is unavailable. Every object
allocated before round 2 is not in the endowment of S because it left earlier. This means that agent 4 received an object that is at least
weakly better than any object owned by S, i.e. μ_0(S). Specifically, agent 4 chose object 5 when objects 1 and 3 are available. He also
likes object 5 more than his initial endowment (i.e. object 4) because he did not leave in the first round. Thus, giving agent 4 any
endowment of S would make him weakly worse off. We have arrived at a contradiction and therefore μ is in the core.
General proof by contradiction:
Suppose that we find a coalition S such that there is a matching μ‘ for the problem S, μ_0(S) where for player i in S, μ‘(i) is better than μ(i).

We can then pick the agent in S who left the algorithm first (this agent may not be unique since it is possible that more than one agent in
S left at the same round; in this case, we can just pick any agent with this property). Suppose this agent is agent j, who left at round k. In
order to improve agent j’s wellbeing, we need an object μ’(i) to be one that has been allocated before round k. However, if the object
μ‘(i) was allocated before round k, then, by definition, this object must belong to some player in S. Then, agent j cannot be the first agent
who left the algorithm among S. We arrive at a contradiction and therefore any matching generated by TTC is in the core.

Note that every core allocation in this game is Pareto efficient. However, in this problem, not every Pareto efficient allocation is in the
core. This is because some Pareto efficient allocations are in conflict with the property rights for the agents. Those allocations are going
to take away someone’s endowment and replace it with something worse. It can be a Pareto efficient allocation but it is not in the core
because the player who had his endowment replaced by something worse would deviate to be a singleton coalition such that he keeps
his endowment.

Example 4: One-to-One Two Sided Matching

We can think of this problem as a marriage market. Consider a collection of agents who are split into two subgroups, namely, men and
women. The task is to match men to women in a one-to-one-fashion. To be in the core, the matching needs to be such that there is no
coalition of men and women who can all become better off by reshuffling the matching within that coalition.

Set Up
Suppose that there are two sides of the marriage market:

The market does not have to be balanced (i.e. k does not have to be equal to q). Each player has preference over the other side of the
market and him/herself (i.e. an player may prefer to be single than to be matched). If player i who is a man, his preference is over the set
W union {i}. If player i is a woman, her preference is over the set M union {i}. Mathematically,

We can only match between men and women (i.e. cannot match two players of the same sex). This is a key difference between two-sided
matching and one-sided matching. Models of one-sided matching are more difficult because we cannot guarantee that the core is not
empty even in the simplest model. In contrast, the core in a two-sided matching is definitely not empty.

In this game, a matching is a function μ that maps M union W into M union W that satisfies the following properties:
• Property 1: For every male in M, his partner must be in the set W union {m}; for every female in W, her must be in the set M union {w}.
If the partner of woman w is w, then this women stays single. The same applies to man m.
• Property 2: for every player i who is not single, we must have μ(μ(i))=i. This means that the matching is one-to-one.

This function μ takes an agent as the input and give the partner of that agent as the output; i.e. if the input is m, then the output would
by μ(m).

Core
In this game, we can define the concept of pairwise stable matching, which is simpler than the core and yet is equivalent to the core.

A pair (m, w) blocks the matching μ if

1. m is not matched to w in the matching μ,
2. m is better than the current partner of w, denoted by μ(w), from the point of view of w, and
3. w is better than the current partner of m, denoted by μ(m) from the point of view from m.
In other words, the pair (m, w) blocks μ if
1. m and w and not married to each other, and
2. Both of them can be better off if they leave their current partners and make a new marriage (i.e. both m and w prefers each other to
their current partner).

The matching μ is individually rational if the partner of agent i is weakly better than being single for all agent i. This property says that for
μ to be individually rational, we cannot force someone to marry someone if that person prefers to stay single. Mathematically, μ is
individually rational if

A core in this problem is a matching μ such that we cannot find a coalition S for which agents in S can all become better off by reshuffling
their marriage in comparison to μ. A matching is stable or pairwise stable if it is individually rational and if there there exists no blocking
pair. The definition of a pairwise stable matching is similar to that of a core. The definition requires μ to be immune to deviations to some
coalitions, but we can restrict the size of the coalitions. Specifically, if μ is individually rational, the coalition of a single player cannot split
off. If there is no blocking pair, we cannot find a coalition of two players, one on each side of the market, such that they can split off and
remarry within the coalition. Thus, for a pairwise stable matching, we restrict attention to coalitions of size one and two, whereas for a
core, coalitions of any size other than the grand coalition cannot deviate.

The definition of a core is equivalent to the definition of a pairwise stable matching. The reason is that agents’ preferences are over the
actions of the coalition. Agents care only about the identify of their partner and they do not care about who else is out there and what
others are doing. This means that if we can find a coalition that deviates and remarries, it is necessary that inside that coalition, there is a
blocking pair. Then, we can restrict attention to that blocking pair and ignore everyone else in that coalition. Therefore, we use the
definition of a pairwise matching to solve the problem.

Such a game can have multiple stable matchings, but finding all of them is computationally intensive in general. Instead, we find some
stable matchings using the deferred acceptance algorithm (DAA). We first look at men proposing deterred acceptance algorithm
(MPDAA).
1. Men rejected in the previous round (except for in the first round) make proposals to their favorite women who have not rejected
them yet. Proposals that were not rejected in the prior round carry over to the next round.
2. Women reject all but their favorite proposal. If a woman receives a better proposal, she can reject the proposal that she has accepted
in the previous round and accept the better proposal.
3. Repeat steps 1 and 2 until no rejection is made within a round.

Suppose there are four men (a b c d) and four women (w x y z). The RHS table shows the preference of each agent. For example, b
prefers x to w, w to y, and y to z. The LHS table shows the different rounds of the algorithm.

Round 1:
• In the first, round, each man propose to their favorite women (represented by the dashed lines).
• w receives three proposals, she accepts her favorite one, which is the one made by a and rejects c and d. The pair (a, w) is represented
by the solid line.
• x receives only one proposal, so she accepts it. The pair (b, x) is represented by the solid line.
• y and z do not receive any proposal.

Round 2:
• We obtain a matching, which is represented by the solid lines.

We claim that this matching is stable. The example is symmetric in terms of the sides of the market. Rewriting this algorithm as women
proposing deterred acceptance algorithm (WPDAA) would also give a stable matching. Both MPDAA and WPDAA would give a stable
matching.
WPDAA using same preferences as above gives the following.

Note that the two resulting matchings are different.

Properties of matchings generated by DAA:

1. DAA always generate stable matchings.
2. All men would refer MPDAA and all women would prefer WPDAA.
A. A general result is that the matching generated by MPDAA is the best matching for every man out of the entire set of stable
matchings. The same applies to every woman.
B. The implication is that if the matching generated by MPDAA and WPDAA are the same, we can conclude the in this problem,
there is only one unique stable matching. This is because the matching the both the best and the worst for men and women,
therefore it is the unique stable matching. This implication is useful if we want to know whether a matching is unique for a
particular problem.
3. If an agent is unmatched in a stable matching, we know that this agent would be unmatched in all stable matchings.

Proof of property 1:
To prove property 1, we need to prove two statements:
1. DAA produces matching that is individually rational (IR).
2. DAA produces matching that is not blocked by any pair.

Suppose that DAA generates the matching μ.

Statement one: μ is IR.

IR requires every player in that matching who is matched with someone else to prefer his partner to being single. We need to show that
DAA would generate a matching in which someone is matched with a partner who is worse than being single. We start with men. Men
would not be matched to partners who, from the point of view of men, are worse than being single because once men reach a point at
which every partner down the road is worse than being single, they would make a proposal to themselves and would never get rejected
it. Thus, men are going to be matched only with women who are better than being single. The similar logic applies to women. If someone
is worse than being single makes a proposal to a woman, she can reject that person. In short, men never propose to “unacceptable”
partners and women always reject “unacceptable” partners. A partner is acceptable if being matched to that partner is better than being
single; vice versa. Therefore, μ is IR.

Statement two: μ is such that there exists no blocking pair (m, w).
Proof by contradiction:
Suppose that (m, w) is a blocking pair. This means that m is not matched to w in μ, m is better than w’s current partner from the point of
view of w, and w is better than m’s current partner from the point of view of m. Mathematically, a matching pair is defined as

Suppose we are using the MPDAA. We want check if can happen. Woman w is better than μ(m) means that in the course
of the algorithm, m would propose to w before he proposes to μ(m). Man would propose to μ(m) only if he is rejected by w.

Now, w would reject m only if she has received a better proposal from someone else, say m’, i.e. If this is the case, the
only way that the proposal did not work out is that w rejected m’. If w never rejected m’, m’ would not be able to make any other
proposal and w and m’ would be matched in μ. Thus, it is either that m’ = μ(w) or μ(w) at least weakly better than m’, i.e.
Since m’ is better than m from the perspective of w, it follows that μ(w) must be strictly better than m, i.e. We arrival at
a contradiction because m must be better than μ(w) for (m, w) to be a matching pair that blocks μ.
We can do the same for WPDAA and we would get the same proof and result. Since we have proved both statements, we have shown
that DAA produces stable matchings and we are guaranteed to obtain matchings that are in the core.

Proof of property 2:
Theorem: Let μ_DAA be the matching produced by MPDAA. Then, for any μ that is stable and for any m in M: μ_DAA(m) is weakly better
than μ(m); and for any w in W: μ_DAA(w) is weakly worse than μ(w). The opposite applies to the matching produced by WPDAA.

We first introduce the concept of unachievable pair. A pair (m, w) is achievable if there exists a stable matching μ such that m and w are
matched together, i.e.

To prove property 2, we first prove the following claim. In we run a DAA, man m would never be rejected by w if (m, w) is achievable.
This claim implies the first line of the theorem:

Consider a man m with some ranking w_1, w_2, w_3, ..., w_4 (i.e. this is the preference for m). We can go through all possible stable
matchings and highlight all women who can form an achievable pair with m.

Suppose that for now, we take the claim as given. If we run the DAA, m would first propose to his favorite woman, w_1. Since w_1 is not
highlighted, she would eventually reject m because otherwise, they would be matched together at the end of the algorithm. This, along
with the fact that DAA always generates stable matching, imply that (m, w_1) would form a achievable pair, which cannot be the case.
Then, m would go to w_2, who is achievable. Given that the claim is true, m would never by rejected by w_2. Therefore, in the DAA, m
and w_2 would be matched. Then, μ_DAA(m) = w_2 and w_2 is at least weakly better than all μ(m) (i.e. all women highlighted) because m
proposes in the order of his ranking. Therefore, we can prove the property if we can prove the claim.

Proof by contradiction and induction:

By contradiction, suppose that a man may be rejected by a woman of whom he forms an achievable pair.
By induction, suppose that this occurs for the first time at round k. Let (m, w) be a achievable pair and suppose that m is rejected by w.
The only reason for w to reject m is that she receives a proposal from m’ in round k who, from the point of view of w, is better than m.
Since (m, w) is an achievable pair, there exists a stable matching μ such that μ(m) = w. The question is, who is matched to m’ in the
matching μ? Suppose that μ(m’) = w’. Then, the pair (m’, w’) is achievable. This means that m’ was not rejected by w’ in all the rounds up
to round k because round k is the first round at which the achievable pair (m’, w’) gets split up. Since m’ was not rejected by w’ and since
at round k, m’ makes the proposal to w, it must be that from the point of view of m’, w is better than w’. We can write the preferences of
follows:

If we look at these statements, we would realize that the statements imply (m’, w) forms a blocking pair of the matching μ. However, by
assumption, μ is a stable matching. Therefore, we have arrived at a contradiction and we have proved that no man would be rejected by
a woman who forms a achievable pair with that man. Therefore, we have shown that MPDAA generates the best stable matching for all
man.

We also need to prove the second part of the theorem:

Proof by contradiction:
By contradiction, suppose that there exists a woman w and a stable matching μ such that μ_DAA(w) = m is better than μ(w) from the
point of view of w. We claim that (m, w) blocks μ. This is because m is preferred to μ(w) from the point of view of w and w is also
preferred to μ(m) from the point of view of m. We know that m prefers w to μ(m) because
This would hold as an equality only if μ_DAA(m) = μ(m), i.e. m with matched with w in μ_DAA and μ. But this cannot be the case because
of the inequality
Therefore, m is better than μ(w) and w is better than μ(m) from the point of view of w and m respectively, i.e.

This satisfies the definition of a blocking pair and we arrive at a contradiction. Thus, the second part of the theorem also holds.

This concludes the proof for the theorem (i.e. property 2).

This property is a corollary of a more general result, which is the lattice theorem. This is beyond the scope of the course.
 ECON0027 Lecture notes
Section 6: Cooperative game theory. Matching.
Reading: Osborne: Ch 8

• Non-cooperative game: agents act in an uncoordinated manner

• Cooperative game: many agents, coordination is allowed, but agents are still rational, i.e.
maximize their own payo↵

• Models: housing allocation, school choice, matching medical doctors to hospitals, etc.

• Allocation mechanisms: serial dictatorship, top trading cycles, deferred acceptance algo-
rithm

6.1 A cooperative game

• A set of players N

• A set of coalitions 2N (N is called a grand coalition)

• A set of actions coalitions can take

• Each player i has a preference relation defined on the set of action profiles

6.2 Example: a transferable utility (TU) game in characteristic form

• A set of players N = {1, ..., n}

• Characteristic function (value of a coalition) v : 2N ! R

P
• An action coalition S can take is a division of surplus of this coalition: xi = v(S).
i2S

• Player i’s preferences: x ⌫i y i↵ xi yi .

1
6.3 Example: marriage market (NTU)
• A set of players N = M [ W = {m1 , ..., mn , w1 , ..., wk }

• A matching µ : N ! N such that

– for any m 2 M : µ(m) 2 W [ m

– for any w 2 W : µ(w) 2 M [ w
– for any z 2 N : µ(µ(z)) = z

• Action a coalition S can take is a matching defined on set S.

• Preferences:

– any man m has strict preferences over the set W [ m

– any woman w has strict preferences over the set M [ w
– therefore, any agent z (either man or a woman) has preferences over the set of match-
ings:
µ z µ0 () µ(z) z µ0 (z)

6.4 Intuition for a solution

• An idea is to allow agents to take joint actions, i.e. to coordinate within coalitions...

• and look for “stable” outcomes: the outcomes that are immune to coalitional deviations

• an outcome is immune to coalitional deviations if any deviation is either unfeasible or not

profitable

6.5 Core
An action of a grand coalition y is in the core if there exists no coalition S and action x that
this coalition can take such that for all i 2 S : x i y.

6.6 TU game in characteristic form

A core is nonempty i↵ a game is balanced, i.e. if there exists ↵ : 2N \ ; ! [0, 1] such that
P
1. for all i 2 N : ↵(S) = 1
S22N :i2S
P
2. ↵(S)v(S)  v(N )
S22N

2
6.7 An example
• A set of players N = {1, 2, 3}
• A characteristic function v(N ) = 5, v(C) = |C| if C 6= N .
• This game is symmetric because v(C1 ) = v(C2 ) for all C1 and C2 such that |C1 | = |C2 |
• For symmetric games the previous nesessary and sufficient condition simplifies to

v(N ) v(C)
8C ⇢ N :
|N | |C|

• Graphic representation of a core:

6.8 Another example

• A set of players N = L [ R, where |R| = |L| 1
• A characteristic function v(S) = min{|S \ L|, |S \ R|}
• The interpretation is that each pair that consists of one agent from L and one agent from
R can produce one unit of consumption good.
• The core of this game consists of a single outcome: Agents in R get 1 and agents in L get
0.
• There is an excess supply of agents in L, so their ”price” is zero, just as in the competitive
outcome
• This is not a coincidence: competitive equilibrium is always in the core if there are no
complementarities on either side of the market (more on this later)

6.9 Mergers in a cournot competition model

• A set of firms N = {1, ..., n}
• Demand is P = A Q. No costs
• In a coalition, firms agree on a joint output and share a profit (not necessarily equaly)
• Since there are no costs, a coalition of firms can be viewed as a single firm (a merger)
• Grand coalition: monopoly. qm = A/2 and ⇡m = A2 /4
• Suppose a coalition C decides to break away and be independent: there are two ”firms”
in the economy and each will produce qN = A/3 and ⇡N = A2 /9

3
6.10 Mergers in a cournot competition model (cont.)
• A characteristic function v(N ) = A2 /4, v(C) = A2 /9 for any C 6= N

• The core is nonempty if for any C ⇢ N

v(N ) v(C)
n |C|

• The tightest inequality is for |C| = 1, i.e.

A2 A2
4n 9
or, equivalently n < 2.25

• If n = 2 the core consists of outcomes in which each firm gets a profit of at least A2 /9 and
the sum of profits is A2 /4

6.11 NTU
• In previous models agents were distributing joint surplus

• In NTU models, roughly speaking, there is no money...

• Examples: kidney exchange, school choice, public housing

6.12 Allocation of public housing

• A set of agents N

• A set of houses H

• Each agent has strict preferences over the set of houses: i

• No transfers allowed

• The task is to have a mechanism that allocates houses

• Desired properties: stability (the allocation should be in the core), Pareto-efficiency, strat-
egy proofness

4
6.13 Serial dictatorship
• Suppose houses are unassigned from the very beginning
• Serial dictatorship algorithm:
– Order agents (randomly or not)
– Starting from the top, let agents pick their best house from the ones that are still
available
SD outcome is Pareto efficient, but not fair (ex post). SD is strategy proof

6.14 Serial dictatorship is Pareto efficient

The outcome is Pareto efficient if you cannot improve the well being of any agent without
making some agent worse o↵.
Theorem 1. 1. The outcome generated by serial dictatorship is Pareto efficient.
2. Any Pareto efficient outcome can be generated by a serial dictatorship mechanism.
Proof:
By contradiction, suppose it is not. There exist a person a1 whose well being can be improved
by awarding him a house h1 that was unavailable to him (if it were available he would have picked
it). Suppose h1 was awarded to an agent a2 by the mechanism. There two cases: (1) h1 is the
best house from the point of view of a2 or (2) otherwise. In case (1) we arrive at contradiction
because we cannot improve the well being of a1 without making a2 worse o↵. In case (2) we
can improve the well being of a2 by awarding him a house h3 that was unavailable to him. It
is easy to see that if we continue the chain of improvements, eventually we will arrive at the
contradiction because at least one person, the one who was ranked first by the mechanism,
received his first best choice.
Lemma 1. For any Pareto efficient allocation there is at least one person who is allocated his
first best choice.
Proof: Indeed, suppose by contradiction that no such agent exists. Draw a graph in which
each agent i points towards another agent j who is allocated i’s first best choice. There is a
cycle in such a graph (this cycle is called trading cycle). Allowing agents to trade their objects
along the cycle is a pareto improvement hence the contradiction.
Take a Pareto efficient allocation.
1. Select all agents who receive their first best choice (you can always do that by lemma
above) and assign them top ranks (in an arbitrary manner).
2. Remove them and their objects from the problem. The new allocation is also Pareto
efficient.
3. Repeat 1-2 until no agents left
4. Applying SD with the resulting ranking will obtain the allocation in question

5
6.15 Serial dictatorship is strategy proof
The mechanism is strategy proof if reporting your preferences is a weakly dominant strategy.

Theorem 2. Serial dictatorship is strategy proof.

Proof: Any agent essentially picks his best object out of available ones. Misreporting pref-
erences will have no e↵ect on the set of available objects.

6.16 Top trading cycles

• Solve the same allocation problem...

• but with agents initially owning some objects

• Applications: donor organs (kidney exchange)

1. Objects point to their owners

2. Agents point to their top choice

3. Find cycles and execute the trade along these cycles

4. Remove agents who traded in the cycles and repeat 1-4 until no agents left

The outcome generated by TTC is pareto efficient. TTC is strategy proof

6.17 TTC outcome is Pareto efficient

Theorem 3. The outcome generated by TTC is Pareto efficient and is in the core.

Proof: A Pareto improvement represents a trading cycle: agents a1 , ..., am exchange their
houses in such a way that everyone is better o↵. Suppose by contradiction, that this trading
cycle is not a top one. Then, it must be that some participants of this cycle traded earlier in the
mechanism and left the market with some house assigned. Since the mechanism requires them
to point to their best option available, they left with something better than what is o↵ered in
the pareto improving trading cycle which is a contradiction.

6.18 TTC is strategy proof

Theorem 4. TTC is strategy proof.

Proof: Agents who trade in the first TTC don’t want to misreport their preferences because
they can get their first best choice. Agent’s who trade in the k’th TTC don’t want to misrepresent
their preferences because they cannot alter the outcome of any previous TTC and therefore they
get their best choice out of the available ones.

6
6.19 Marriage market

Extra reading: D. Gale and L. S. Shapley: ”College Admissions and the Stability of
Marriage”, American Mathematical Monthly 69, 9-14, 1962.

1. Two-sided matching: men on one side and women on the other

2. Similar to allocation problem but now both sides have preferences

3. The task is to have a mechanism that matches agents in pairs

4. Desired properties: stability (the allocation should be in the core), Pareto-efficiency, strat-
egy proofness

6.20 Setup
• A set of players N = M [ W = {m1 , ..., mn , w1 , ..., wk }

• A matching µ : N ! N such that

– for any m 2 M : µ(m) 2 W [ m

– for any w 2 W : µ(w) 2 M [ w
– for any z 2 N : µ(µ(z)) = z

• Preferences:

– any man m has strict preferences over the set W [ m

– any woman w has strict preferences over the set M [ w
– therefore, any agent z (either man or a woman) has preferences over the set of match-
ings:
µ z µ0 () µ(z) z µ0 (z)

6.21 Example

m1 m2 w1 w2
w1 w2 m2 m1
w2 m2 m1 w2
m1 w1 w1 m2

7
6.22 Stable matchings
• A pair m, w is a blocking pair for matching µ if

µ(m) 6= w, w m µ(m) and m w µ(w)

• A matching µ is stable if it is individually rational, i.e. 8z 2 N : µ(z) ⌫z z, and there

exists no blocking pairs.

Theorem 5. A matching is stable i↵ it is in the core.

Proof: The only thing that matters for an agent is his/her match. Therefore if there is a
matching µ that blocks another matching µ0 there must be at least one blocking pair.

6.23 Example

m1 m2 w1 w2
w1 w2 m2 m1
w2 w1 m1 m2
m1 m2 w1 w2

6.24 Deferred acceptance algorithm

1. Start with all men proposing to their top choice

2. Each woman selects a top man out of the ones that proposed to her, tentatively accepts
his proposal and rejects the rest

3. All men that were rejected at the previous stage propose to their top choice out of all
women who did not yet rejected them.

4. Each woman selects a top man out of the ones that proposed to her (including the one
who holds a tentative acceptance from this woman), tentatively accepts his proposal and
rejects the rest

5. Repeat 3-4 until no man is rejected. Finalize the resulting tentative acceptances into a
matching.

6.25 Example: preferences

a b c d w x y z
w x w w b a a b
x w z y a b b a
y y y z c c c d
z z x x d d d c

8
6.26 Example: Men-proposing DAA

round 1 round 2
a w a w
b x b x
c y c y

d z d z

6.27 Example: Women-proposing DAA

round 1 round 2 round 3

a w a w a w
b x b x b x
c y c y c y

d z d z d z

6.28 Properties
1. Stability

2. Pareto efficiency

3. One-side strategy proofness

4. The best stable matching for all men, the worst stable matching for all women

6.29 Stability
Theorem 6. A matching generated by DAA is stable

Proof: Start with observing that this matching is IR. By contradiction, assume that there
is a blocking pair m, w. Since w m µ(m), m must have proposed to w and been rejected. If
w rejected m, at round k, it must be that she did so in favor of some m0 w m. At the later
rounds she could either keep m0 or reject him in favor of even better candidate. Therefore,
when the algorithm stopped, w must have been matched to someone at least as good as m0 , i.e.
µ(w) ⌫w m0 w m which is a contradiction.

Corollary 7. A matching generated by DAA is Pareto efficient

9
6.30 DAA is the best for all men
Theorem 8. Take any stable matching µ. For any man m : µDAA (m) ⌫m µ(m) and for any
woman w : µ(w) ⌫w µDAA (w).

Proof:

• Define (m, w) to be achievable for each other for if they are paired in some stable matching.
Show that in men-proposing DA, with strict preferences, no man is ever rejected by an
achievable woman. (This implies the theorem)

• Assume that up to a given round no man has been rejected by an achievable woman.
Suppose at that round a man m is rejected by an achievable woman w who chooses m0 .
We know that m0 prefers w to any women, except for those who previously rejected him,
and all these women are unachievable (Why?).

• Since (m, w) are achievable for each other, there exists a stable matching µ pairing them.
In that matching, say µ(m0 ) = w0 . Clearly, w0 is achievable for m0 , so m0 must prefer w to
w0 . Hence (m0 , w) blocks µ, so µ cannot be stable... contradiction

6.31 Rural hospital theorem

Theorem 9. The set of men and women who are unmatched is the same in all stable matchings.

Proof:

• Consider the man-optimal stable matching and some other stable matching.

• Any man who is matched in the other matching, must be matched in the man-optimal
matching, so at least as many men are matched in the man-optimal.

• Any woman matched in the man-optimal matching must be matched in all other stable
matchings.

• In any stable matching, the number of matched men just equals the number of matched
women.

• So the same set of men and women are matched in the two matchings, although di↵erent
pairings.

6.32 One-sided strategy proofness

Theorem 10. There exists no mechanism that is two-sided strategy proof.

Proof:
m1 : w 1 > w2
m2 : w 2 > w1
w 1 : m2 > m1
w 2 : m1 > m2

10
Theorem 11. A matching generated by DAA is strategy proof for men, i.e. reporting the true
preferences is a weakly dominant strategy for men.

Proof:

• Fix the reports if all the women and all but one man. Show that whatever report the man
m starts with, he can make a series of (weak) improvements leading to a truthful report.

• Suppose man m is considering a strategy that leads to a match µ where he gets w. Each
of the following changes improves his outcome

• Reporting that w is his only acceptable woman: µ is still unblocked. By RHT, m must
get matched, and so must get w.

• Reporting honestly, but truncating at w: m being unmatched is still blocked (because it

was blocked if m reported just w), so m must do at least as well as w.

• Reporting honestly with no truncation: This won?t a↵ect DA relative to above strategy.

6.33 Generalizing DAA to many-to-one matching

1. Two-sided many-to-one matching: colleges on one side and students on the other

2. Both sides have preferences

3. A college can accept more than one student. Each college c has a fixed number of seats sc

The algorithm can be modified as follows:

1. Start with all students apply to their top choice

2. Each college c selects sc top candidates out of the ones that applied to it, tentatively
accepts their applications and rejects the rest

3. All students that were rejected at the previous stage apply to their top choice out of all
colleges where they were not yet rejected

4. Each college c selects sc top candidates out of the ones that applied (including the ones
who hold a tentative acceptance from this college), tentatively accepts their applications
and rejects the rest

5. Repeat 3-4 until no student is rejected. Finalize the resulting tentative acceptances into a
matching.

11