Chapter 17. The Assignment Problem

Market clearing prices, the Hungarian method, and the ascending-price LLP algorithm.

This page: LLP forms. View classical forms »

The assignment problem

Given $n$ bidders and $n$ items with valuations $v[b, i]$, find an assignment (perfect matching) and a price vector $C[1..n]$ such that every bidder is assigned to a most-preferred item at the given prices. Equivalently, find the minimum market clearing price vector: the smallest prices such that the preferred-items graph (edges to items maximising $v[b, i] - C[i]$) contains a perfect matching.

Overdemanded sets

A set $J$ of items is overdemanded if the set of bidders who prefer items in $J$ is strictly larger than $|J|$. By Hall's theorem, a perfect matching exists iff no overdemanded set exists. The LLP formulation uses overdemand as the forbidden predicate.

ConstrainedMarketClearingPrice

The high-level LLP algorithm. The price vector $G$ starts at zero. Forbidden detects items $j$ belonging to a minimal overdemanded set; advance raises $G[j]$ by one. The fixed point is the minimum clearing price vector.

Time complexity: $O(n^3)$, where $n$ is the number of agents.

int[] ConstrainedMarketClearingPrice(int[][] v) {
  int n = v[0].length;
  int m = v.length;
  int[] G = new int[n];
  forall k in [0..n-1] : G[k] = 0;
  forbidden (j) : isOverDemanded(j, v, G) =>
    advance : G[j] = G[j] + 1;
  return G;
}

LLP-Assignment

A more efficient implementation that raises prices by the minimum amount $\delta_j$ needed to shift a bidder away from item $j$. The algorithm iteratively checks for a perfect matching in the preferred-items graph; when none exists, it identifies the minimal overdemanded set and raises prices accordingly.

Time complexity: $O(n^3)$ via the Hungarian / LLP fixpoint, where $n$ is the side length of the cost matrix.

int[] LLPAssignment(int[][] v) {
  int n = v[0].length;
  int m = v.length;
  int[] C = new int[n];
  forall k in [0..n-1] : C[k] = 0;
  boolean done = false;
  while (!done) {
    boolean hasMatching = checkPerfectMatching(v, C);
    if (hasMatching) { done = true; }
    else { raiseOverdemandedPrices(v, C); }
  };
  return C;
}

LLP predicates for this chapter

Each LLP program in this chapter defines a state vector $G$ and a forbidden predicate; the algorithm runs until no $j$ is forbidden. The table below lists, for each algorithm, what $G[j]$ represents and the negation of the forbidden clause from the matching .llp source.