Mixed bundle pricing is a classic revenue management problem arising in industries such as e-commerce, tourism, and video games. It refers to designing product combinations (i.e., bundles) and determining their prices to maximize expected profit. Exact mixed-bundling formulations capture this structure but are computationally intractable because the number of possible bundles grows exponentially with the number of products. We propose a graph neural network (GNN)-guided pruning framework for scalable (non-)additive bundle pricing. Instead of learning on the exponential bundle-level formulation, we encode each instance as a compact customer-product graph and train an edge-output GNN to learn the product-assignment probabilities from optimal mixed-bundling solutions. The predicted probabilities are then converted into restricted candidate bundle families through fixed cutoff pruning and progressive cutoff pruning; the final prices and assignments are obtained by solving the mixed bundling formulation over the retained bundles. We further introduce a GNN-guided local search and an iterative self-improvement procedure for larger instances. The local search refines the retained bundle family by prioritizing high-confidence add/drop moves, while the iterative self-improvement procedure generates high-quality solutions on larger instances for retraining. Theoretically, we show that under mild distinguishability conditions the proposed edge-output GNN class is expressive enough to recover the optimal product-assignment mapping. Experiments show that the proposed policies recover over 98% of the optimal profit on small instances and outperform bundle-size pricing on larger instances with substantial runtime savings.

TL;DR: The misspecification loss due to ignoring demand correlation may increase or decrease in lead time. 

We study a periodic-review inventory system with positive lead time and correlated demand. While most inventory models assume independent demand for tractability, this simplification may lead to model misspecification in practice. We consider a decision maker who implements a myopic base-stock policy based on a misspecified i.i.d. model, while the true demand follows a stationary Gaussian AR(1) process. We derive closed-form expressions for the optimal policy under the true model and for the cost of the misspecified policy, and quantify misspecification loss via a competitive ratio. Our results show that longer lead times do not necessarily amplify misspecification loss. In particular, when demand exhibits positive correlation, increasing the lead time can attenuate the impact of misspecification. At the same time, this misspecification becomes increasingly consequential when backlog penalties are high. Under positive correlation, underestimation of uncertainty leads to persistent understocking and substantial losses, whereas under negative correlation, misspecification induces overstocking and the resulting loss is less sensitive to stockout penalties. Overall, the cost of using a simplified demand model depends not only on demand variability, but also on whether demand exhibits persistence or reversal over time and the relative costs of backlog versus excess inventory.

TL;DR: Use a graph neural network to derive high-quality solutions to large-scale constrained assortment problems within seconds. 

Assortment optimization seeks to select a subset of substitutable products, subject to constraints, to maximize expected revenue. The problem is NP-hard due to its combinatorial and nonlinear nature and arises frequently in industries such as e-commerce, where platforms must solve thousands of such problems each minute. We propose a graph convolutional network (GCN) framework to efficiently solve constrained assortment optimization problems. Our approach constructs a graph representation of the problem, trains a GCN to learn the mapping from problem parameters to optimal assortments, and develops three inference policies based on the GCN's output. Owing to the GCN's ability to generalize across instance sizes, patterns learned from small-scale samples can be transferred to large-scale problems. Numerical experiments show that a GCN trained on instances with 20 products achieves over 85% of the optimal revenue on problems with up to 2,000 products within seconds, outperforming existing heuristics in both accuracy and efficiency. We further extend the framework to settings with an unknown choice model using transaction data and demonstrate similar performance and scalability.

TL;DR: With very few resolvings, we can achieve constant regret (even without the non-degeneracy assumption) for OLP and NRM problems.

Online linear programming (OLP) has gained significant attention from both researchers and practitioners due to its extensive applications, such as online auction, network revenue management, order fulfillment and advertising. Existing OLP algorithms fall into two categories: LP-based algorithms and LP-free algorithms. The former one typically guarantees better performance, even offering a constant regret, but requires solving a large number of LPs, which could be computationally expensive. In contrast, LP-free algorithm only requires first-order computations but induces a worse performance, lacking a constant regret bound. In this work, we bridge the gap between these two extremes by proposing a well-performing algorithm, that solves LPs at a few selected time points and conducts first-order computations at other time points. Specifically, for the case where the inputs are drawn from an unknown finite-support distribution, the proposed algorithm achieves a constant regret (even for the hard 'degenerate' case) while solving LPs only O(log log T) times over the time horizon T. Moreover, when we are allowed to solve LPs only M times, we design the corresponding schedule such that the proposed algorithm can guarantee a nearly O(T^{(1/2)^{M-1}}) regret. Our work highlights the value of resolving both at the beginning and the end of the selling horizon, and provides a novel framework to prove the performance guarantee of the proposed policy under different infrequent resolving schedules. Furthermore, when the arrival probabilities are known at the beginning, our algorithm can guarantee a constant regret by solving LPs O(log log T) times, and a nearly O(T^{(1/2)^{M}}) regret by solving LPs only M times.  Numerical experiments are conducted to demonstrate the efficiency of the proposed algorithms. 

