Notes: Budish (2011)

1. Introduction

In this note, I outline the results in Budish (2011)¹ for a presentation in Prof. Sargent’s reading group. Here are the slides themselves.

This paper introduces a new concept for clearing markets with indivisible goods and asset complementarities which is similar to a competitive equilibrium with equal incomes (CEEI)². In particular, Budish (2011) extends this idea from the baseline setting with independent and perfectly divisible goods by allowing for both approximate market clearing as well as slightly unequal incomes. He then shows that the resulting equilibrium and market design concepts have the desirable qualities of being Pareto efficient, fair and strategy-proof (…given that these last $2$ concepts have been appropriately adjusted).

2. Terminology and Notation

There are a set of $N$ students denoted by $\mathcal{S} = \{1,2,\ldots,N\}$ . There is a set of $M$ courses, $\mathcal{C} = \left\{ 1, \ldots, j, \ldots, M \right\}$ with $q_j \in \mathbb{Z}_+$ seats in each course $j$ . A consumption bundle $x_i$ for student $i$ is a binary vector in $\{0,1\}^M$ with $1$ meaning that the student took the course and $0$ meaning that the student didn’t. In this notation, the set of all possible courses is the powerset of $\mathcal{C}$ : $2^{\mathcal{C}}$ . Each student $i$ has von Neumann Morgenstern preferences over allocations defined as $u_i(\cdot): \{0,1\}^M\mapsto \mathbb{R}_+$ . Let $\Psi \subset 2^{\mathcal{C}}$ be the set of admissible schedules where the utility from an inadmissible schedule is $0$ . Formally, an economy is an object:

Suppose that each student gets assigned an endowment $b_i \in \mathbb{R}_+$ of fake currency and the market clears at prices $p_j \in \mathbb{R}$ for each class $j \in M$ .

3. Approximate CEEI

With this terminology in hand, I now define the equilibrium concept:

Definition (Approximate CEEI): Take an economy $\mathcal{E}$ . For this economy, the allocation $\mathbf{x}$ , budgets $\mathbf{b}$ and prices $\mathbf{p}$ constitute a $(\alpha,\beta)$ -Approximate CEEI if the following $3$ conditions hold:

(1) $\begin{align*} x_i &= \arg \max_{x \in 2^{\mathcal{C}}} \left\{ u_i(x) \mid \mathbf{p} \ x \leq b_i \right\} \quad \forall i \in \mathcal{S} \\ \alpha &\geq \left\Vert z_1(\mathbf{p}),z_2(\mathbf{p}),\ldots,z_M(\mathbf{p}) \right\Vert_2 \\ 1 + \beta &\geq \max_{i \in \mathcal{S}} b_i \geq 1 = \min_{i' \in \mathcal{S}} b_{i'} \end{align*}$

where $z_j(\mathbf{p}) = \sum_{i \in \mathcal{S}} x_{i \to j} - q_j$ .

In words, $\alpha$ is controlling the approximation of the market clearing condition and $\beta$ is controlling the approximation of the equal income condition. For example, say that $\alpha = 10$ , and then there are at most $2$ classes with $7$ too many students: $\sqrt{7^2 + 7^2} \approx 10$ . Alternatively, there could be $1$ class with $10$ students too many students. Turning to $\beta$ , suppose that we have a $\beta = 0.05$ , then the student with the least fake class-seat-buying currency has $1$ dollar while the most wealthy student has no more that $1.05$ dollars.

Next, I give the central existence result:

Proposition (Equilibrium Existence): Define the following $2$ new variables:

(2) $\begin{align*} k &= \max_{i \in \mathcal{S}} \max_{x \in \Psi} \vert x \vert \\ \sigma &= \min \left\{ 2 \cdot k, M \right\} \end{align*}$

First, we have that for any $\beta > 0$ , there exists a $(\sqrt{\sigma \cdot M}/2 , \beta)$ -Approx CEEI.

