The prices nobody can break away from

The auction ends at prices that certify the best assignment, and the certificate it reaches is not unique. There are usually many sets of prices that clear the market — at which every buyer holds the house they like best at those prices — and the auction lands on one of them because of the order in which people happened to bid. Which one it lands on matters to everybody involved. Higher prices move money from buyers to sellers without changing who lives where.

This essay looks at the whole set of such outcomes at once. It is a small, explicit polygon when there are two houses, and its shape carries three facts that are not at all obvious in advance: the set is never empty, it has one point that is best for every buyer simultaneously and one best for every seller simultaneously, and the buyers’ best point pays each buyer exactly what that buyer adds to the market.

The model is Lloyd Shapley and Martin Shubik’s assignment game of 1971. Each seller owns one house and will not sell below a reserve price. Each buyer wants at most one house and has a value for each. If buyer $i$ buys house $j$ at price $p$, the buyer gains value minus price and the seller gains price minus reserve, and between them they share the surplus $a_{ij} = \max(0,\ \text{value} - \text{reserve})$. Nothing else — no rankings, no mechanism — is assumed.

Who can break away, and from what #

An outcome is a matching of buyers to houses together with a split of each matched pair’s surplus: a payoff $u_i$ for every buyer and $v_j$ for every seller. It breaks down if some buyer and some seller who are not matched to each other could deal with each other instead and both do better. They could split their own surplus $a_{ij}$ between them, so they both do better exactly when $u_i + v_j < a_{ij}$.

So an outcome is stable — in the core, in the language of coalitions that can walk away — when

$$u_i + v_j \ge a_{ij} \quad \text{for every buyer } i \text{ and house } j,$$

with nobody paid less than nothing and the payoffs adding up to what the matching produces. Larger coalitions need not be checked: any group that breaks away still has to pair off buyer with house, so if no pair gains, no group does.

Written that way, the core is a set of inequalities that is already familiar. They are the constraints of the dual of the assignment problem — a price on every person and every task, with no pair’s prices adding to less than its value. And the condition that payoffs add up to what the matching produces says the dual total equals the best matching’s total. The core is exactly the set of optimal dual solutions, which is Shapley and Shubik’s theorem, and it is non-empty for the same reason strong duality holds: the corners of the assignment polytope are whole assignments, so the best matching’s value is also the dual’s.

It also explains the matching. Only a best matching can appear in a core outcome, because a matching worth less than the best would leave the payoffs short of the dual optimum. Who gets which house is decided by total surplus alone; the core decides only the prices.

Reading the polygon #

In the opening figure buyer A values house 1 at 11 and house 2 at 8; buyer B values them at 10 and 9; the reserves are 4 and 6. So the surpluses are $a_{A1} = 7$, $a_{A2} = 2$, $a_{B1} = 6$, $a_{B2} = 3$. The best matching gives A house 1 and B house 2, for $7 + 3 = 10$.

Once the matching is fixed, the sellers’ payoffs are determined by the buyers’: seller 1 gets $7 - u_A$ and seller 2 gets $3 - u_B$. So every outcome is a point $(u_A, u_B)$, and the core’s inequalities become lines in that plane. The boxes $0 \le u_A \le 7$ and $0 \le u_B \le 3$ keep everybody’s payoff non-negative. The unmatched pairs give the rest. Buyer A and seller 2 could break away if $u_A + (3 - u_B) < 2$, so the core needs $u_A - u_B \ge -1$. Buyer B and seller 1 could break away if $u_B + (7 - u_A) < 6$, so it needs $u_A - u_B \le 1$. Those two lines of slope one, inside the box, cut out the band the figure shades, with corners at $(0, 0)$, $(1, 0)$, $(4, 3)$, $(2, 3)$ and $(0, 1)$ — every one found by intersecting two of the constraints exactly and keeping the intersections that satisfy all the rest.

The two diagonal edges are the whole story of competition in this market. The upper one is where buyer A is exactly as well off as dealing with seller 2 would make them; the lower one is where buyer B is exactly as well off as with seller 1. Between them, each buyer’s alternative is worse than the deal they have, and neither can threaten to switch.

Best for every buyer at once #

