Date: 9 November 2026, Monday
Time: 10.30 – 11.30
Place: MA-330
“Coordinating Markets via Perturbed Prices”
by
Süleyman Kerimov
Rice University
Abstract
We study the online allocation of finite, non-replenishable resources to self-interested buyers with private types who demand bundles of goods. The planner knows the type distribution and associated valuations but does not observe each arriving buyer’s type. This informational constraint creates an implementability gap: type-observing allocation policies achieve constant regret, whereas conventional bid-price mechanisms, though implementable under private type information, can incur regret on the order of √T, where T is the number of buyers. The gap arises because posted prices can induce indifference, leaving the buyer’s action not uniquely determined.
We close this gap with Perturbed Posted Price (PPP), an online and anonymous mechanism that posts a single vector of item prices together with a type-independent payment adjustment that depends on the chosen lottery over bundles. The adjustment induces the
randomization needed when buyers are indifferent while preserving decentralized buyer self-selection. We prove that PPP achieves constant regret relative to the hindsight first-best for online packing (network revenue management), with a bound independent of both the
horizon and initial inventory. We also extend our construction to online matching.
To the best of our knowledge, PPP is the first online, anonymous mechanism based on a single price vector to achieve constant regret in these private-information allocation settings. The mechanism is derived from a nonsmooth regularization of the fluid relaxation, revealing a broader role for regularization as a mechanism design instrument: it selects implementable behavior at indifference while stabilizing the allocation target against stochastic demand fluctuations.
Bio
Süleyman Kerimov is an assistant professor of operations management at the Jones Graduate School of Business at Rice University. He holds a Ph.D. in operations research from Stanford University and a B.S. in mathematics from Bilkent University. He works on market design, applied probability, and healthcare operations.