Bit the bullet and started a (reading) course on market design. The plan is to begin with some lectures that cover some of the usual stuff that is covered followed by readings. First session was on the Shapley-Shubik (SS) assignment model. A summary can be obtained by clicking on mktdesign1

The readings cover the following topics:

1) Credit Default Swaps

2) Bankruptcy

The Economics of Bankruptcy Reform Author(s): Philippe Aghion, Oliver Hart, John Moore Source: Journal of Law, Economics, & Organization, Vol. 8, No. 3 (Oct., 1992), pp. 523-546

New Approach to Corporate reorganization by Lucien Bebchuk, Harvard Law Review, 1988

Analysis of secured debt, Stultz and johnson, JFE, 1985

3) Healthcare Markets

Ho, Katherine 2009. “Insurer-Provider Networks in the Medical Care Market.” American Economic Review, 99(1): 393–430.

4) IPO’s

5) Affirmative Action

Hickman

Fryer & Loury

Chung

5) Wages, centralized matching, unraveling

Bulow & Levin

Roth

Halaburda

**1. Shapley-Shubik Model **

There is a set of buyers and a set of sellers each selling one unit of a good (could be divisible or not). Let be the monetary value that buyer assigns to seller ‘s object. In other words, we assume quasi-linear preferences. No buyer wants more than one of any good. By adding dummy sellers or buyers we can ensure that .

Depending on the ‘s you can assign a couple of interpretations to the SS model. First, . Here is the value to buyer of acquiring a good irrespective who sells it. In effect the sellers all sell the same good. is the opportunity cost to seller . Under this interpretation, SS is a model of bilateral trade.

