Chapter 8 Matching Markets

Let us now return to the housing allocation example from the introduction and to the bipartite matching problems we considered in chapter 6. Consider the bipartite graph in Figure 8.1 (which is the same one we considered in the introduction) where we have a set of three people ( $A$ , $B$ , and $C$ ) on the left side and a set of three houses ( $H_{1}$ , $H_{2}$ , and $H_{3}$ ) on the right side, and interpret the existence of an edge between an individual and a house as saying that the individual finds the house acceptable.

**Figure 8.1:** A basic example of a matching problem between people and houses.

Using the maximum matching algorithm described in chapter 6, we can find the largest set of players that can be “matched” (i.e., allocated) to a house that they find acceptable (specifically, one such maximum matching would match $A$ to $H_{2}$ , $B$ to $H_{1}$ , and $C$ to $H_{3}$ ). But, in such matchings, we are only guaranteed that the people get some house they find “acceptable.” In reality, however, people have preferences over houses; we may represent these preferences by specifying, for each player, an (individual) valuation for each house. Additionally, houses are typically not free; we may thus also associate prices with each house, and define a player’s utility for a house as their valuation for the house minus the price they would have to pay for it. We refer to such a situation as a matching market. In this chapter, we investigate how correctly set prices—so-called market-clearing prices—can be used to ensure that not only all buyers get allocated a house, but they also end up with their most preferred allocation.

8.1 Definition of a Matching Market

We turn to formalizing the general matching market problem. Given a set of players (buyers) $X = [n]$ and a set of $n$ items (houses) $Y$ :

we associate with each player (buyer) $i \in X$ , a valuation function $v_{i} : Y \to ℕ$ .¹ For each $y \in Y$ , $v_{i} (y)$ determines $i$ ’s valuation for item $y$ (independent of its price).
we associate with each item $y \in Y$ , a price $p (y) \in ℕ$ .
a buyer $i$ who receives an item $y$ gets utility $v_{i} (y) - p (y)$
(that is, the valuation it has for the item, minus the price it needs to pay); buyers who do not get any item get utility 0.

For simplicity of notation, we restrict to the case when $| X | = | Y |$ , but the more general case can be reduced to this special case by either adding “dummy buyers” (who value all items at 0) or adding “dummy items” (with value and price 0).

Definition 8.1. We refer to the tuple $Γ = (n, Y, \vec{v})$ , where $n \in ℕ$ , $| Y | = n$ and $\vec{v}$ is a vector of functions such that for all $i \in [n], v_{i} : Y \to ℕ$ , as a matching market.

Given a matching market $Γ = (n, Y, \vec{v})$ , we are interested in studying different allocations of items $y \in Y$ to players $i \in [n]$ such that each item gets allocated to at most one player (or remains unallocated). In other words, an allocation is a matching in the complete bipartite graph over players, $[n]$ , and items, $Y$ . (Recall that in a complete bipartite graph, the edge set is the full set of all possible edges, so that all allocations are possible.)

Definition 8.2. An allocation, or matching, $M$ for a matching market $Γ = (n, Y, \vec{v})$ is a matching in the complete bipartite graph over $[n] \cup Y$ .

Recall that such a matching can be specified as a function $M : [n] \to Y \cup {⊥}$ such that $M (i)$ specifies the assignment of player $i$ (or $⊥$ if $i$ is unmatched). In the rest of this chapter, we will rely on this way of specifying the matching. Note that if $M$ is a perfect matching, then for all $i \in [n], M (i) \neq ⊥$ (i.e., all players get allocated some item).

An outcome of a matching market specifies the allocation $M$ as well as prices for all the items $y \in Y$ ; we specify these prices through a price function $p : Y \to ℕ$ , where for every $y \in Y$ , $p (y)$ specifies the price for item $y$ :

Definition 8.3. Given a matching market $Γ = (n, Y, \vec{v})$ , we refer to the pair $(M, p)$ as an outcome of $Γ$ if $M$ is an allocation for $Γ$ and $p$ is a function $p : Y \to ℕ$ .

