CS Paper Radar

A Stochastic Growth Model for Online Platforms

Farbod Ekbatani, René Caldentey

cs.GT ·submitted 2026-10-12 22:03 UTC · v1
top venue

Abstract

We investigate the growth trajectory of online platforms operating as market makers in two-sided matching markets. Their expansion, often referred to as the ``chicken-and-egg dilemma'' in the literature, poses an inherent challenge: service providers find value in joining the platform because of the presence of customers, while customers are drawn to the platform by the availability of service providers. Much of the existing literature addresses this expansion challenge through either a static market-clearing lens or aggregate dynamic models, emphasizing how network externalities shape a platform's growth trajectory and equilibrium size. These approaches do not fully capture how gradual growth must be implemented through server-level admission, assignment, and compensation decisions. Embedded in this growth process are intertemporal participation constraints that the platform must satisfy to attract and retain forward-looking servers. To explicitly account for the stochastic dynamics of a platform's gradual growth, we model the system as a Markov process. Potential servers and customers arrive according to Poisson processes, and customer demand is non-decreasing in the number of active servers. Under mild conditions, we characterize the platform's optimal admission, assignment, and compensation policies. The platform admits servers at the maximum feasible rate until it reaches an endogenous target size, which can be smaller than the static market-clearing optimum. In the baseline model, seniority-based compensation acts as an operational substitute for financially subsidized growth: instead of using upfront subsidies to induce early server participation, the platform uses future cash flows to reward early servers for joining when demand is limited and for helping the platform reach later, higher-demand states.

Closest papers

Nearest neighbours by meaning across the whole index.

Equilibrium Joining Strategies for Queues in Two-Phase Random Environment