Second, is the output generated when worker is matched with firm . Sometimes one assumes a specific functional form form for , for example, . Here each agent (firm or worker) has a type and their joint output is a function of their types. Third, each seller is an advertising slot and each buyer an advertiser. Then, is the the click through rate on slot and is the value per click to advertiser . Because billions (and if one were Carl Sagan one would repeat the word `billions’) of $’s are transacted this way, it is obligatory to mention this example in a class on market design to give the whole enterprise a certain gravitas. There is a natural optimization problem one can associate with SS, which is to find an assignment of goods to buyers to maximize the total value achieved so that no buyer consumes more than one good and no seller gives more than one good. In other words, find an efficient allocation. This is called the assignment problem or maximum weight bipartite matching. The problem has a long history going back to Monge (1700’s). Indeed, well before Becker, it was Monge who considered the problem under the assumption that . Since Monge’s time, the literature has split. One branch, via Kantorovich, interprets the problem in terms of coupling of measures and this has blossomed into an active and influential area of Mathematics called optimal transport of measure. It has important applications in pde’s and concentration of measure. There are also some applications in economic theory. I won’t go down that branch. The other, via Koopmans and Hitchcock, sticks to the discrete set up described here. That is the branch I will follow.

**2. Shapley-Shubik (Divisible) **

So that the problem of finding an efficient allocation can be expressed as an LP suppose the goods are divisible and each buyers utility for goods is linear in quantity. However, no buyer wants to consume more than one unit in total (unit demand). Let be the quantity of good allocated to buyer . For any and , let

subject to

The first constraint arises from the unit demand assumption. The second ensures no seller supplies more than they have. These constraints imply that for all and .

Let be the dual variable associated with each constraint and the dual variable associated with each constraint . The dual to the above program is:

subject to

The dual has an interesting interpretation. Think of as the price of object . Given a collection of prices, the optimal solution to the dual is found by setting each to Thus, each represents the maximum surplus that agent can receive from the consumption of a single object at prices .

At prices , buyer must solve:

subject to

to determine its demand. It is easy to check that the optimal solution is any convex combination of objects that yield maximum surplus to the buyer.

Suppose is an optimal primal solution and an optimal dual solution. Then, the prices `support’ the efficient allocation in the following sense. Suppose we post a price for each . Ask each buyer to name their demand correspondance at the posted prices. Then, it is possible to give each agent one of their demanded bundles and not exceed supply . To see why, recall complementary slackness:

So, if it follows that Hence, in this economy there is a set of prices that can be posted for each good so as to balance supply with demand. In other words, LP duality gives us the existence of Walrasian prices in this economy.

The set of feasible dual solutions forms a lattice with respect to the partial order if and only if . In this partial order there is a smallest element, which corresponds to the smallest Walrasian price. This can be determined by choosing from among all optimal dual solutions one that minimizes (equivalently maximizes total surplus to buyers).

Hold fixed and consider as a function of subsets of . Then, is non-decreasing. It is also submodular. Why? From the dual we see that it is obtained by minimizing a linear (i.e. submodular) function over a lattice. As submodularity is preserved under minimization, it follows that is submodular in . A similar argument shows that is supermodular in . This submodularity/supermodularity is useful in deriving certain incentive properties of the efficient allocation.

One can associate a tu co-op game with the assignment model. For any coalition of buyers () and sellers () let be the value of the coalition. The core, will be the set of solutions to the following:

The core has the usual interpretation. It is the set of allocations that cannot be blocked by any coalition of buyers and sellers.

Consider the following dual program (DP):

subject to

It is straight forward to check that every optimal solution to (DP) is in and every point in corresponds to an optimal solution to (DP). Why is this interesting? It says that most of the constraints that define the core are redundant. It suffices to consider only pairs of agents consisting of one buyer and one seller. If the core is the set of efficient allocations immune to deviations by any subset of agents, then equivalence to (DP) says that it suffices to consider only pairwise deviations.

From the core, consider the following two relations:

Negate the second and add to the first:

The term on the right hand side is buyer ‘s marginal product. Hence, no point in the core can give any buyer more than their marginal product. Submodularity of implies that there is a point in the core that gives each buyer their marginal product (an old result of Shapley’s). What is this point? It is the one that corresponds to the minimal Walrasian price, i.e., the optimal solution to (DP) that maximizes .

Suppose sellers are non-strategic and we run a Vickrey auction to allocate the goods amongst the buyers. Then, each buyer would walk away with a surplus equal to their marginal product (which is what the Vickrey auction gives buyers to give them the incentive to reveal their valuations). Thus, in this assignment economy, minimal Walrasian prices correspond to the prices that would be charged in a Vickrey auction.

**3. Shapley-Shubik (Indivisible) **

Now suppose the goods in SS are indivisible. I’m going to show the results outlined above carry through unchanged. To do that I need to tell you about totally unimodular matrices.

** 3.1. Total Unimodularity **

A matrix is called **totally unimodular** (TUM) iff the determinant of each square submatrix has value 1, -1 or 0. If a matrix is TUM then so is its transpose. If and are TUM, then so is .

Example 1The following matrixis TUM. The following is not:

Every proper square submatrix has determinant with absolute value 0 or 1, but the determinant of the entire matrix is 2.

Theorem 1Let be a TUM matrix. Let be a integral vector. Then, every extreme point of is integral.

**Proof:** To every extreme point of there is a basis of such that . By Cramer’s rule, we can write where is the adjoint of . Since has all integer entries, has all integer entires. Since is TUM and is non-singular, it follows that . Hence has all integer entries. Thus, is integral.

Paul Seymour gave a complete (polytime) characterization of TUM matrices. The upshot of it is that most TUM matrices are **network matrices**. is a network matrix if for all and each column contains at most two non-zero entires of opposite sign.

Theorem 2If is a network matrix, then is TUM.

**Proof:** Proof is by induction on the size of a submatrix. Consider a square submatrix of , call it . If each column of has exactly two non-zero entries then . Why? Summing up the rows of gives us zero, meaning that the rows of are linearly dependent. If there is a column of that contains exactly one non-zero entry, then compute the determinant of using the minor associated with this entry. By induction the determinant must have value, 0,1, -1. A column with all zeros means that .

** 3.2. Back to SS **

I’ll show that the constraint matrix for the assignment program that defines is TUM. This would mean that there is always an efficient allocation which produces an integral allocation.

Fix a good and agent . Consider the column associated with the variable . The variable appears with a coefficient of 1 in exactly two rows. One occurs in a row corresponding to agent and the other to a row corresponding to object . Let consist of all rows corresponding to objects and the set of all rows corresponding to agents. Multiply all the rows in by -1. We now have a constraint matrix where each column contains exactly two non-zero entries of opposite sign.

** 3.3. Ascending Auctions **

The equivalence between minimal Walrasian prices and Vickrey prices in SS means that the Vickrey outcome can be obtained from a t\^{a}tonnement process that terminates in the minimal Walrasian price. Two have been proposed in the literature. One by Crawford and Knoer and the other Demange, Gale and Sotomayor (see also Leonard). Both a variations of dual ascent algorithms for solving the LP formulation of the assignment model.

I’ll outline Demange, Gale and Sotomayor (DGS). Assume that the ‘s are integral. In each iteration we have a vector of prices . Initially all prices are set to zero. In each iteration buyers report their demand correspondance. That is, the set of goods that maximize their surplus at current prices. Let be the demand correspondance of buyer . Consider now the bipartite graph defined on as follows: an edge exists iff . If this graph contains a perfect matching, stop. At current prices demand equals supply. A perfect matching means that there is a way to give each an such that and no good is allocated to more than one buyer. If a perfect matching does not exist, by the Hall marriage theorem (I will state and prove this later), there must exists a set such that The set is called overdemanded. Identify a minimally overdemanded set and increase the price of each good in this set by 1 unit. Repeat.

**4. Bilateral Trade **

Lets put this machinery to work on bilateral trade. This is the case when . Suppose is the private information of buyer and is the private information of seller .

- The core of the associated tu game is non-empty.
- The point in the core that maximizes the total surplus to buyers makes it a dominant strategy for them to reveal their private information.
- The point in the core that maximizes the total profit to the sellers makes it a dominant strategy for them to reveal their private information.
- In general, there is no point in the core that is jointly `best’ for buyers and sellers. Hence, there is no way to obtain an outcome in the core for which it is a dominant strategy for both sides to reveal their private information.

We have the outlines of an archetypal matching paper. First, show that a stable or core outcome exists. Second, show that when only one side is strategic, one can implement the core outcome in an incentive compatible way. Third, observe that it is impossible to implement the core outcome when both sides are strategic. Fourth, show that as the economy gets large, one can implement something asymptotically close to the core in an incentive compatible way (or implement a core outcome in an asymptotically incentive compatible way). So, lets do the fourth.

The idea is due to Preston McAfee. Order the buyers so that . Order the sellers so that . The efficient allocation can be computed by determining the largest such that . Buyer is matched with seller for all . McAfee suggests stopping at . Charge all buyers a price of . Pay all sellers , . What each agent pays or receives does not depend on their reports. So, reporting their private information is a dominant strategy. Further, the mechanism runs a slight surplus and is individual rational. However, it is not efficient. The efficiency loss is . Assuming ‘s and ‘s are independent draws from a distribution with bounded support, the percentage loss in efficiency approaches zero as .

Alternatively, one can implement the Vickrey outcome. In this case each buyer pays and each seller receives . The deficit of the Vickrey auction will grow like . One can then use properties of order statistics and the Kolmogorv-Smirnov bounds to show that the deficit goes to zero as .

**5. More on TUM **

Recall the constraints for the assignment model:

An integer solution, , to these constraints defines a permutation matrix whose entry is . A fractional solution to these constraints is a doubly stochastic matrix. TUM of the constraint matrix means that every doubly stochastic matrix is a convex combination of permutation matrices. This is is known as the Birkhoff-von Neuman theorem. Alternatively, the assignment constraints define the convex hull of doubly stochastic matrices.

For our purposes, TUM means that every fractional solution to the assignment constraints can be interpreted as a lottery over integer assignments. Thus, the assignment constraints give us a succinct description of the set of all lotteries over integer assignments. This is will be useful in applications when we search for randomized allocation rules satisfying other properties.

Network matrices are an important class of TUM matrices. There are matrices that don’t appear to be network matrices but after certain elementary row operations can be converted into network matrices. One such class is the set of 0-1 matrices with the consecutive 1’s property (C1). A 0-1 matrix has the consecutive 1’s property if there is a permutation of its rows such that the non-zero entries in each column are consecutive. The following matrix is C1:

C1 matrices arise in a variety of applications (interval graphs, cyclic staffing). Fulkerson and Gross were the first to give a polytime algorithm for recognizing C1 matrices. The following is due to Veinott and Wagner (1962).

Theorem 3If is a C1 matrix, then, is TUM.

**Proof:** Suppose the rows of have already been permuted so that the columns have the consecutive 1’s property. Suppose that is . Define to be the following matrix:

- For all , , .
- For , .
- For all and , .

Here is a example of :

To complete the proof it suffices to verify that is TUM and is a network matrix. Note that pre-multiplying by corresponds to negating row of and adding it to row of .

I turn now to a class of C1 matrices that will be useful later.

Let be a ground set of elements and a collection of subsets of . is called **laminar** if for any either , or . If one drops the condition that , then is called a **chain**.

Given a collection of subsets, we can represent it using a 0-1 matrix as follows. A column for each member of and a row for each element of . Set if the set corresponding to column contains . Its easy to see that if is laminar, then is C1. Call a 0-1 matrix that arises in this way a **laminar matrix**.

In fact, is `equivalent’ to a 0-1 matrix with exactly one non-zero entry in each row. Here is is how. Pick any two columns of , and . Let and be the sets they correspond to in . Suppose . Negate column and add it to column . Note that this can at most flip the sign of the determinant of any square submatrix of . Repeat. The result is a 0-1 matrix whose columns are disjoint, i.e., exactly one non-zero entry in each row.

## Recent Comments