In a market, buyers and sellers express preferences. A matching allocates buyers to sellers according to these preferences. Here we will see how, under suitable circumstances, a perfect matching can be achieved. This illustrates how valuations and prices can decentralize a market in such a way that individuals, acting only in their own interests, can still produce socially optimal outcomes.

## Valuations

Consider a variation of the earlier example of the management of final year projects.

Example. Assuming again that there are as many supervisors as there are students, each student, rather than selecting a subset of suitable supervisors, rates each supervisor with a numerical score, as a measure for the degree of happiness of such an assignment.

For example, if there are three supervisors, $A$, $B$, and $C$, and three students, $X$, $Y$ and $Z$, and each student has three valuations, one for each of the supervisors, one can graphically illustrate one possible matching as follows.

Here, student $X$ values supervisor $A$ at $12$, supervisor $B$ at $4$ and supervisor $C$ at $2$.

One can measure the quality of the matching as the sum of the valuations on the edges that form part of the matching: $12 + 6 + 5 = 23$.

An optimal assignment maximises total happiness, but not necessarily individual happiness.

It is now natural to ask, how to find an optimal assignment. This question is a generalization of the perfect matching problem. (how?)

## Prices and Payoffs

Prices. As a further ingredient, we now add prices to the model. In order to make the discussion more realistic we switch to a property market example.

Suppose there are $n$ sellers, selling $n$ houses to $n$ buyers. As before, each buyer $j$ has a valuation $v_{ij} \in \mathbb{N} \cup \{0\}$ for each house $i$.

Moreover, each seller $i$ sets a price $p_i$ for their house.

Payoffs. With these values in place, buyer $j$’s payoff is $v_{ij} - p_i$, if she buys house $i$. Hence, wishing to maximise the payoff, she has an interest in dealing with those sellers $i$ that maximise the quantity $v_{ij} - p_i$. This interest can be described by a preferred sellers graph, a bipartite graph, where each buyer is connected to exactly those sellers that maximise the buyer’s payoff.

Examples. In the following example, seller $A$ has a price of $5$ for his house, seller $B$ a price of $2$, and seller $C$ a price of $0$. The resulting preferred sellers graph is a perfect matching.

In the next example, seller $A$ has a price of $2$ for his house, seller $B$ a price of $1$, and seller $C$ a price of $0$. The resulting preferred sellers graph is a bipartite graph with many edges that does not contain a perfect matching. (Why?)

The final example is similar, except that seller $A$ now has a price of $3$ on his house, with the effect that the resulting preferred sellers graph is a bipartite graph with a perfect matching.

Hence in this example, buyers and sellers can be matched up in such a way that each buyer maximises her payoff.

## Market-Clearing Prices

A set of prices is called market-clearing, if the resulting preferred seller graph has a perfect matching.

Maybe surprisingly, one can show that, for any set of buyer valuations, there exists a set of market clearing prices.

Before we turn to the proof of this claim (in the form of an algorithm that actually constructs a set of market clearing prices), let us note that market-clearing prices yield a socially optimal outcome.

Optimality of Market-Clearing Prices. For any set of market-clearing prices, a perfect matching in the resulting preferred-seller graph has the maximum total valuation of any assignment of sellers to buyers.

This claim is justified as follows. Clearly, any such perfect matching has maximal total payoff, since the preferred-seller graph consists only of edges that maximise an individual buyer’s payoff. Now the maximal total payoff is just the difference of the maximal total valuation and the sum of all the prices. But the sum of the prices does not depend on the chosen perfect matching.

## Constructing Market Clearing Prices

We now provide an algorithmic proof the following claim.

Existence of Market-Clearing Prices. For any set of buyer valuations, there exists a set of market clearing prices.

The procedure will be some kind of auction, although now we are dealing with many sellers, selling many items to many buyers. The auction works a s follows.

Initially, all sellers set their prices to zero: $p_i = 0$. Buyers then choose the preferred sellers, and if the resulting graph contains a perfect matching we are done.

If not, there is a constricted set, that is a set $S$ of buyers, with the property that $|N(S)| < |S|$ (here $N(S)$ is the set of neighbours of all nodes in $S$): the number $|N(S)|$ of sellers these buyers are interested in is strictly smaller than the number $|S|$ of buyers.

In other words, those houses are in “high demand”, and consequently those sellers can increase their prices. The aution continues with each seller in the set $N(S)$ raising their price by one unit.

It will be convenient to have the lowest price equal to $0$ throughout. In order to ensure this, at this stage of the algorithm, all prices are adjusted by subtracting the smallest price (which might be $0$).

In summary, starting with all prices being $0$, the auction repeats the following sequence of steps until a perfect matching is found.

1. Construct the preferred-seller graph on the basis of the current prices

2. Stop if the graph contains a perfect matching.

3. Else find a constricted set $S$ of buyers, and their neighbours $N(S)$.

4. All sellers in $N(S)$ simultaneously raise their prices by one unit.

5. Modify all prices by subtracting the smallest price.

Example. The following graphs illustrate how the algorithm works on the set of valuations we considered earlier. Initially, with all prices $p_i = 0$, we get the following preferred-seller graph.

Clearly, this graph has a constricted set $S = \{X, Y, Z\}$, and in the next step, the sole node in $N(S) = \{A\}$ raises their price by one unit. This results in a slightly modified preferred-seller graph.

In this graph, $S = \{X, Z\}$ forms a constricted set with $N(S) = \{A\}$, so $A$ raises his price by another unit, resulting in a new preferred-seller graph.

Here one can identify $S = \{X, Y, Z\}$ as a constricted set with $N(S) = \{A, B\}$, justifying further price increases, and another preferred-seller graph.

At this point the algorithm stops: the graph contains a perfect matching (as we already knew).

Termination. To finish the proof, it remains to show that the procedure always comes to an end, not only on the above example.

To that end, we introduce a notion of potential energy, as follows. The potential energy of a buyer is their current maximal payoff. The potential energy of a seller is their current price. (Both buyers and sellers would receive these as payoff if the prices were market-clearing.) The potential energy of the auction then is the total sum of the potential energies of all buyers and sellers.

Initially, as all prices are zero, the potential energy equals the maximal total valuation. Clearly, the potential energy will never drop below zero (as no buyer or seller will allow their potential energy to become negative).

How does the potential energy of the auction change over time, that is when the individual steps of the algorithm are carried out?

Note that only steps 4 and 5 above can have an impact on the potential energy, as they are the only steps that affect the prices.

In step 5, subtracting a fixed amount $p$ from each price will reduce each seller’s payoff by $p$ and at the same time increase each buyer’s payoff by $p$. The net effect on the potential energy hence is $0$.

In step 4, however, the price increases add one unit to the payoff of each of the sellers in the set $N(S)$, while they take away one unit from the payoff of each buyer in the set $S$. As $|S| > |N(S)|$, this strictly decreases the potential energy.

Therefore the process has to come to an end after finitely many steps. This concludes the proof of the claim that market-clearing prices exist.