Posted Price Mechanisms for Online Allocation with Diseconomies of Scale

Hossein Nekouyan Jazi, Bo Sun, Raouf Boutaba, Xiaoqi Tan

TL;DR

This paper introduces r-Dynamic, a novel randomized dynamic posted-price mechanism for online resource allocation when production costs increase with scale (diseconomies of scale). By independently randomizing the price of each unit based on custom probability distributions, the algorithm achieves optimal performance for small inventories and outperforms existing mechanisms for large inventories, closing a critical gap in algorithmic mechanism design.

What Problem Does This Paper Address?

Traditional online resource allocation algorithms usually assume a fixed inventory with zero or constant marginal costs. However, real-world systems frequently face diseconomies of scale—situations where supplying each additional unit costs more than the last. For example, cloud data centers experience superlinear power consumption costs as server utilization climbs, and network routing suffers severe congestion delays as traffic intensity grows.

The authors tackle the Online $k$-Selection with Diseconomies of Scale (OSDoS) problem. Here, a seller has $k$ units of an item to sell to sequentially arriving buyers with private, bounded valuations ($v_t \in [L, U]$). The seller must instantly post a price $p_t$ to each buyer without knowing future demand. The core challenge is a delicate balancing act: price items too low early on, and you burn through inventory on low-value buyers while rapidly driving up your own marginal production costs; price too high, and you miss out on mutually beneficial trades.

Prior solutions were either deterministic (which perform poorly with small inventories) or randomized-static (which fail to scale efficiently as inventory grows).

Methods

The authors propose a representative function-based approach to model the dynamics of any randomized online algorithm using a sequence of $k$ probabilistic allocation functions.

  1. Establishing a Tight Lower Bound: They construct a family of adversarial "hard instances" where buyer valuations arrive in incrementally increasing waves. By analyzing how an $\alpha$-competitive algorithm must perform on these instances, they formulate a system of differential equations to compute a tight, discrete lower bound ($\alpha^*_{\mathcal{S}}(k)$) without relying on unrealistic continuous/fractional approximations.
  2. The r-Dynamic Algorithm: By reverse-engineering these differential equations, they derive unique inverse probability functions ($\phi_i$) for pricing each unit. At initialization, the algorithm generates a vector of independent random seeds. As buyers arrive, the price for the $i$-th unit is sampled from its specific distribution $\phi_i$. The pricing intervals are chained together sequentially so that the posted prices are guaranteed to be non-decreasing over time, naturally mirroring the rising marginal production costs.

Datasets

The authors evaluated their mechanism using synthetic datasets designed to simulate three distinct buyer arrival patterns (1000 buyers per trial, averaged over 300 instances):

  • Instance-IID: Buyer valuations are drawn randomly from a truncated normal distribution $N(15, 15)_{[1,30]}$.
  • Instance-Sorted: Valuations are generated via the IID method but sorted in ascending order to mimic the theoretical worst-case adversarial environment.
  • Instance-Low2High: A two-phase arrival pattern where low-value buyers ($N(7.5, 7.5)$) arrive first, followed entirely by high-value buyers ($N(22.5, 7.5)$).

Key Insights and Ideas

  • Discrete vs. Fractional Analysis: Previous literature mapped discrete allocation problems to fractional counterparts to find lower bounds. This paper proves that analyzing the problem directly in the discrete domain yields a much tighter and more practical bound for finite inventories.
  • Unit-Independent Randomization: Instead of picking one global randomized pricing strategy, r-Dynamic uses a completely different cumulative distribution function (CDF) to price each individual unit independently based on current inventory depletion.
  • Adversarial Robustness: The non-decreasing structure of the chained pricing intervals prevents the algorithm from being tricked by early waves of low-value buyers, making it highly robust against adversarial manipulation.

Key Results

  • Exact Optimality for Small Inventory: The authors prove mathematically that r-Dynamic is exactly optimal when $k=2$, perfectly matching the theoretical lower bound.
  • Fast Asymptotic Convergence: For large inventory sizes, r-Dynamic converges to the lower bound significantly faster than previous deterministic dynamic pricing models.
  • Empirical Superiority: In numerical simulations (using $k=10$), r-Dynamic dramatically outperformed both deterministic dynamic pricing (d-Dynamic) and randomized static pricing (r-Static) on the challenging Instance-Sorted and Instance-Low2High benchmarks, tracking remarkably close to the absolute lower bound.
Figure 1: The blue curve (i.e., r-Dynamic) corresponds to the competitive ratio of Algorithm 1 that uses randomized dynamic pricing. The red curve (i.e., d-Dynamic) and the yellow curve (i.e., r-Static) corre- spond to the competitive ratios of the deterministic dynamic pricing mechanism developed by [Tan+23] and the static randomized pricing mechanism by [Sun+24]. In this figure, we set 𝐿= 1, 𝑈= 10, and 𝑓(𝑖) = 𝑖2

Limitations and Future Work

  • The Intermediate Inventory Conjecture: While r-Dynamic is proven optimal for $k=2$ and asymptotically optimal as $k \to \infty$, proving exact optimality for intermediate inventory sizes ($k \ge 3$) remains an open conjecture that requires a more refined mathematical analysis.
  • Single-Item Constraint: The current mechanism only supports a single type of resource. Extending these randomized dynamic pricing principles to multi-resource or combinatorial settings (where buyers bid on bundles of interdependent items) is a vital next step for real-world cloud computing applications.
  • Alternative Metrics: The objective is strictly focused on maximizing social welfare. Future iterations could incorporate other practical metrics such as revenue maximization, risk constraints, or buyer fairness.

Summary updated

Abstract

This paper addresses the online $k$-selection problem with diseconomies of scale (OSDoS), where a seller seeks to maximize social welfare by optimally pricing items for sequentially arriving buyers, accounting for increasing marginal production costs. Previous studies have investigated deterministic dynamic pricing mechanisms for such settings. However, significant challenges remain, particularly in achieving optimality with small or finite inventories and developing effective randomized posted price mechanisms. To bridge this gap, we propose a novel randomized dynamic pricing mechanism for OSDoS, providing a tighter lower bound on the competitive ratio compared to prior work. Our approach ensures optimal performance in small inventory settings (i.e., when $k$ is small) and surpasses existing online mechanisms in large inventory settings (i.e., when $k$ is large), leading to the best-known posted price mechanism for optimizing online selection and allocation with diseconomies of scale across varying inventory sizes.
BibTeX
@inproceedings{jazi2025posted,
  author = {Hossein Nekouyan Jazi and Bo Sun and Raouf Boutaba and Xiaoqi Tan},
  title = {{Posted Price Mechanisms for Online Allocation with Diseconomies of Scale}},
  booktitle = {The Web Conference},
  year = {2025},
}
Figure