Optimal dynamic pricing designs emerge from nonlinear equation solutions

Beyond a Single Optimal Design: A Dynamical Systems Characterization of Online Allocation with Convex Costs

Computer Science and Game Theory

Summary

This work studies how to best set prices when resources can be produced dynamically but at increasing costs. Instead of finding just one best algorithm, the authors show there are actually many optimal pricing strategies that can achieve the best possible balance between cost and allocation efficiency. They use a mathematical approach involving dynamical systems and nonlinear eigenvalue problems to understand these pricing rules. This new perspective unifies past methods and reveals that mixing fixed and changing prices can be just as good as fully dynamic pricing. Their results also provide improved pricing strategies when future demand or supply constraints are uncertain or limited.

What this means in practice

  • For e-commerce platform operators: Design pricing algorithms that flexibly combine fixed and dynamic prices to optimally allocate limited inventory with variable restocking costs.
  • For cloud resource managers: Develop resource allocation policies that dynamically price compute or storage capacity reflecting convex production costs and uncertain demand.

A theory result. No direct application yet.

Authors

Haoxin Sang, Bo Sun, Xiaoqi Tan

Abstract

We study online allocation with convex costs (\OACC), a generalization of limited-supply models in which additional resources can be produced dynamically at convex cost. Prior work largely focuses on constructing a single algorithm that achieves strong competitive guarantees. In contrast, our main contribution is a structural characterization of the optimal design space of reserve functions (i.e., normalized pricing rules) for \OACC, yielding a family of optimal online algorithms. Using a principled dynamical-systems approach, we show that optimal online algorithms arise as solutions of a nonlinear eigenvalue problem: the optimal competitive ratio corresponds to the dominant eigenvalue, and the associated eigenfunction determines the optimal reserve function. This perspective establishes the existence of infinitely many optimal designs attaining the best possible competitive ratio, thereby unifying and generalizing a broad class of prior algorithms. Beyond unification, our characterization uncovers new structural phenomena, including the ability to flexibly mix dynamic and static pricing without loss of optimality and the construction of universally competitive algorithms under unknown or stochastic costs. We further extend the analysis to more structured settings such as supply-oblivious arrivals and hard supply constraints, obtaining sharper guarantees that improve upon previous bounds.
View PDFOpen arXiv