Look at the top-right corner, $(4, 3)$. It gives buyer A more than any other core point does, and it gives buyer B more than any other core point does — at the same time. There was no reason to expect such a point. In most bargaining problems what is best for one participant is worse for another, and there is no single outcome all of one side prefers.

The reason there is one here is that the core has a lattice structure.

Take any two core outcomes and form a new one by giving each buyer the better of their two payoffs, and each seller whatever is left of their matched pair’s surplus. The new outcome is in the core, and the check is one line. Giving a matched buyer the larger of two payoffs gives their seller the smaller, since the pair’s surplus is fixed. Now take any pair $i, j$. Seller $j$’s new payoff is the smaller of their two, say the one from the first outcome; buyer $i$’s new payoff is at least their payoff in the first outcome; and in the first outcome the pair already satisfied $u_i + v_j \ge a_{ij}$. So they still do. The same argument, with the roles swapped, works for the worse of two payoffs, and both are confirmed in the figure on three random pairs. So the core is closed under “better for every buyer” and “worse for every buyer”, and a finite polygon closed under both has a top and a bottom.

Stable matching has exactly the same structure: the stable matchings form a lattice with one end best for all proposers and the other best for all receivers, and the essay on who every stable answer leaves out noted that the priced version of the problem is this game. The two lattices are not an analogy. The stable matching problem is the assignment game with the prices removed — values replaced by rankings and money replaced by nothing — and both lattices come from the same fact: the side that is better off in one stable outcome is better off throughout, because improving it only tightens constraints on the other side.

What each buyer adds #

The buyers’ corner has a value that can be predicted without drawing anything.

Remove buyer A from the market. The best matching among what remains — buyer B and both houses — gives B house 1, worth $6$. With A present the market produces $10$. So A adds $10 - 6 = 4$ to the market: their marginal contribution. Remove buyer B instead: A takes house 1 for $7$, and B adds $10 - 7 = 3$.

Those are exactly the coordinates of the buyers’ corner, $(4, 3)$. At the buyers’ best core point, each buyer is paid their marginal contribution to the market — a theorem of Herman Leonard from 1983, and of Gabrielle Demange independently — and the sellers’ best point pays each seller theirs. The core cannot pay a buyer more than they add, because then the rest of the market, which could produce the remaining value without them, would be receiving less than it could get on its own; the surprise is only that every buyer can be paid their full marginal contribution simultaneously.

That payment has a famous name in another subject. Paying each participant what they add to everyone else is the principle of the Vickrey–Clarke–Groves mechanism, under which reporting one’s true values is always the best strategy. So the buyers’ corner is the outcome of an auction in which no buyer has any reason to lie about their values — the multi-object version of the second-price sealed-bid auction. The ascending auction of Demange, Gale and Sotomayor, a cousin of the bidding auction with smaller increments, reaches exactly these lowest clearing prices.

Choosing a point inside #

Between its two corners the core usually holds many outcomes, and nothing in the stability condition prefers one. A market that ran the buyer-favouring ascending auction would land at one corner; a market in which sellers set prices and buyers accepted or refused would drift toward the other. Neither is more stable than any interior point.

Cooperative game theory has proposals for choosing, and the natural one here is the nucleolus: the core point that makes the most aggrieved coalition as little aggrieved as possible, and then the next, and so on. For the assignment game it has a pleasant reading: every coalition that matters is a buyer–seller pair, so the nucleolus balances how far each unmatched pair is from breaking away, pushing the outcome as deep inside the polygon as the constraints allow. Tamás Solymosi and T. E. S. Raghavan showed in 1994 that for assignment games it can be computed efficiently, which is not true of cooperative games in general. It is a compromise in a precise sense, and it is also a reminder that the core describes what cannot happen, not what will — the polygon rules out the outcomes somebody would walk away from and is silent on which of the rest a market reaches.

A buyer who buys nothing still moves the prices #

Add a third buyer, C, who values both houses at 8 — less than A and B value them, so C buys nothing in the best matching. C’s presence changes nothing about who lives where. It changes the core a great deal.

C buys nothing and so gets nothing in any core outcome, and the core condition for C and seller 1 is then $v_1 \ge a_{C1} = 4$: seller 1 must get at least what a sale to C would give, or C and seller 1 would break away together. That caps buyer A’s payoff at $7 - 4 = 3$, and similarly for B. So the whole top of the polygon is cut off, and the buyers’ corner drops to $(2, 1)$ — each buyer’s marginal contribution in the new market, since removing A now lets C take a house.