8.2 Acceptability and Preferred Choices

Given a matching market $Γ$ and a price function $p$ , we say that item $y$ is acceptable to buyer $i$ if $v_{i} (y) \geq p (y)$ (i.e., buyer $i$ has value for item $y$ that is at least its price). We can now define the “acceptability graph” induced by $Γ$ and $p$ .

Definition 8.4. Given a matching market $Γ = (n, Y, \vec{v})$ and a price function $p : Y \to ℕ$ , we define the induced acceptability graph $G = ([n] \cup Y, E)$ , where $(i, y) \in E$ if and only if $y$ is acceptable to $i$ .

The fact that $y$ is acceptable to $i$ does not imply that $i$ prefers $y$ over all other items; we say an item $y$ is a preferred choice for $i$ if $y$ is acceptable to $i$ and $y$ maximizes $v_{i} (y) - p (y)$ over all items in $Y$ —that is,

v_{i} (y) - p (y) = max_{y^{'} \in Y} v_{i} (y^{'}) - p (y^{'}) .

Note that there may not necessarily exist a unique preferred choice for all buyers; for instance, two items could have the same valuation and price.

The notion of a preferred choice allows us to construct a different bipartite graph:

Definition 8.5. Given a matching market $Γ = (n, Y, \vec{v})$ and a price function $p : Y \to ℕ$ , we define the induced preferred choice graph as $G = ([n] \cup Y, E)$ , where $(i, y) \in E$ if and only if $y$ is a preferred choice to $i$ .

See Figure 8.2 for an illustration of induced acceptability and preferred choice graphs. We can easily guarantee a perfect matching in the acceptability graph by making all items free ( $p (y) = 0$ for all $y \in Y$ ), since then every item would be acceptable to every buyer (so we can just give the item with index $i$ to buyer $i$ ). Can we also set prices so that everyone ends up with an outcome they are the most happy with (and not just find acceptable)? That is, can we set prices so that there exists a perfect matching in the preferred choice graph (and thus everyone ends up with their preferred choice)? The notion of a market equilibrium addresses this.

Definition 8.6. Given a matching market $Γ = (n, Y, \vec{v})$ , we say that an outcome $(M, p)$ is a market equilibrium (or Walrasian equilibrium) if $M$ is a perfect matching in the preferred choice graph induced by $Γ$ and $p$ .

The reason we call such a pair, $(M, p)$ , an equilibrium is that in it, no buyer $i$ prefers to switch to a different item $y^{'} \neq M (i)$ (as they are receiving their “preferred choice”) or to not buy their assigned item $M (i)$ (as they are receiving non-negative utility for it).

For a given matching market $Γ$ , prices $p$ are called market clearing if there exists some market equilibrium of the form $(M, p)$ for $Γ$ .

8.3 Social Optimality of Market Equilibria

As we now show, market equilibria are socially optimal outcomes. To formalize this, define the social value of an allocation $M$ in a matching market $Γ$ as

S V^{Γ} (M) = \sum_{i \in [n], M (i) \neq ⊥} v_{i} (M (i)) .

Note that this notion of social value only takes into account the value the buyers have for the items; in other words, we are implicitly assuming the seller has no value for the items.² Also, note that the social value is different from the sum of buyers’ utilities, as it considers only the value the buyers get from the items, but without considering the prices they need to pay for them. However, it is not hard to see that the social value of an assignment actually equals the social welfare of all players (i.e., if we consider the utility of both the buyers and the seller) no matter what the prices are, if we define the utility of the seller to be the sum of the prices paid by the buyers. More precisely, define $S W^{Γ} (M, p)$ as the sum of the buyers’ utilities + the seller’s utility; namely:

S W^{Γ} (M, p) = \sum_{i \in [n], M (i) \neq ⊥} (v_{i} (M (i)) - p (M (i))) + \sum_{i \in [n], M (i) \neq ⊥} p (M (i)) .

As the prices $p (M (i))$ cancel out in the expression, it simplifies to just

\sum_{i \in [n], M (i) \neq ⊥} v_{i} (M (i)) = S V^{Γ} (M) .

We thus conclude the following claim:

Claim 8.1. For any matching market $Γ = (n, Y, \vec{v})$ , any prices $p : Y \to ℕ$ and any allocation $M$ for $Γ$ , we have that

S W^{Γ} (M, p) = S V^{Γ} (M) .

We say that an allocation $M$ maximizes social value if $S V^{Γ} (M) = max_{M^{'}} S V^{Γ} (M^{'})$ where the $max$ is quantified over all allocations $M^{'}$ for $Γ$ . Similarly, an allocation $M$ and and prices $p : Y \to ℕ$ maximize social welfare if $S W^{Γ} (M, p) = {max}_{M^{'}, p^{'}} S W^{Γ} (M, p^{'})$ (where again the $max$ is defined over allocations $M^{'}$ and prices $p^{'}$ for $Γ$ ). By Claim 8.1, we directly have the following corollary.

Corollary 8.1. For any matching market $Γ = (n, Y, \vec{v})$ , an allocation $M$ maximizes social value if and only if $(M, p)$ maximizes social welfare for any (or every) $p$ .

Thus, if we have an outcome that maximizes social value, then social welfare will be maximized regardless of how we set prices. Let us now use this observation to show that any market equilibrium maximizes social welfare.

Theorem 8.1 (Social optimality of market equilibria). Given a matching market $Γ$ and a market equilibrium $(M, p)$ for $Γ$ , we have that $M$ maximizes social value.

Proof. Consider some market equilibrium $(M, p)$ for $Γ$ ; we aim to show that $M$ maximizes social value. Toward this, consider some (potentially other) assignment $M^{'}$ that maximizes social value for $Γ$ . By Corollary 8.1, $(M^{'}, p)$ also must maximize social welfare (in fact, $(M^{'}, p^{'})$ maximizes social welfare for any $p^{'}$ ). Since $M$ is a perfect matching in the preferred-choice graph, by assumption, every buyer must receive an item that maximizes their utility given the prices (and which gives them non-negative utility). In particular, for all $i \in [n]$ (letting $v_{i} (⊥) = 0$ and $p (⊥) = 0$ to deal with the fact that $M^{'}$ may leave some players unassigned), we have:

v_{i} (M (i)) - p (M (i)) \geq v_{i} (M^{'} (i)) - p (M^{'} (i)) .

And thus, the buyers’ combined utilities are at least as high in $M$ as in $M^{'}$ :

\sum_{i \in [n], M (i) \neq ⊥} (v_{i} (M (i)) - p (M (i))) \geq \sum_{i \in [n], M^{'} (i) \neq ⊥} (v_{i} (M^{'} (i)) - p (M^{'} (i))) .

Additionally, since in $M$ all items are assigned to some buyer, we have that

\sum_{i \in [n], M (i) \neq ⊥} p (M (i)) = \sum_{y \in Y} p (y) \geq \sum_{i \in [n], M^{'} (i) \neq ⊥} p (M^{'} (i))

and thus the seller’s utility is also at least as high in $M$ as in $M^{'}$ . We thus conclude that

S W^{Γ} (M, p) \geq S W^{Γ} (M^{'}, p) .

It follows that $(M, p)$ must also maximize social welfare, and then, by Corollary 8.1, we have that $M$ maximizes social value as desired.

■

Let us end this section by noting that whereas the proof of Theorem 8.1 is relatively simple, the fact that this result holds is by no means a triviality—we have already seen several examples of situations (e.g., coordination and traffic games) where equilibria lead to outcomes that do not maximize social welfare. Theorem 8.1 is an instance of what is known as the first fundamental theorem of welfare economics and a formalization of Adam Smith’s famous invisible hand phenomenon—that free markets lead to a socially optimal outcome as if guided by “unseen forces.”

8.4 Existence of Market Equilibria

So, given the awesomeness of market equilibria, do they always exist? In fact, it turns out that they always do! Thus, we can always set prices in such a way that (1) everyone gets one of their preferred choices, and (2) items are given to people in a manner that maximizes social value.

We now show that not only do market equilibria always exist, but they can also be efficiently found (relying on the material covered in chapter 6). This theorem is an instance of what is referred to as the second fundamental theorem of welfare economics.

Theorem 8.2. A market equilibrium $(M, p)$ exists in every matching market $Γ = (n, Y, \vec{v})$ . Additionally, there exists an efficient procedure that finds this equilibrium in polynomial time in $n \cdot v a l$ , where $v a l$ is an upper bound on the valuations of all players.

Proof. We present a particular price updating mechanism—analogous to BRD for games—which will converge to market-clearing prices. Start by setting $p (y) = 0$ for all $y \in Y$ . Next, iteratively update prices as follows:

If there exists a perfect matching $M$ in the preferred-choice graph, we are done and can output $(M, p)$ . Recall that by Theorem 6.2, this step can be performed efficiently.
Otherwise, by Theorem 6.3, there exists a constricted set of buyers $S \subseteq [n]$ (i.e., a set such that $| N (S) | < | S |$ ) in the preferred-choice graph; furthermore, recall that this constricted set may also be found efficiently.
Next, raise the prices of all items $y \in N (S)$ by 1.
If the prices of all items are now greater than zero, shift all prices downward by the same amount (i.e., 1, since we can only increase prices by 1 in any step) to ensure that the cheapest item has a price of zero.

**Figure 8.4:** The preferred-choice graphs for the intermediate states of the algorithm. Constricted sets are indicated by red edges.

(An example of the execution of this procedure can be found in Figures 8.3 and 8.4.) Clearly, if this procedure terminates, we have found a market equilibrium. Using a potential function argument, we can argue that the procedure does, in fact, always terminate (and thus always arrives at a market equilibrium):

For each buyer $i \in [n]$ , define $Φ_{i}^{B} (p)$ as the maximal utility buyer $i$ can hope to get for some item; that is, $max_{y \in Y} (v_{i} (y) - p (y))$ . (Note that if we have a perfect matching $M$ in the preferred-choice graph, then this is actually the utility buyer $i$ gets in $M$ . Also note that the “maximal utility” may be negative if all items are too expensive.)
Let $Φ^{B} (p) = \sum_{i \in [n]} Φ_{i}^{B} (p)$ be the sum of the potentials for all buyers.
Let $Φ^{S} (p) = \sum_{y \in Y} p (y)$ be the “maximal utility” the sellers can hope to get. (Again, note that this utility is attained in a perfect matching since all items are sold.)
Define the final potential as $Φ (p) = Φ^{B} (p) + Φ^{S} (p)$ .

Let us first show that the potential is always non-negative.

Claim 8.2. Consider a single iteration of the algorithm where prices get updated from $p$ to $p^{'}$ . Then $Φ (p^{'}) \geq 0$ .

Proof. First, note that prices start off non-negative (in fact, zero) and then can never become negative (in particular, we only ever decrease prices until the cheapest item is free). It thus follows that $Φ^{S} (p^{'}) \geq 0$ .

Next, since there always exists some item with price $0$ , we know that $Φ_{i}^{B} (p^{'}) \geq 0$ for every buyer $i$ , since $i$ may always obtain non-negative “potential utility” by going for this free item. So $Φ^{B} (p^{'}) \geq 0$ , and thus $Φ (p^{'}) \geq 0$ .

■

We next show that the potential decreases at every iteration of the algorithm.

Claim 8.3. Consider a single iteration of the algorithm where prices get updated from $p$ to $p^{'}$ . Then $Φ (p^{'}) < Φ (p)$ .

Proof. Recall that the algorithm first increases the price of the items in the neighbor set, $N (S)$ , of the constricted set, $S$ , by 1. This increases $Φ^{S}$ by $| N (S) |$ . But for each player $i \in S$ , it decreases $Φ_{i}^{B}$ by 1, since they now must pay 1 extra for their preferred item—we here rely on the facts that (a) since there exists some item with price 0, every player $i$ has at least one preferred item, thus $| N (S) | \geq 1$ , and (b) since valuations are integers, if we increase the prices of all preferred choices of $i$ by 1, the items will still maximize $i$ ’s utility among items $y \in Y$ (although there may now also exist other items that maximize $i$ ’s utility); thus, for all $i \in S$ , $Φ_{i}^{B}$ decreases by 1. For player $i \notin S$ , $Φ_{i}^{B}$ remains the same.

We conclude that $Φ^{B}$ decreases by $| S |$ , and thus in total $Φ$ changes by $| N (S) | - | S |$ . However, by the definition of a constricted set, $| S | \geq | N (S) | + 1$ , and so $Φ$ must decrease by at least 1 during this phase.

Next, if we shift all prices downward by one, $Φ^{S}$ will decrease by $n$ , but $Φ^{B}$ will increase by $n$ (by the same logic as above), and so the price shift step has no impact $Φ$ .

■

Finally, notice that, at the start, $Φ^{S} = 0$ and

Φ^{B} = \sum_{i \in [n]} {max}_{y \in Y} v_{i} (y) \leq n \cdot v a l,

where $v a l$ is any upper bound on the valuations of the players. So, by the above two claims, the procedure will terminate, and it will do so in at most $n \cdot v a l$ iterations.

■

8.5 Emergence of Market Equilibria

Tatonnement The above proof just shows that market-clearing prices (and hence market equilibria) always exist. But how do they arise in the “real world”? We can think of the process described above as a possible explanation for how they might arise over time. If demand for a set of items is high (there are too many people who prefer those items—that is, we have a constricted set in the preferred-choice graph), then it seems reasonable to assume that the market will adjust itself to increase the prices of those items.

The price shift operation, however, seems somewhat less natural. But it is easy to see that it suffices to shift prices downward whenever all items are too expensive for some buyer (in other words, when the potential utility of some buyer becomes negative) and thus we cannot sell everything off. In such a case, it may seem more natural for the sellers to decrease market prices (e.g., in a housing market, if too many houses remain for sale, the whole housing market starts going down).

In general, these type of market adjustment mechanisms, and variants thereof, are referred to as tatonnement (French for “groping”) mechanisms and have been the topic of extensive research. Whether market-clearing prices and equilibria actually do arise in practice (or whether, for example, conditions change faster than the tatonnement process converges to the equilibrium) is a question that has been debated since the Great Depression in the 1930s.

Buyer-optimal and seller-optimal market equilibria Let us remark that market equilibria are not necessarily unique. Some equilibria are better for the seller, whereas others are better for the buyers. To understand why this can happen, consider the (degenerate) special case of a single buyer and a single item for sale; if the buyer values the item at $v$ , then every price $\tilde{p} \in [v]$ can be sustained in an equilibrium $(M, \tilde{p})$ (where $M$ is the trivial matching where the buyer gets matched with the seller). In particular, setting the price $\tilde{p} = 0$ is clearly optimal for the buyer, whereas setting the price $\tilde{p} = v$ is optimal for the seller. A similar reasoning can be applied also in more complicated situations: we can often shift prices by a small—or, as in Figure 8.5, a large—amount while preserving the matching in the market; higher prices will be better for the seller, and lower prices will favor the buyer.

**Figure 8.5:** *Left*: The equilibrium we found with the algorithm is, in fact, buyer optimal. *Right*: If we increase the prices of all houses by as much as possible such that our matching in the preferred-choice graph stays the same (even though the preferred-choice graph now is different!), we obtain the seller-optimal equilibrium. Notice that the seller now gets all of the utility.

8.6 Bundles of Identical Goods

Finally, let us consider a special case of the matching market model, where each “item” $y_{j} \in Y$ is actually a bundle of $c_{j} > 0$ identical goods. Each player $i$ has their own individual value per good $t_{i}$ , and their valuation for a bundle $y_{j}$ of size $c_{j}$ is simply the product of the number of goods, $c_{j}$ , and their value per good, $t_{i}$ ; that is,

v_{i} (y_{j}) = c_{j} t_{i} .

(As a concrete example of such a market—which we will revisit in chapter 10—a bundle $y_{j}$ may correspond to an “advertising slot” that yields $c_{j}$ “impressions” of an advertisement, and each player $i$ has their own individual value $t_{i}$ for an impression of their advertisement.)

We assume without loss of generality that the bundles are ordered in decreasing size—that is, $c_{1} \geq c_{2} \geq \dots \geq c_{n}$ . We refer to such a matching market $Γ = (n, Y, \vec{v})$ as a matching market for bundles defined by $\vec{c}, \vec{t}$ .

Observe that in any outcome that maximizes social value, we have that the largest bundle $y_{1}$ must go to the person who values the good (and hence the bundle of goods) the most. Consequently, the person who values the good the second-most should get $y_{2}$ , and so on and so forth. Hence, by Theorem 8.1 (which states that market equilibria maximize social value), this property must also hold in any market equilibrium.

We now show that in any market equilibrium, the largest bundles will also have the highest price per good (i.e., the highest “unit price”). At first sight this may seem counterintuitive—when shopping for groceries we would expect a larger bundle of goods to have a lower price per good! The difference here is that the supply of bundles is limited and each buyer can only purchase a single bundle.³

Theorem 8.3. For any matching market for bundles $Γ = (n, Y, \vec{v})$ defined by $\vec{c}, \vec{t}$ , and every market equilibrium $(M, p)$ for $Γ$ , it holds that for every $j = 1, \dots, n - 1$ ,

\frac{p (y_{j})}{c_{j}} \geq \frac{p (y_{j + 1})}{c_{j + 1}} .

Proof. Consider a market equilibrium $(M, p)$ . Let $α_{j} = \frac{p (y_{j})}{c_{j}}$ be the price per good in bundle $y_{j}$ . Consider two bundles $y_{j}, y_{j^{'}}$ where $j < j^{'}$ , and assume for the sake of contradiction that $α_{j} < α_{j^{'}}$ —that is, the goods in the larger bundle $y_{j}$ are cheaper. Now consider the player $i$ who is matched to the smaller bundle $y_{j^{'}}$ of more expensive goods. His utility is currently $c_{j^{'}} (t_{i} - α_{j^{'}})$ , which must be non-negative by the market equilibrium property of $(M, p)$ . If they were to switch to the larger bundle $y_{j}$ of cheaper goods, they could increase their utility by $c_{j} (t_{i} - α_{j}) - c_{j^{'}} (t_{i} - α_{j^{'}}) > 0$ , since $c_{j} \geq c_{j^{'}}$ and $α_{j} < α_{j^{'}}$ by assumption. So $y_{j^{'}}$ cannot be a preferred choice for $i$ , contradicting the fact that $(M, p)$ is a market equilibrium.

■

Notes

Matching markets were first considered by Gale and Shapley [GS62] and the formal model was introduced by Shapley and Shubik [SS71]. Shapley and Shubik [SS71] also proved that existence of market equilibria; the constructive procedure for finding market equilibria is due to Demange, Gale, and Sotomayor [DGS86], and the analysis technique (using potential functions) is due to [EK10]. The notion of a market equilibrium (i.e., a Walrasian equilibrium) and the tatonnement process dates back to the 1870s and the work of Leon Walras [Wal54]. (The treatment of bundles of identical goods is new.)

¹We restrict to integer valuations to simplify our treatment; in particular, some of our existence results will rely on this.

²If the seller also has some values $v_{S} (y)$ for items $y \in Y$ , this can be captured by introducing an additional “buyer” (representing the seller’s interests in keeping the items) with those valuations.

³The bounded supply assumption is actually only one part of the story here. For instance, another reason why we tend to see lower prices for higher quantity bundles in practice is that values for bundles usually are not strictly linear in the size of the bundle (as we have modeled them here): it is common to have decreasing marginal values.