Second, it is also the case that for any $\beta > 0$ , any budget vector $\mathbf{b}$ that lies in the $[1,1+\beta]$ interval and any $\varepsilon > 0$ , there exists a $(\sqrt{\sigma \cdot M}/2 , \beta)$ -Approx CEEI with budgets $\mathbf{b}^*$ that satisfy the condition:

(3) $\begin{align*} \varepsilon &> \vert b_i^* - b_i \vert \quad \forall i \in \mathcal{S} \end{align*}$

What is this proposition saying in words? The first part of the result says that for any arbitrarily small distortion of wealth inequalities, there exists an $(\alpha,\beta)$ -approximate CEEI where the market clearing approximation is bounded by the amount $\sqrt{\sigma \cdot M}/2$ . The second part of the result captures the fact that, for any budget vector $\mathbf{b}$ in the $[1,1+\beta]$ interval that a school administrator might choose, there is a $(\alpha,\beta)$ -Approximate CEEI really close too it. Put differently, a school administrator can just randomly assign the initial budget vectors. Thinking ahead, this second clause indicates that the budget dispersion rather than the allocations themselves plays a key role.

Before I sketch out the proof of this result, let me first walk through an illustrative example:

Example (2 Diamonds, 2 Rocks): Suppose that there are $2$ buyers, Bob and Alice, who want to split $4$ items between them:

(4) $\begin{align*} \mathcal{C} &= \left\{ {\Large \text{Diamond}}, {\small \text{Diamond}}, {\Large\text{Rock}}, {\small\text{Rock}} \right\} \end{align*}$

If both Bob and Alice have an equal endowment, then there will not exist a price vector for each stone that clears the market. At each price point, both buyers would want the exact same bundle bundle making prices a useless tool for dividing up the goods. However, suppose instead that Bob has $\$1$ while Alice has $\$(1+\varepsilon)$ . Then, Alice would be able to buy the big diamond at a price of $\$(1 + \varepsilon)$ . Given that Alice would then have no more money, Bob could then afford to purchase both the small diamond and the big rock:

Thus, by noising up the wealth distribution a little bit, prices can become a useful tool for dividing up indivisible goods. What’s more, although Bob still envies Alice’s big diamond, his envy is limited to a single good making this division as fair as possible given the inherent indivisibility of the goods.

I now turn to sketching the existence proof out in more detail below:

Proof: I want to show that there exists a tuple of prices, budgets and allocations $(\mathbf{p},\mathbf{b},\mathbf{x})$ that satisfy the $3$ conditions in the definition above so long as $\alpha \leq \sqrt{M \cdot \sigma} / 2$ and $\beta > 0$ . If we were in the standard Econ 101 world of Mas-Collel et al. (2001) Ch 16 with Walrasian equilibria, then we could use the smoothness and convexity of the problem to guarantee existence and derive the welfare theorems. Here though, I need to overcome a critical problem: due to indivisibilities and asset complementaries, the excess demand function is discontinuous and possibly non-convex. Thus, I need to bound the size of the aggregate impact of these discontinuities, make the problem convex, and then finally apply well known fixed point theorems to show that an equilibrium must exist:

The result is in essence that, if people are given budgets with a little bit of noise from person to person, then there will exist a price vector $\mathbf{p}$ such that no one would be strictly better off with a pairwise switch and markets almost clear. I prove a restricted version of the result showing the existence of $(M \cdot \sqrt{\sigma},\beta)$ -Approximate CEEI. The jump from this baseline result to the tighter $\sqrt{\sigma \cdot M}/2$ result is purely mathematical, so for details please refer to the paper.

(Bound Discontinuities) The finiteness of the problem and the income inequality bound the aggregate size of the demand discontinuities. First, note that at worst a small change in prices can make an agent switch his entire portfolio from one bundle $x_i$ to an entirely different bundle $x_i'$ with $\emptyset = x_i \cap x_i'$ . The Euclidean distance in the change in the aggregate demand due to such a shift would be $\sqrt{\sigma}$ . To get a clearer idea of this magnitude, consider the $M = 2$ case below:

