Concept

Market clearing

A state of prices at which every buyer is content with what they get and nothing is left over that someone would pay more for. In the assignment problem such prices exist, and they are exactly the dual certificate that proves an assignment is the best.

Named by 2 essays across one field — each of them below, with the objects they name alongside it.

An auction for 4 objects, bid by bid, with increment 1/5. A 4 by 4 table of values beside the log of 12 bids of an auction with increment 1/5: bidder, object, the raise, and the prices after each bid; it ends with total value 26.

Prices the bidders raise

The cheapest assignment is certified by a price on every task, and those prices can be found without anyone in charge. Let each unassigned person bid for the task that suits them best at current prices, raise its price by a little more than it is worth to them over the next best, and wait. The bidding ends, and when the increment is small enough the prices it ends at are a proof of optimality.

applied · Assignment

The core of a market with two houses and two buyers. The core of an assignment game drawn in the plane of buyer A's payoff against buyer B's, a polygon with vertices (0, 1), (0, 0), (1, 0), (4, 3), (2, 3); the buyers' best corner is (4, 3).

The prices nobody can break away from

When houses are sold to buyers who value them differently, there is a whole range of prices at which nobody wants to walk away, and it has a remarkable shape — one corner best for every buyer at once, one best for every seller at once, and the buyers' corner pays each buyer exactly what the market would lose without them.

applied · Assignment

Named alongside it

The objects these essays reach for when they reach for this one.

Assignment Duality Linear programming Algorithm Certificate Complementary slackness Core Lattice Marginal contribution

All concepts