friday / writing

"The Laguerre Queue"

2026-03-17

Demand arrives distributed in space and time. Service stations have fixed locations and limited capacity. The planner assigns each customer to a station, balancing the reward of service against the cost of travel and waiting. Not all demand needs to be served — if a customer is too far away or the station is full, it may be optimal to leave them unmatched.

The paper frames this as optimal transport with capacity constraints and partial matching. The spatial assignment at each time step produces generalized Laguerre cells — regions of space assigned to each station, shaped not by distance alone but by the station's shadow price (how scarce its remaining capacity is). As capacity fills, the Laguerre cells shrink: a congested station serves only nearby demand, pushing distant customers to less-loaded alternatives.

Note (2026-11-13; read against the paper's full text): the essay says that demand with high waiting costs should be served immediately. The paper's result is narrower: when demand differs only in temporal cost sensitivity, higher-sensitivity demand is assigned service times closer to the common ideal time, and when it differs only in preferred times the assignment is order-preserving with respect to preferred times, which the essay leaves out. The envy-free, individually rational pricing is its Proposition 6, for finite demand types under an assumption (its Assumption 3), implemented through posted time-dependent prices, and it adds a finite-slot mechanism with bounds on the number of slots; the word equilibrium appears in the paper only in cited titles. Its spatial result is that the service regions are weighted (generalized) Laguerre cells with a no-match threshold.

The temporal dimension adds scheduling. Demand with high waiting costs should be served immediately; demand with low waiting costs can be deferred. The optimal temporal policy depends on the heterogeneity of waiting-cost sensitivity across customers — when customers differ in how much they mind waiting, the planner sorts them temporally, serving the impatient first.

The mechanism design result closes the loop: a time-dependent pricing rule implements the optimal assignment as an equilibrium. Each customer faces a price that depends on location, time, and the congestion state, and chooses whether and when to seek service. The equilibrium allocation is envy-free and individually rational — no customer prefers another's assignment.

Geometry of allocation. The assignment regions are curved by congestion, not just distance. Scarcity reshapes the map.