cs.GT math.PRcs.NI ·2026-09-26 ·Konstantin Avrachenkov, Uri Yechiali
published similarity 0.55
Abstract · This paper has been accepted at the 29th International Conference on Analytical and Stochastic Modelling Techniques and Applications (ASMTA …

We study equilibrium joining strategies in an M/M/1-type queueing system with strategic customers operating in a two-phase random environment described as a continuous-time Markov process. Strategic customers, upon arrival, choose whether to join or to balk based on available information and anticipated utility, considering the trade-off between reward from service and waiting cost. Four observation scenarios are analysed: fully observable (both queue length and environment phase are disclosed to a customer upon arrival), queue-only observable, environment-only observable, and fully unobservable. In each case, equilibrium joining strategies are analysed. In the environment-only observable and fully unobservable cases, explicit solutions and equilibrium conditions are derived under rapid oscillations and under very slow transitions between environment phases.

0.37

Stochastic Aggregation with Prescribed Resources and Additive Delay

cs.DS ·2026-11-10 ·Tianhang Lu, Runtian Ren, Shengcai Liu
similarity 0.55
Abstract

We study online aggregation with prescribed resources and additive delay. In this problem, we are given a finite set of resources with purchase costs and a collection of request types, each specifying the resources it requires. Requests arrive over time, and each request can be served immediately or postponed to a later time. A service may serve several pending requests together by purchasing every resource required by at least one of them, paying for each purchased resource only once. These purchases serve only the current batch; resources needed in a later service must be purchased again. A request served $t$ units of time after its arrival incurs delay cost $t$. The objective is to serve all requests while minimizing the sum of resource purchase costs and individual delay costs. We consider a stochastic version of this problem in which requests of each type follow an independent Poisson process of known rate. An online algorithm knows these rates but observes requests only upon arrival. We compare its expected cost with that of an offline optimum that knows the entire realized input and may choose every batch freely. A resource--scale linear program supplies both an offline lower certificate and synchronized service periods. This yields a deterministic online algorithm with polynomial-time preprocessing on rational input and a long-run ratio of expectations below $2.113$. The guarantee applies in particular to rooted multi-level aggregation and prescribed-pair aggregation on trees. Besides, for Poisson TCP acknowledgment, we further characterize the optimal long-run ratio of expectations at every load, showing that its worst-case value is approximately 1.409 and is attained by a deterministic online policy.

0.17

Dynamic Matching with Abandonment: Optimal Guarantees via Static Priority Policies

cs.DS cs.CCcs.GTecon.TH+1 ·2026-10-09 ·Nick Arnosti, Rad Niazadeh, Pranav Nuti, Felipe Simon
benchmarktheory similarity 0.54
Abstract

We study stochastic dynamic matching with abandonment, a fundamental model in which agents of different types arrive over time, may abandon the market while waiting, and can be matched in pairs for rewards that depend on their types. No online policy can guarantee more than $0.5$ of the omniscient benchmark, which knows all arrival and departure times. Whether this guarantee is achievable has been a central open problem, even in special cases. We resolve this problem by showing that, on every instance, a simple static priority policy, which is computable in polynomial time, earns at least $0.5$ of the omniscient benchmark. This establishes that the optimal competitive ratio is exactly $0.5$, improving the previous best guarantee of 0.192 for the general model [Li et al. 2026; Collina et al. 2020] Our analysis rests on a key stochastic result, which is a new lower bound on the probability that some agent from a given set of types is available. Building on this bound, we develop two approaches: a primal approach that reads the priorities from an optimal solution of a novel linear program, and a dual approach that assigns a ``value'' to each type, and prioritizes matches with high ``surplus'' (reward minus value of involved agents). These values are the unique solution of a fixed-point equation derived from linear programming duality. We also show that the two approaches are closely connected.

0.39

Spot Markets for AI Inference: Dynamic Capacity Allocation and Pricing on a Shared Accelerator Fleet

eess.SY ·2026-11-08 ·Quanyan Zhu
similarity 0.53
Abstract · 39 pages, 12 figures, 4 tables

Inference providers size their accelerator fleets for the interactive peak and sell spare capacity through fixed discounts, such as batch tiers at half price. However, inference differs from conventional cloud capacity in four respects: capacity depends on the latency tier through batching, moving weights between models is slow and costly, spot demand can wait until its deadline, and power can bind. In this paper, we develop a framework for dynamic capacity allocation and pricing of AI inference on a shared accelerator fleet. We consider a provider that serves several models under a power cap and sells each model in an interactive tier with a speed promise and in a spot tier for preemptible work with a deadline. In each period, the provider chooses how many replicas of each model to keep loaded and what spot price to quote. We show that one interactive token displaces a fixed number $ρ_m>1$ of spot tokens, and that the optimal spot price lies midway between the interactive price and the effective cost of capacity in the deadline window, which is close to the prevailing half price only when the fleet is slack. We further show that a spot tier raises the optimal reliability of the interactive tier, and that placement should follow persistent demand shifts while prices absorb transients. Building on these results, we design a model predictive controller based on a linear program with explicit approximation bounds, which solves each period in milliseconds. Numerical experiments on a simulated week with a measured daily demand profile, a flash crowd, and a grid curtailment show that the controller raises profit by 7.4% over fixed half-price practice, captures 93% of the gain available with perfect forecasts, keeps the interactive promise through both events, and leaves spot buyers better off.

0.28

Two-Sided Screening in Quality-Differentiated Markets

cs.GT ·2026-11-04 ·Yaohao Liu, Mengfan Ma, Mingyu Xiao
similarity 0.53
Abstract

Motivated by digital marketplaces such as Uber and Airbnb, we study how a two-sided platform designs a menu of qualities, consumer prices, and provider wages. Consumers and providers self-select according to their private values and costs, so the platform must design its menu to attract consumers while inducing enough supply to meet their demand. We study this coordination problem over a continuous quality space, requiring supply to cover demand at every quality threshold. We formulate menu design as an optimization over trading distributions, which specify how much trade occurs at or above each quality. Through convexification of the technological cost function, we characterize the profit- and welfare-optimal trading distributions. This characterization shows how production technology alone can reduce menu size without sacrificing optimal profit or welfare, regardless of the type distributions, and determines when optimal menus can be finite. We then show that profit maximization can be highly efficient: under monotone hazard rate conditions on both sides, a profit-optimal menu achieves at least $1/(e-1)$ of optimal social welfare. We next consider the practical setting in which the menu size is restricted to a prescribed number of offers. We establish how the restricted menu approximates the unrestricted optimum in profit. We develop an algorithm that computes a menu within this size limit in polynomial time. The computed menu simultaneously approximates the unrestricted optimal profit and social welfare with additive error.

0.28

A Sharp Additive Bound for the Threshold Rule in Repeated Rent-or-Buy

cs.DS ·2026-11-03 ·Vasco Schiavo
similarity 0.52
Abstract · 16 pages

Motivated by context management in LLM agents, we study a repeated rent-or-buy model with schedule-independent history growth and a fixed reset price $K$, a discrete form of dynamic TCP acknowledgment: every call pays as rent the history accumulated since the last reset, and a reset clears it. The classical threshold rule is $2$-competitive, and no deterministic rule guarantees a smaller ratio. We show that, measured additively, its loss is governed by the changes in the growth: if the growth is constant on $P$ runs, the threshold rule, knowing neither the runs nor the horizon, pays at most $(2P-1)K$ more than the optimal schedule chosen with hindsight, and the coefficient $2P-1$ is sharp. If the growth is only within a factor $1+\varepsilon$ of $P$ runs, the bound holds up to a factor $1+\varepsilon$ and an extra $\varepsilon K$. The proof is a potential argument built from the relative value functions of the single-rate problems. On two runs no deterministic rule guarantees a loss below $2K$. A rule that also resets when the growth decreases guarantees $2K$, while the threshold rule can lose arbitrarily close to $3K$.

0.30

Online Network Design with Maximum Delay and Stochastic Arrivals

cs.DS ·2026-11-10 ·Tianhang Lu
theory similarity 0.52
Abstract

We study online network services that combine pending requests into batches. Each batch pays for its spatial service and for the waiting time of its oldest request. The objective is the sum of these costs over all batches. Thus requests can share both a spatial purchase and one maximum-delay charge. We assume independent Poisson arrivals of known rates, while actual requests are revealed only upon arrival. For stateless services, suppose that each type has an attainable minimum cost when served alone, that every batch costs at least the stand-alone minimum of each type it contains, and that one finite-cost action can serve any batch, regardless of its request multiplicities. We give a deterministic algorithm with long-run ratio of expectations $e/(e-1)$ against an unrestricted offline optimum. This factor is optimal, even allowing randomization, already at one request location. The key comparison measures the union of time intervals associated with requests. The theorem applies directly to multi-root and pair aggregation on trees. We also study facility location, where each request pays its own connection distance and the bounded-action assumption can fail. A deterministic policy gives a ratio $3$ for arbitrary nonnegative opening costs. It immediately serves a finite initial set of requests, computes an assignment from their observed arrival gaps, and then keeps that assignment fixed. Its analysis combines Poisson insertion with a time-slice packing bound on the offline optimum. Every guarantee includes the full cost of completing finite inputs without an end-of-input signal.

0.15

Stability of Fork-Join Systems with Redundancy and Heterogeneous Servers

cs.IT math.PR ·2026-09-08 ·Chutong Gao, Seyed Iravani, Ohad Perry
similarity 0.52
Abstract · 28 pages, 1 figure. Current status: Reject and Resubmit, Operations Research. Resubmitted on July 26, 2026

We consider the stability problem of fork-join systems with redundancy (FJR) and heterogeneous servers under both static and dynamic capacity-allocation policies. In an $(n,k)$ FJR system, each arriving job is split into $n$ independent tasks, with one task assigned to each of $n$ parallel servers. Once $k \le n$ tasks have been processed, they are joined and the corresponding job departs the system; the remaining $n-k$ unprocessed tasks are then removed and are therefore termed redundant. We first identify the nominal traffic intensity and characterize the maximal stability region, defined as the set of traffic intensities for which there exists an admissible policy that stabilizes the system. We then establish conditions under which this maximal stability region is attained for two classes of policies: static and dynamic. Specifically, we show that for static allocation policies, in which service capacities remain fixed over time, maximality is achieved whenever the fastest server is allocated no more than $1/k$ of the total service capacity. For dynamic allocation policies, in which a fixed total service capacity may be repeatedly reallocated among the servers, we show that maximality is achieved whenever the cumulative capacity allocated to the $j$ shortest queues does not exceed $j/k$ of the total capacity for every $j=1,\ldots,k-1$. Our analysis is based on a projection of the $(n,k)$ FJR system onto a simpler $(k,k)$ system that has no redundancy, together with a novel sample-path comparison argument for multidimensional processes based on the generalized Schur-convex order.

0.31