TL;DR: Use mobile ads to impact customers' engagement, which is a partially observed Markovian state, to boost revenue. 

We investigate a seller's optimal advertising campaign strategy targeting customers who interact with the seller over time. We model customers' engagement by a continuous-time Markov chain with two states, active and inactive. While in the active state, customers make purchases according to a Poisson process, with each purchase yielding a certain reward; in contrast, customers in the inactive state make no purchases. The seller can use advertisements to activate customers and the activation probability may be affected by customers' fatigue to promotion. The objective of the seller is to maximize the long-term average expected profit by designing an optimal ad campaign strategy based on customers' purchase histories. For a single customer without budget constraints, we demonstrate the optimality of a triple-threshold policy based on the elapsed time since the last purchase or ad campaign. Moreover, we find that the seller tends to push ads earlier to customers with high purchase rates and low recapture rates (i.e., low transition rates from an inactive state to an active state). Surprisingly, we also find that the seller should push ads earlier to customers with intermediate churn rates (i.e., intermediate transition rates from an active state to an inactive state) compared to those with small or large churn rates. When confronted with a budget constraint on the overall ad cost, we suggest first solving a relaxed problem and then implementing a separate triple-threshold policy for each customer with a specified budget. We establish the asymptotic optimality of this policy and show that the asymptotic loss order is O(\sqrt{\log T /T}) for the general problem and O(1/\sqrt{T}) for a special case. In addition, we explore the case with strategic customer reactions. Overall, our work reveals important insights of the optimal ad campaign problem and provides a useful strategy in practice.

TL;DR: Compare two widely adopted two-sided market business models, dealership and marketplace, by multi-period dynamic models. 

Problem Definition: We consider two business models for a two-sided economy under uncertainty: dealership and marketplace with fulfillment services. Although both business models can bridge the gap between demand and supply, it is not clear which model is better for the firm or for the consumers. Methodology/Results: We show that while the two models differ substantially in pricing power, inventory risk, fee structure, and fulfillment time, both models share several important features, with the revenues earned by the firm from the two models converging when the markets are thick. We also show that for thick markets there is a one-to-one mapping between their corresponding optimal policies. Managerial implications: Our results provide guidelines for firms entering two-sided markets: when the market is thick, the two business models are similar; when the market is thin, they should carefully inspect a number of market conditions before making the choice.

TL;DR: Compare the emission tax regulation and the emission permit regulation when the market demand is uncertain. 

Government regulations on emission control can be broadly divided into two categories: price instruments and quantity instruments. In this paper, we develop a stylized model to compare the two instruments in the presence of market uncertainty. We find that when the emission intensity (i.e., emissions per unit of production) and the market uncertainty are both high or low, the expected social welfare under the price instruments will be higher; otherwise, the performance of the quantity instruments is comparatively better. The results are robust when incorporating firm competition and national/regional pollution damage.  Afterward, we demonstrate that the government's quick-response capability or a hybrid of the price and quantity instruments can improve the expected social welfare, especially for high-emitting industries when the market uncertainty is intermediate. Lastly, for heterogeneous firms, we find that allowing permit trading in the quantity instrument may not be beneficial when pollution from each firm is more likely to have regional effects.

TL;DR: To minimize total query cost plus latency cost in a multi-LLM setting, two LLMs are sufficient to achieve asymptotic optimality. 

We study a Bayesian binary sequential hypothesis testing problem with multiple large language models (LLMs). Each LLM j has per-query cost cj>0, random waiting time with mean μj>0 and sub-Gaussian tails, and \emph{asymmetric} accuracies: the probability of returning the correct label depends on the true hypothesis θ∈{A,B} and needs not be the same under A and B. This asymmetry induces two distinct information rates (Ij,A,Ij,B) per LLM, one under each hypothesis. The decision-maker chooses LLMs sequentially, observes their noisy binary answers, and stops when the posterior probability of one hypothesis exceeds 1−α. The objective is to minimize the sum of expected query cost and expected waiting cost, 𝔼[Cπ]+𝔼[g(Wπ)], where Cπ is the total query cost, Wπ is the total waiting time and g is a polynomial function (e.g., g(x)=xρ with ρ≥1). We prove that as the error tolerance α→0, the optimal policy is asymptotically equivalent to one that uses at most two LLMs. In this case, a single-LLM policy is \emph{not} generically optimal: optimality now requires exploiting a two-dimensional tradeoff between information under A and information under B. Any admissible policy induces an expected information-allocation vector in ℝ2+, and we show that the optimal allocation lies at an extreme point of the associated convex set when α is relatively small, and hence uses at most two LLMs. We construct belief-dependent policies that first mix between two LLMs when the posterior is ambiguous, and then switch to a single ``specialist'' LLM when the posterior is sufficiently close to one of the hypotheses. These policies match the universal lower bound up to a (1+o(1)) factor as α→0.