Prices for things wanted only together

In every market drawn so far, each buyer wanted one thing. Each person took one task, each buyer one house, and that single restriction made the theory unusually generous. The prices nobody can break away from found a whole polygon of prices at which every buyer holds the house they like best and nobody wants to walk away, and prices the bidders raise found a procedure that reaches one of them without anyone in charge. Both rested on the fact that the best assignment can be found by a linear program whose corners are whole numbers, which the corners are whole assignments proved and where the corners stop being whole showed to be fragile.

Real markets are full of buyers who want things together. A delivery company bidding for landing slots wants the slot at the far end of the route as well as the near one, since either alone is useless. A mobile operator bidding for radio licences wants adjacent regions so that its network covers a whole territory. A buyer of a left shoe has no use for it without the right. In each case the value of a pair is more than the value of its parts, and the items are called complements.

This essay asks what complements do to prices. The answer is that clearing prices — one price per item, at which every buyer is content with what they are given and nothing that could be sold is left over — can cease to exist, and that whether they exist in a given market is decided by one comparison between two numbers that were already in play.

The smallest market that cannot be priced #

The figure above holds the whole phenomenon in its smallest form. There are two items, A and B. Buyer 1 wants both together and values the pair at 3; a single item is worth nothing to them. Buyer 2 wants one item, either will do, and values it at 2. The best way to hand the items out is to give both to buyer 1, worth 3, against 2 for giving one item to buyer 2.

Now look for prices. A price on each item, $p_A$ and $p_B$, makes each buyer prefer some set of items: the one that leaves them the most value after paying. For the allocation that gives buyer 1 the pair to be stable, buyer 1 must want the pair at these prices, so $p_A + p_B \le 3$ — the triangle. And buyer 2, who gets nothing, must want nothing, which means neither item is worth buying: $p_A \ge 2$ and $p_B \ge 2$ — the square. A point in both would need $p_A + p_B$ to be at most 3 and at least 4. There is none.

The other allocations fare no better. Give item A to buyer 2 and leave B unsold, and an unsold item must be free, since a seller with something left on the shelf at a positive price would cut it. But at $p_B = 0$ buyer 2 would rather have B than pay anything for A, so $p_A$ must be nought too, and at prices of nought buyer 1 wants the pair. Every allocation has a buyer who would rather have something else at any prices that make the others content. The figure’s arithmetic checks this not by argument but by search: every allocation was tested against every pair of prices on a grid of quarters from 0 to 6, and none clears.

What has gone wrong is easy to state. Buyer 2 is willing to pay up to 2 for either item, so to keep buyer 2 out of the market both items must cost at least 2. Buyer 1 values the pair at 3, which beats buyer 2’s 2 for one item, but cannot afford 4. The market has a winner, and no way of letting the prices say so, because a price is attached to an item and buyer 1’s value is attached to the pair.

The gap that decides it #

The numbers printed beside the first figure say more than that one market failed. The best whole allocation is worth 3. The other number, the relaxation, is the best value of the market when items may be shared fractionally: each buyer takes a fraction of each set they are interested in, no buyer takes more than one set in total, and each item is handed out at most once in total. That is a linear program, the same kind of object as the one behind every assignment in this series, and its best value here is $7/2$.

The theorem that connects the two numbers is due to Sushil Bikhchandani and John Mamer, in 1997: clearing prices exist if and only if the relaxation is worth no more than the best whole allocation. When the two agree, the relaxation’s dual solution — the prices that a price for every person and task used to certify optimality — are clearing prices. When the relaxation is worth more, there are none.

The sweep tests the theorem at twenty-five values of the pair. When buyer 1 values the pair at 4 or more, the pair goes to buyer 1, the relaxation agrees, and prices such as 2 for each item clear the market. At a value of exactly 0 buyer 1 is not in the market at all and buyer 2 can be sold an item at price 0. Everywhere strictly between, the lines separate and the grid search finds no clearing prices — including the values between 0 and 2, where the best whole allocation gives an item to buyer 2 rather than the pair to buyer 1, and the market still cannot be priced. Buyer 1’s presence is enough: at prices low enough for buyer 2 to buy, buyer 1 wants the pair too.

The direction of the theorem that needs proof is the one that turns a gap into an impossibility, and it is the familiar argument of duality. If prices clear the market, then each buyer’s surplus at those prices, plus the prices of all the items, adds up to the value of the allocation being made. But those same prices and surpluses form a feasible point of the relaxation’s dual, which bounds every fractional allocation from above. So the fractional allocations are worth no more than the whole one, and there is no gap. Clearing prices are a certificate that the market’s best fractional allocation is whole, and when it is not, no certificate can exist.