Next, if all agents had the same income $b_i = b_{i'} \ \forall i \in \mathcal{S}$ , such a shift might lead to an $N \cdot \sqrt{\sigma}$ change in the aggregate demand vector. However, if every agent has a unique budget $b_i$ , then in general there will be at most $M$ agents affected by a tiny price fluctuation. Why? Due to the variation in budget sets, there will always be some agent $i_j$ who is closest to his budget constraint hyperplane in the $j^{th}$ direction:

Thus, a little change in prices will in general only cause an $M \cdot \sqrt{\sigma}$ shift in the aggregate demand vector.

(Convexify) Next, I want to convexify the problem. Due to the demand discontinuities and asset complementarities, it may be the case that moving prices by $\varsigma$ might make you demand less of asset $j$ , but moving them by $2 \cdot \varsigma$ might make you demand more as the good you would have liked to buy is now too expensive and you have to settle. To do this, I use a limiting result. Consider a tatonnement process $f(\mathbf{p})$ such that:

(5) $\begin{align*} f(\mathbf{p}) &= \mathbf{p} + \mathbf{z}(\mathbf{p}) \end{align*}$

where a fixed point of $f(\cdot )$ would represent a set of market clearing prices. Then convexify the mapping $f(\cdot)$ as follows:

(6) $\begin{align*} F(\mathbf{p}) &= \mathtt{co} \left\{ \mathbf{y} \mid \exists \mathbf{p}_n \to \mathbf{p} \text{ s.t. } f(\mathbf{p}_n) \to \mathbf{y} \right\} \end{align*}$

Cromme and Diener (1991) show that $F(\cdot)$ is upper hemi-continuous and convex. Thus, if I can find a fixed point for $F(\cdot)$ I know in some sense that there is a market clearing set of prices for the true economy nearby.

(Apply Fixed Point Theorems) Finally, I can apply standard fixed point theorems to this object $F(\cdot)$ in order to show that an equilibrium exists. In particular Cromme and Diener (1991) also show that if $P \subset \mathbb{R}^n$ is compact and convex and $f: P \mapsto P$ is any mapping, then we have that:

(7) $\begin{align*} \alpha &\geq \left\Vert f(\mathbf{p}) - \mathbf{p} \right\Vert \end{align*}$

From intuition above, we know that $\sqrt{\sigma} \cdot M > \alpha$ .

This error of $\alpha \propto M \cdot \sqrt{\sigma}$ is particularly nice because it doesn’t depend on either $q_j$ or $N$ . Thus, even as the market gets really large, the market clearing error remains the same size.

4. Efficiency

Given that the equilibrium exists, we also want to know its relationship to the first best outcome:

Proposition (Analogue to First Welfare Theorem): Suppose $\left( \mathbf{x}, \mathbf{b}, \mathbf{p} \right)$ is an $(\alpha,\beta)$ -Approx CEEI of the economy $\mathcal{E}$ . Then, the allocation $\mathbf{x}$ is a Pareto efficient allocation in $\mathcal{E}$ .

This result comes almost for free and follows the standard First Welfare Theorem line of argument:

Proof: Suppose that there is some feasible allocation $\mathbf{x}'$ that Pareto improves on $\mathbf{x}$ for an agent $i$ . Since we know that $x_i$ was in agent $i$ ‘s feasible utility maximizing set, then if $x_i' \neq x_i$ we have that $\mathbf{p} \ x_i' > \mathbf{p} \ x_i$ . However, this means that the consumption bundle $\mathbf{x}'$ is infeasible as:

(8) $\begin{align*} \sum_{i = 1}^N \mathbf{p} \ x_i' &> \sum_{i=1}^N \mathbf{p} \ x_i \end{align*}$

yielding a contradiction.

5. Fairness

In some sense, in a world with indivisible goods there will always be some unfairness. Bob or Alice can have the big diamond in the example above, but not both; thus, either Bob or Alice will envy the other’s allocation. In order to properly discuss the relative fairness of different equilibrium concepts, we need to introduce a measuring stick concept in order to compare degrees of unfairness:

Definition (Envy Bounded by a Single Good): An allocation $\mathbf{x}$ satisfie envy bounded by a single good if, for any $i,i' \in \mathcal{S}$ , either:

(9) $\begin{align*} u_i(x_i) &\geq u_i(x_{i'}) \end{align*}$

…or, there exists some good $j \in x_{i'}$ such that

(10) $\begin{align*} u_i(x_i) &\geq u_i(x_{i'} \setminus \{ j\}) \end{align*}$

If an equilibrium satisfies the condition of envy bounded by a single good, then we could play the following game. You get to pick any $2$ agents $i$ and $i'$ in the economy where $u_i(x_{i'}) > u_i(x_i)$ and give them to me. Then, I will show you the good $j$ in agent $i'$ ‘s allocation such that if you removed that good, agent $i$ would no longer envy agent $i'$ ‘s allocation. For instance, in the example above, we could remove the big diamond from Alice’s allocation and then Bob would be perfectly happy with his little diamond and big rock allocation. Below I give the main result showing that if income inequality is small enough, then an $(\alpha,\beta)$ -Approximate CEEI will display envy bounded by a single good:

Proposition (Bounded Envy): For any economy $\mathcal{E}$ , if $\left( \mathbf{x}, \mathbf{b}, \mathbf{p} \right)$ is an $(\alpha, \beta)$ -Approx CEEI with

(11) $\begin{align*} \beta &< \frac{1}{k-1} \end{align*}$

…then $\mathbf{x}$ satisfies the condition of envy bounded by a single good.

To get an idea of where this result is coming from, return to the example with Alice and Bob above. In this example, by giving Alice a little bit more income in the beginning she was able to buy the big diamond; however, because she no longer had any money left, Bob could then buy the small diamond and the big rock. This intuition would break down if we gave Alice, say, $2 + \varepsilon$ times the amount of money as Bob so that she could buy both the big and small diamonds. Thus, we should suspect that envy bounded by a single good will fall out of an $(\alpha,\beta)$ -Approximate CEEI in a world where the income inequality is not so large. The proof below makes this intuition a bit more precise:

Proof: Suppose a contradiction where agent $i$ envies agent $i'$ ‘s allocation and this envy is not bounded by a single good. Let $k' \leq k$ denote the number of objects envied in bundle $x_{i'}$ by agent $i$ . Thus, for each of these goods, we could remove just $1$ of them and agent $i$ would still prefer this bundle to his own:

(12) $\begin{align*} u_i(x_{i'} \setminus \left\{ j_1 \right\} ) &> u_i(x_i) \\ &\vdots \\ u_i(x_{i'} \setminus \left\{ j_{k'} \right\} ) &> u_i(x_i) \end{align*}$

What’s more, it has to be the case that agent $i$ cannot afford any of these bundles otherwise he would have bought them in the first place:

(13) $\begin{align*} b_{i'} &\geq \mathbf{p} \ (x_{i'} \setminus \left\{ j_1 \right\} ) > b_i \\ &\vdots \\ b_{i'} &\geq \mathbf{p} \ (x_{i'} \setminus \left\{ j_{k'} \right\} ) > b_i \end{align*}$

By summing up these budget constraint inequalities we get the result that:

(14) $\begin{align*} (k'-1) \cdot b_{i'} &\geq (k'-1) \cdot (\mathbf{p} \ x_{i'}) > k' \cdot b_i \\ \frac{b_{i'}}{b_i} &\geq \frac{k'}{k'-1} \end{align*}$

Since $k' > k$ we can replace $k'/(k'-1)$ in the above inequality with the term $k/(k-1)$ . However, we know that at most the ratio of $b_{i'}/b_i$ can be $1+\beta$ so have that if $(k-1)^{-1} > \beta$ there is a contradiction!

6. Strategy Proof-ness

Finally, I turn to strategy proof-ness. As this is a property of the actual algorithm for assigning agents to allocations and not of the stopping condition for this algorithm (i.e., the equilibrium), I first need to outline this algorithm:

Definition (Approximate CEEI Mechanism): Define the algorithm below as the Approximate CEEI Mechanism:

Each agent $i$ reports her utility function $\hat{u}_i$ .

Check for $(0,0)$ -Approximate CEEI’s.

If non-empty:

Choose random $(\mathbf{x}, \mathbf{b}, \mathbf{p})$ .

If empty:

Choose target budget $\mathbf{b}'$ uniformly from $[1,1+\beta]$ with $\beta < \min \left\{ N^{-1}, (k-1)^{-1} \right\}$ .

Set $\varepsilon \approx 0$ , $\delta < 1 - N \cdot \beta$ and $\alpha \leq \sqrt{\sigma \cdot M}/2$ .

Compute set of feasible $(\alpha,\beta)$ -Approx.\ CEEI’s.

Choose random $(\mathbf{x}, \mathbf{b}, \mathbf{p})$ from set with minimum $\alpha$ and $\Vert \mathbf{b} - \mathbf{b}' \Vert$ small.

In words, this algorithm says to first solicit preferences and check for exact market clearing with prices. If no such solution exists, compute the set of $(\sqrt{\sigma \cdot M}/2, \beta)$ -Approximate CEEI with $\beta$ sufficiently small and choose a market clearing set of prices and allocations randomly from this set.

Next, I want to show that this algorithm is strategy proof if all of the agents behave as price takers. This seems like a reasonable assumption given that the equilibrium chooser (…think about a business school administrator) randomly selects from the set of admissible equilibria at the end of the period. One way to formalize this price taker idea would be to think about replacing each agent in the economy with a unit mass of identical agents:

Definition (Continuum Replication): The continuum replication of an economy $\mathcal{E}$ written as:

(15) $\begin{align*} \mathcal{E}^\infty &= \left( \mathcal{S}^\infty, \mathcal{C}, \left( q_j \right)_{j=1}^M, \left( \Psi_i \right) _{i \in \mathcal{S}^\infty}, \left( u_i \right)_{i \in \mathcal{S}^\infty} \right) \end{align*}$

can be constructed as by replacing each agent in the original economy with a unit mass of identical agents. $\mathcal{S}^\infty = (0,N]$ so that agent $1$ is replaced with the mass $(0,1]$ , agent $2$ with the mass $(1,2]$ , agent $3$ with the mass $(2,3]$ and so on…

Then, given this replacement, we can define a strategy proof-ness concept for price taking agents:

Definition (Strategy Proof in the Large): A mechanism is strategy proof in the large if it is exactly strategy proof in the continuum replication of any finite economy.

This yields the final result:

Proposition (Strategy-Proofness): The Approximate CEEI Mechanism is SPITL.

Proof: Pick an economy $\mathcal{E}$ and consider its continuum replication $\mathcal{E}^\infty$ . Consider agent $i \in \mathcal{S}^\infty$ and fix all other agent’s reports. Agent $i$ has measure $0$ so cannot affect prices. By definition of approximate-CEEI, agent $i$ does best by truth telling given budget $b_i$ otherwise the maximization condition would be violated.

7. Conclusion

I chose this paper to present because it has $2$ interestign take aways: First, this paper outlines the actual mechanics of market clearing in a common real world setting. In standard macroeconomic and financial theory, this process is a bit of black box. While the goods usually considered in these matching models are things like class and job allocations³, elementary school allocations⁴ and organ donor matching⁵, you could think about alternative settings that might be fitting in macro-finance like buy-sell trade matching at high frequencies or even capital good allocations at lower frequencies in a market with financial constraints where it is difficult to get loans to make side payments.

Second, the paper presents a model in which in order to constrain the extent of the supply-demand mismatch, the model demands a bit (…a quantity which I define in more detail below) of inequality in order to achieve the equilibrium. Heterogeneity in wealth actually allows agents to equitably decide who gets indivisible assets using prices. Thus, wealth inequality has a new and different role in the effectively clearing markets.

Website: Eric Budish at Chicago Booth. ↩
See Varian (1974). ↩
See Hylland and Zeckhauser (1979), Roth (1982) and Roth and Peranson (1999). ↩
See Abdulkadiroglu et al. (2005), Abdulkadiroglu et al. (2005) or Pathak and Sonmez (2008). ↩
See Roth et al. (2004). ↩