The sellers’ corner does not move. Competition among buyers comes entirely out of the buyers’ share. A losing bidder never pays anything, and yet the mere existence of their bid transfers money from the winners to the sellers. That is the mechanism by which markets with more buyers than goods drive prices up, and in this model it is exact: each unmatched buyer’s valuations become floors under the sellers’ payoffs.

Four buyers for three houses #

The same structure holds at any size, where it can no longer be drawn as a polygon but can be tabulated.

The fourth buyer, D, buys nothing but has high enough values to compete for everything, and the effect is visible at the sellers’ corner: every buyer’s payoff there is zero. With a buyer waiting in the wings for every house, sellers can extract the whole surplus, because any buyer who asked for more could be replaced. At the buyers’ corner, D’s presence still bounds how well the winners can do — A, B and C receive 3, 2 and 1, far less than their surpluses.

Every core outcome lies between the two corners for every participant separately — a buyer is never better off than at the buyers’ corner or worse off than at the sellers’ — and every whole-number core outcome in the figure confirms it there is. That is the lattice again, in four dimensions where no picture can show it. The count of thirteen is itself small for a reason: D’s values sit just below the winners’, so the constraints D imposes leave each winner only a unit or two of room, and the core is a thin slab rather than a box. Lower D’s values and the slab thickens toward the box the three-buyer market would have; raise them and it shrinks to a point, which is what happens in a market with many identical losing bidders, where competition pins every price.

The price of each house #

Payoffs translate back into prices: a house’s price is its seller’s reserve plus the seller’s payoff. So the core assigns each house an interval of possible prices, running from its price at the buyers’ corner to its price at the sellers’ corner.

The low end of each band is set by competition: house 1 cannot sell for less than 9, because buyer D values it at 9 and at any lower price D and seller 1 would deal. The high end is set by the winner’s alternatives: house 1 cannot sell for more than 12, buyer A’s value, and in this market the other buyers’ willingness to take other houses leaves no tighter bound. The narrow band of house 3 is a house two buyers value at 8 and 7 against a reserve of 4, where the second-highest value nearly pins the price.

At the low end every price is a second price, in the sense familiar from single-item sealed-bid auctions: what the winner pays is set by the best alternative bid, not by their own. The core generalises that to many houses at once, with the twist that a house’s second price depends on what happens in the markets for the other houses.

What the picture cannot show #

The polygon is exact, but it is two-dimensional only because the market has two houses. With more, the core is a polytope in as many dimensions as there are matched pairs, and only its extreme points and the intervals they project to can be shown. The lattice structure does not help draw it; it helps describe it.

The figures also take values as known and reported truthfully. The core is a statement about which outcomes are stable given the values, and says nothing about how anyone learns them. That the buyers’ corner is also the outcome of a truthful mechanism is a separate theorem, and it has a sharp limit: the same mechanism is not truthful for the sellers, and no mechanism can make every participant on both sides want to report truthfully while also producing an efficient, individually rational outcome with balanced payments. The picture shows the set of stable outcomes, not how a market chooses among them.

And the model assumes each buyer wants at most one house. Once buyers want bundles — two adjacent plots, a set of broadcast licences — the core can be empty, and the lattice and its corners can disappear.

Still open: markets where buyers want more than one thing #

For single-unit demand, everything above is settled: the core is the dual optimum, it is a non-empty lattice, and its corners are the marginal contributions. The open questions begin where that assumption fails.

When buyers want bundles, a competitive equilibrium exists under a condition called gross substitutes — raising the price of one item never lowers demand for another — found by Alexander Kelso and Vincent Crawford in 1982, and it is known to be essentially the largest condition under which one is guaranteed. Outside it, markets can have empty cores and no clearing prices at all, and how to design auctions for such markets — spectrum licences are the standard case — is a subject in which the best known methods are engineered rather than derived, and in which which outcome to aim for when the core is empty has no agreed answer. Even with single-unit demand one question remains a matter of choice rather than theorem: which point of the core a fair procedure should select. The two corners favour one side completely; the nucleolus, the midpoint between the corners and several other rules have been proposed, and each is defensible and none is compelled.