What the relaxation does instead #

The relaxation’s best point, when it beats every whole allocation, is not a mystery. It is a schedule that no market can carry out.

Half the pair goes to buyer 1, and buyer 2 takes half of A and half of B, which together make one item’s worth of the single item buyer 2 wants. Each item is used exactly once: half to buyer 1 and half to buyer 2. The value is $3/2 + 1 + 1 = 7/2$. And the relaxation’s dual prices, $3/2$ for each item, clear this fractional market: buyer 1 is exactly indifferent between paying 3 for the pair and having nothing, and buyer 2 is indifferent between A and B at a surplus of $1/2$ each. Every buyer is content with their fraction, every item is fully sold, and the arithmetic of duality closes perfectly.

The trouble is that the schedule is a lottery over allocations that do not fit together, rather than a lottery over whole assignments of the kind every table of shares turned out to be when buyers wanted one thing each. In the single-unit world, a fractional schedule could always be taken apart into whole allocations, each of them feasible. Here it cannot: the half-pair and the two half-items can only be realised by a lottery in which one outcome gives the pair to buyer 1 and another gives buyer 2 both items, which buyer 2 does not want and which wastes one of them. The relaxation is counting a combination that the whole market cannot achieve, and that combination is exactly what prices cannot exclude.

Three pairs around a triangle #

The two-item market fails because one buyer wants a pair and another wants a part of it. A purer failure involves only pairs.

Each buyer wants a different pair of the three items A, B and C, and values it at 2. Any two pairs share an item, so a whole allocation serves at most one buyer and is worth 2. The relaxation gives each buyer half their pair, which uses every item exactly once in total — each item lies in two pairs, each pair at one half — and is worth 3. The relaxation is half as large again as anything a whole allocation can do, and so there are no clearing prices. A direct check confirms it: if the pair AB is sold and C is not, C must be free; then the buyer of AC must not want AC, so A costs at least 2, and likewise B costs at least 2, and the winner pays 4 for a pair worth 2.

This is the triangle of where the corners stop being whole, now carrying prices. There, adding a single edge that closed an odd cycle to a matching problem produced a corner with a half in every coordinate. Here the items are the vertices, the buyers are the edges, and the market is a matching problem on a triangle — so the odd cycle produces the same half-corner, and the half-corner produces the absence of prices. The relaxation’s dual prices are 1 on each item, at which each buyer is exactly indifferent to their pair, and they would clear the market if items could be sold in halves.

The same triangle appears, in another vocabulary, in a split nobody can walk away from, where three players each able to earn something in pairs left a cooperative game with an empty set of stable divisions. That is no accident. In a market, clearing prices give a point of the core — a division of the gains that no group of buyers and sellers can improve on by trading among themselves — and when buyers want pairs that overlap in an odd cycle, the core of the market can be empty for the same reason that game’s was.

A rising-price auction that stalls #

When prices exist there is a natural way to find them, and it is the auction of prices the bidders raise generalised to sets: start every price at nought, ask each buyer which set they want at the current prices, and raise by a small step the price of every item that more than one buyer asks for. Alexander Kelso and Vincent Crawford showed in 1982 that, under a condition to be described in the next section, this process ends at clearing prices. On the pair market it does something else.

At the start buyer 1 asks for the pair and buyer 2 for item A, so A is contested and its price rises. Buyer 2 switches to the cheaper B, which is now contested, and its price rises. The two prices climb alternately up a staircase, buyer 2 always choosing whichever is cheaper and buyer 1 always wanting both, until the pair costs 3, buyer 1’s whole value. Then buyer 1 drops out. Buyer 2 takes A, nobody is contesting anything, and the auction stops. B sits unsold at a price of $3/2$.

That is not an outcome a market can rest at. The seller of B would rather sell at a lower price than not at all. But lower B’s price and buyer 1 wants the pair again, buyer 2 may switch to B, and the contest restarts. The process does not converge because there is nothing to converge to.

It is also unfair to buyer 1 in a way that has a name. Suppose buyer 1 had stayed in a little longer and won A at $3/2$ before dropping out of B. They would hold one item, worth nothing to them, and have paid for it. A bidder who wants a pair and bids on its items one at a time is exposed to winning half of what they want, and auction designers call it the exposure problem. Prices on single items are the root of it: a buyer cannot express “both or neither” in a language that has only one price per item.

When values add, prices always exist #

