Knowledge that Transforms

Assortment optimization has received significant attention in recent revenue management and combinatorial optimization literature. In “The Approximability of Assortment Optimization Under Ranking Preferences,” A. Aouad, V. Farias, R. Levi, and D. Segev provide best-possible approximability bounds for this problem under an almost general model specification, where preferences are expressed as a distribution over rankings. This paper shows how this optimization problem relates to the computational task of detecting large independent sets in graphs, allowing the establishment of strong complexity lower bounds with respect to various problem parameters. These findings are complemented by a number of algorithms that attain essentially best-possible approximation factors, proving that the hardness results are tight up to lower-order terms. Surprisingly, their results imply that a simple and widely studied policy, known as revenue-ordered assortments, achieves the best possible performance guarantee with respect to prices.

We propose information-directed sampling—a new approach to online optimization problems in which a decision maker must balance between exploration and exploitation while learning from partial feedback. Each action is sampled in a manner that minimizes the ratio between squared expected single-period regret and a measure of information gain: the mutual information between the optimal action and the next observation. We establish an expected regret bound for information-directed sampling that applies across a very general class of models and scales with the entropy of the optimal action distribution. We illustrate through simple analytic examples how information-directed sampling accounts for kinds of information that alternative approaches do not adequately address and that this can lead to dramatic performance gains. For the widely studied Bernoulli, Gaussian, and linear bandit problems, we demonstrate state-of-the-art simulation performance. The electronic companion is available at https://doi.org/10.1287/opre.2017.1663 .

We develop the first nonparametric learning algorithm for periodic-review perishable inventory systems. In contrast to the classical perishable inventory literature, we assume that the firm does not know the demand distribution a priori and makes replenishment decisions in each period based only on the past sales (censored demand) data. It is well known that even with complete information about the demand distribution a priori, the optimal policy for this problem does not possess a simple structure. Motivated by the studies in the literature showing that base-stock policies perform near optimal in these systems, we focus on finding the best base-stock policy. We first establish a convexity result, showing that the total holding, lost sales and outdating cost is convex in the base-stock level. Then, we develop a nonparametric learning algorithm that generates a sequence of order-up-to levels whose running average cost converges to the cost of the optimal base-stock policy. We establish a square-root convergence rate of the proposed algorithm, which is the best possible. Our algorithm and analyses require a novel method for computing a valid cycle subgradient and the construction of a bridging problem, which significantly departs from previous studies. The e-companion is available at https://doi.org/10.1287/opre.2018.1724

Worst-case risk measures provide a means of calculating the largest value of risk when only partial information of the underlying distribution is available. For popular risk measures such as value-at-risk (VaR) and conditional value-at-risk (CVaR) it is now known that their worst-case counterparts can be evaluated in closed form when only the first two moments are known. We show in this paper that closed-form solutions exist for a general class of law invariant coherent risk measures, which consist of spectral risk measures (and thus CVaR also) as special cases. Moreover, we provide worst-case distributions characterized in terms of risk spectrums, which can take any form of distribution bounded from below. As applications of the closed-form results, new formulas are derived for calculating the worst-case values of higher order risk measures and higher order semideviation, and new robust portfolio optimization models are provided. The online appendix is available at https://doi.org/10.1287/opre.2018.1736 .

We address the problem of risk sharing among agents using a two-parameter class of quantile-based risk measures, the so-called range-value-at-risk (RVaR), as their preferences. The family of RVaR includes the value-at-risk (VaR) and the expected shortfall (ES), the two popular and competing regulatory risk measures, as special cases. We first establish an inequality for RVaR-based risk aggregation, showing that RVaR satisfies a special form of subadditivity. Then, the Pareto-optimal risk sharing problem is solved through explicit construction. To study risk sharing in a competitive market, an Arrow–Debreu equilibrium is established for some simple yet natural settings. Furthermore, we investigate the problem of model uncertainty in risk sharing and show that, in general, a robust optimal allocation exists if and only if none of the underlying risk measures is a VaR. Practical implications of our main results for risk management and policy makers are discussed, and several novel advantages of ES over VaR from the perspective of a regulator are thereby revealed.The e-companion is available at https://doi.org/10.1287/opre.2017.1716 .