Thursday, January 16, 2014

How 2 sell house

1The house-selling problem¶

Suppose we have $n$ buyers and $n$ sellers. Each buyer $i \in B$ has a value $v_j \geq 0$ for the house of seller $j \in S$.

We can model this problem using a complete bipartite graph. A set of trades is a matching $M$. If all houses are sold, we have a perfect matching. (Assume that each buyer only wants one house.) But who should get to buy which house, and at what price?

This is one of very few problems in economics for which we can actually generate an equilibrium. First, though, we'll look at what happens when the sellers fix the prices. Suppose the house sold by seller $j$ is $p_j$. Each buyer wants to maximise the value $(v_i - p_i)$ for the house he buys (call it $i$) and will choose $i$ accordingly. Essentially, each buyer wants to pick the most "profitable" house for him. This is also known as the best response for buyer $i$ at prices $\vec p$ (a vector containing $p_0$, $p_1$, etc). Note that there can be multiple most profitable houses for a given buyer.

1.1Market-clearing prices¶

We can view the best responses as a subgraph $H_p$ of $K_{n,n}$ (the complete bipartite graph with $n$ vertices in each bipartition). If $H_p$ contains a perfect matching $M$ then $p$ is a set of market-clearing prices (MCPs).

Properties of market-clearing prices:

• There is no excess demand (i.e., 2 people don't want to buy the same house)
• There is no excess supply (i.e., all houses are sold)
• Each buyer gets one of his most profitable (aka most preferred) houses at prices $p$

When does $H_p$ have a perfect matching? Precisely when Hall's condition holds. We say that some subset $A \subseteq B$ is unsuppliable or unmatchable when $|\Gamma(A)| < |A|$. If we can find such a set, then the prices of $\Gamma(A)$ can go up; the prices of undemanded houses should go down.

1.1.1Generation algorithm¶

Here is an algorithm for generating a set of MCPs:

• Set $p=0$. If $H_p$ has a perfect matching $M_p$, output $M_p$. Otherwise:
  • Find an unsuppliable set $A$ in $H_p$
  • Increase by \$1 the price of each house in $\Gamma(A)$ (assuming integer prices)
  • If $p_{\text{min}} > 0$, reduce all prices by \$1
• Continue until a perfect matching exists.

We can prove that this algorithm always terminates with a set of MCPs using a "potential energy" argument. This proof is a little advanced, so we can ignore some of the details, but the basic idea is important.

Let $\phi$ be a potential energy function, defined as follows:

$$\phi = \sum_{i \in B} u_i(p) + \sum_{j \in S} p_j$$

where $\displaystyle u_i(p) = \max_{j \in S}(v_{ij} - p_j)$ represents the maximum utility (or "profit") that buyer $i$ can obtain among all the houses.

At the start, when all the prices are zero, $\vec p = \vec 0$ and so

$$\phi(\vec 0) = \sum_{i\in B}\max_{j\in S}v_{ij}$$

The potential function decreases at each step, by at least 1. It can't ever be negative, though^why?. So the loop must terminate eventually.

Here's why the potential function decreases in each iteration. Since we're increasing the price of each house in $\Gamma(A)$ by \$1, the price of every most profitable house for any $i \in A$ increases by 1 and thus $u_i(p)$ falls by 1. So $\phi$ falls by $\geq |A|$. But $\displaystyle \sum_{j\in S} p_j$ increases by $|\Gamma(A)|$ and so $\phi$ increases by $|\Gamma(A)|$. But $|\Gamma(A)| < |A|$. Thus $\phi$ decreases by $\geq 1$. On the other hand, if we need to reduce all prices by \$1, then $\phi$ falls by $n$?¹

1.1.2Economic efficiency¶

Recall that the algorithm was constructed so that it would only stop when there's a perfect matching. Here's a surprising property. Not only does the resulting set of prices form an equilibrium (so that everyone gets his most preferred house), but this equilibrium is the optimal solution to the system. It also maximises "economic efficiency", i.e., maximises the sum of all the utilities (social welfare, etc). This can also be thought of as maximising the sum of all the values along the edges of the graph.

In fact, the actual prices don't even matter when considering the economic efficiency. If prices are high, seller utility will be high, yes, but this is offset by the lower utility for the buyers. In fact, it cancels out exactly. Recall that utility for buyers is given by $u_{ij} = v_{ij} - p_j$, and utility for sellers is given by $p_{ij}$, so their sum is just $v_{ij}$, which doesn't even take the price into consideration at all. So price doesn't matter, because if one person gains a dollar, another loses a dollar (zero-sum game).

1.1.3The optimal perfect matching¶

Theorem: If there are market-clearing prices, then $M_p$ is an optimal perfect matching.

Proof: Let $M^*$ be an optimal perfect matching. Observe that $M^*$ need not be a subset of $H_p$. $M_p$ is a perfect matching in the best response graph, $H_p$.

However, for any edge $ij \in M^*$, we have that

$$v_{ij} - p_j \leq u_i(p) = \max_{j\in S} v_{ij} - p_j$$

Thus, economic efficiency, or value, for $M^*$, is given by

$$\begin{align} v(M^*) & = \sum_{ij \in M^*} v_{ij} = \sum_{ij \in M^*} (v_{ij} - p_j + p_j) = \sum_{ij \in M^*} (v_{ij} - p_j) + \sum_{ij \in M^*} p_j \\ & \leq \sum_{i\in B} u_i(\vec p) + \sum_{ij \in M^*} p_j = \phi(\vec p) = v(M_p) = \sum_{ij \in M^*} v_{ij}\end{align}$$

So $v(M_p) = v(M^*)$ and $M_p$ maximises economic efficiency.

Also, when you have a perfect matching, $\phi$ is equal to the economic efficiency.