Change one thing about buyer 1. Instead of valuing the pair at 3 and each item at nothing, let them value each item at $3/2$, so that the pair is still worth 3 but only as the sum of its parts. The best whole allocation is now to give one item to each buyer, worth $3/2 + 2 = 7/2$, exactly the relaxation’s value in the first market. And the rising-price auction behaves.

The path is the same staircase. What changes is the place it stops: at $3/2$ for each item, buyer 1 is indifferent to one item at its price and buyer 2 is happy with the other, so an allocation exists that sells everything to a buyer content with it. The prices clear.

The condition behind this is gross substitutes, Kelso and Crawford’s name for it: raising the price of one item never makes a buyer drop their demand for another item. A buyer with additive values satisfies it, since each item is judged on its own. A buyer who wants exactly one item satisfies it, since a rise in one price can only move them to another item. A buyer who wants a pair does not: raising the price of A can make the pair too expensive, and then they drop B as well. Faruk Gul and Ennio Stacchetti showed in 1999 that gross substitutes is in a precise sense the largest condition on single buyers that guarantees prices — for any valuation outside it, there are markets of buyers with one-item demands into which it can be placed so that no clearing prices exist.

The sweep can be run with buyer 1’s values made additive, and it reports what the theorem predicts: the relaxation and the best whole allocation coincide at every one of the twenty-five values, and prices exist at every one. Complementarity, not the size of anyone’s values, is what breaks the market.

How often a random market can be priced #

How common the failure is depends on how common complements are. The census draws random markets with three items and three buyers, all values whole numbers from 1 to 8, of four kinds, and decides each exactly: the relaxation is solved in exact rational arithmetic, the best whole allocation by exhaustion, and when the two agree the relaxation’s dual prices are checked to clear the market.

The first two bars are the theorem’s guarantee: one-item buyers and additive buyers satisfy gross substitutes, and every one of their markets has prices. The third bar is a surprise in the other direction. When each buyer wants a single random bundle and nothing else, prices exist 98% of the time, because the failures need a particular overlap pattern — an odd cycle of pairs, or a pair contested by a buyer of one of its parts — and three random bundles of three items rarely form one. The fourth kind deliberately builds in the pattern of the first figure: a buyer wants a pair whole, and others bid smaller amounts on single items. Almost a third of those markets cannot be priced at all.

What the pictures do not show #

All the figures concern tiny markets, chosen so that every claim could be checked exhaustively, and three items cannot show how the failure scales. In real auctions with dozens of licences and bidders who want overlapping regions, the relaxation and the best whole allocation generally differ, and the theorem then says something stark: no item prices will support the efficient allocation, however they are found.

The theorem also says nothing about prices on bundles. If each set of items can carry its own price, rather than prices being sums of item prices, then clearing prices can be restored — at the cost of exponentially many prices, and of prices that differ from buyer to buyer in the most general versions. The combinatorial auctions used to sell radio spectrum since the 2000s take this route: bidders bid on packages, and the auctioneer solves a whole allocation problem to decide the winners.

And the figures say nothing about strategy. Every buyer here reports their values truthfully and chooses what is best at the posted prices. In an actual auction a buyer may shade their bids, and with complements the incentive to do so is strong, since a buyer who wants a pair benefits from others believing they will not bid high.

Still open: what to aim for when nothing clears #

When the core of a bundle market is empty, there is no outcome that every coalition accepts, and auction designers must choose what to aim for instead. The package auctions in use pick payments from the core of a modified game, or as close to it as possible, or minimise how much any coalition could gain by deviating; each choice is defended and none is forced by the mathematics, which is the situation the single-unit market was in when choosing a point inside a non-empty core, made worse.

Two questions are sharper. The first is about size. With a continuum of small buyers, each negligible, Eduardo Azevedo, Glen Weyl and Alexander White showed in 2013 that clearing prices exist even when buyers want complements, because a market in which no buyer matters can smooth over the indivisibility that broke the two-item example. How close to clearing a finite market can be brought, as a function of how many buyers it has and how large the bundles they want are, is not settled in general; the known bounds shrink as the market grows, and how fast they must shrink is open.

The second is about structure. Gross substitutes is the largest condition on single buyers that guarantees prices whatever the other buyers want, but markets in practice mix substitutes and complements in patterns, and a market can clear even though some of its buyers violate the condition, as most of the single-bundle markets in the census did. Which patterns of complementarity among the buyers of a market guarantee prices — whether, for example, every market whose wanted bundles form a structure with no odd cycle of overlaps can be priced — has answers for particular structures, such as bundles that are intervals of a line, and no general description.