Papers for

e-commerce platform managers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Online algorithms allocate limited products under increasing returns

Online Stochastic Allocation with Increasing Returns

Abstract: Online resource allocation is a fundamental problem in revenue management, sponsored search, and platform operations. Most prior work assumes nonincreasing assignment rewards, capturing diminishing returns. We instead study increasing returns, where assigning more customers to the same product can unlock larger value through scale, visibility, or network effects. We consider capacity-limited products assigned to sequentially arriving customers, where the reward of each product depends on the total number of customers assigned to it. We focus on full compatibility, where every product can be assigned to every customer. The number of customers is unknown to the online algorithm. We show that representative classical approaches, such as online greedy algorithm and LP-based independent rounding, can perform arbitrarily bad in this setting, even when products share a common bonus function. For homogeneous bonus functions, we give a simple polynomial-time algorithm that achieves a tight $1/2$-competitive ratio. For arbitrary heterogeneous bonus functions, we show that no constant competitive ratio independent of the number of products is possible: for $m$ products, the optimal competitive can be as small as $Θ\left({1}/{\sqrt m}\right)$. This shows that heterogeneous delayed rewards can force any online algorithm to guess the realized arrival counts. We then identify a structured heterogeneous regime that restores a constant guarantee. When each bonus function is nonnegative, nondecreasing, and discrete concave, we design an intermediate target repair algorithm with a deterministic pathwise guarantee of $0.2466$. The algorithm repeatedly computes an offline target for a larger demand level and repairs the current allocation toward it using a prefix-robust assignment order. This coordinates buildup while remaining robust to early stopping and yields a distribution-free guarantee.

Mon 28 SeptData Structures and Algorithms
The gist
Assigning products to customers online is tricky when each product gets more valuable as more customers buy it. This paper looks at algorithms to do this when you don’t know in advance how many customers will show up. The usual methods that work when rewards get smaller over time can fail badly here. The authors design new algorithms that guarantee at least about half of the best possible outcome in simple cases, and they explore limits on performance when products have different reward patterns. They also find a special case where a more complex method still works reliably.
Open → 2609.34121v1