In This Issue
Preservation of Supermodularity in Parametric Optimization: Necessary and Sufficient Conditions on Constraint Structures
The concept of supermodularity has received considerable attention in economics and operations research. It is closely related to the concept of complementarity in economics and has also proved to be an important tool for deriving monotonic comparative statics in parametric optimization problems and game theory models. However, only certain sufficient conditions (e.g., lattice structure) are identified in the literature to preserve the supermodularity. In “Preservation of Supermodularity in Parametric Optimization: Necessary and Sufficient Conditions on Constraint Structures,” by Chen, Zhuoyu Long, and Qi new concepts of mostly sublattice and additive mostly sublattice are introduced. With these new concepts, necessary and sufficient conditions for the constraint structures are established so that supermodularity can be preserved under various assumptions about the objective functions. Furthermore, some classes of polyhedral sets that satisfy these concepts are identified, and the results are applied to assemble-to-order systems.
Strategic Behavior in Queues
Pooled queues are employed in many service settings (e.g., call centers, grocery stores) as a way to improve operational performance by reducing the variability in customer arrivals. However, in some settings, such as hospital emergency departments, empirical evidence suggests that pooled queues may not always lead to better operational performance. In “Pooling Queues with Strategic Servers,” Armony, Roels, and Song develop a game-theoretic model that compares the performance of pooled vs. dedicated queues when servers choose their capacities strategically and exhibit varying scopes of customer ownership. They find that dedicated queues can yield substantial benefits when servers’ degree of customer ownership is so low that they choose to operate at high utilization, and when they care much more about their customers’ processing times than about their waiting times; otherwise, the queue configuration makes little difference. These results have important implications for managers trying to determine which queue configuration to adopt.
Deliver Today or Deliver Tomorrow?
In “Robust Multiperiod Vehicle Routing Under Customer Order Uncertainty,” Subramanyam, Mufalli, Laínez-Aguirre, Pinto, and Gounaris study tactical vehicle routing operations where the distributor maintains some control over the time period in which customers are served. However, as customer service requests are received dynamically over the planning horizon, routing plans should maintain a satisfactory degree of flexibility to accommodate potential service requests that have not yet been placed. This setting constitutes a multistage optimization problem with binary recourse decisions and binary random variables, which is inherently intractable. To that end, the authors propose a tractable approximation in the form of a nonanticipative two-stage robust optimization model for which they develop a branch-and-cut solution approach. The practicality of the approach as well as the high quality of the routing plans it generates are demonstrated via a series of rolling-horizon simulations.
On the (Surprisingly) Good Performance of Capped Base-Stock Policies in Lost-Sales Inventory Models
Single-sourcing lost-sales inventory systems with lead times have a long and rich history in the inventory literature and the earliest study dates back to 1958. Due to the complex structure of the optimal policy and computational intractability, such inventory systems are notoriously difficult to optimize. In “Technical Note—Understanding the Performance of Capped Base-Stock Policies in Lost-Sales Inventory Models,” Xin proposes a new family of simple capped base-stock policies and provides a new perspective of constructing a practical hybrid policy combining two well-known heuristics: base-stock and constant-order policies. Each capped base-stock policy is associated with two parameters: a base-stock level and an order cap. Compared with the traditional base-stock policy, the additional order cap provides order-smoothing and constrains high future holding costs. The author numerically demonstrates its superior performance by comparing with other existing heuristics and explains why it performs so well and when it brings the most benefits. The author also builds a theoretic connection between the capped base-stock policy and the constant-order policy.
Incorporating Imperfect Targeting, Deployment Restrictions, and Morale into Combat Models
Military forces engaged in a battle of attrition have classically been described by Lanchester equations. Existing Lanchester combat models focus on two force parameters: numbers (force size) and per-capita effectiveness (attrition rate). Whereas these two parameters are central in projecting a battle’s outcome, there are other important factors that affect the battlefield: (1) targeting capability, that is, the capacity to identify live enemy units and not dissipate fire on nontargets; (2) tactical restrictions preventing full deployment of forces; and (3) morale and tolerance of losses, that is, the capacity to endure casualties. Atkinson, Kress, and MacKay incorporate these three factors into Lanchester models in “Targeting, Deployment, and Loss-Tolerance in Lanchester Engagements” and derive force-parity equations for various combinations of these factors and obtain general implications and trade-offs. The paper shows that more units and better weapons (higher attrition rate) are preferred over improved targeting capability and relaxed deployment restrictions, unless these are poor.
New Algorithms and Models Enable Randomized Network Interdiction Strategies
Traditional network interdiction problems limit the leader to use a deterministic interdiction strategy, but a stochastic interdiction strategy can present a greater dilemma to the follower who seeks a shortest path on the network. In “The Shortest Path Interdiction Problem with Randomized Interdiction Strategies: Complexity and Algorithms,” Holzmann and Smith examine a shortest-path interdiction problem in which the leader randomizes its attacks, and the follower only knows the probability of where attacks will occur. The cost of each arc increases as a function of the number of times the arc is interdicted, and the leader seeks to maximize the follower’s shortest expected path. When the arc cost function is linear in the number of attacks that occur on the arcs, this problem is solvable in polynomial time by linear programming. However, both the special cases in which the arcs are all convex or all concave turn out to be NP-hard. The authors give general-purpose algorithms for this interdiction problem, along with a polynomial-time approximation algorithm for the case of concave cost functions.
Active Option Combination Strategies for Risk-Averse Investors with Transaction Costs and Portfolio Restrictions
Research about equity index options has shown that option prices systematically violate rational pricing bounds for the risk-averse representative investor. These results raise the question of whether profitable trading possibilities exist in this market. Standard portfolio optimization does not apply because of the large bid-ask spreads and low quote sizes in this market. In “Risk Arbitrage Opportunities for Stock Index Options,” Post and Longarela are motivated by these complications, a system of linear inequalities is developed that completely characterizes all risk arbitrage opportunities in the presence of transaction costs and portfolio restrictions. The practical use of this system is illustrated with an application to front-month S&P500 stock index options. Small-scale portfolios seem to produce surprisingly large abnormal returns out of sample; outperformance, however, seems elusive for institutional investors because of the limited quote size, possibly reflecting data limitations.
Trading Networks Through the Lens of Convex Optimization.
This paper considers a network of agents who trade indivisible goods or services via bilateral contracts. Under a substitutability assumption on preferences, it is known that a competitive equilibrium exists. In “Competitive Equilibrium and Trading Networks: A Network Flow Approach,” Candogan, Epitropou, and Vohra show how to determine equilibrium outcomes as a generalized submodular flow problem. Existence of a competitive equilibrium and its equivalence to seemingly weaker notions of stability follow directly from the optimality conditions of the flow problem. The formulation enables the authors to perform comparative statics with respect to the number of buyers, sellers, and trades. In particular, they are able to shed light on the impact of new trading opportunities on the equilibrium trades, prices, and surpluses. In addition, they present algorithms for finding competitive equilibria in trading networks and testing stability.
The Value of Navigations Apps and How to Choose Them
Over the years, travelers are increasingly relying on navigation services to inform their route choices and save time. How much value—in terms of saved time—can these services indeed provide to their users? The answer is not as simple as one may think because the value of traffic information not only depends on its accuracy, but also on how widely it is shared among travelers. For instance, information on an incident has the highest value for a traveler when the traveler is the only person who knows about it and takes a detour. However, this information becomes less valuable when it is shared with more travelers, who may take the same detour and cause congestion. In “Value of Information in Bayesian Routing Games,” Wu, Amin, and Ozdaglar use a game-theoretic approach to analyze how the relative value of information provided by different navigation services changes with their market share and how travelers may choose from different available services.
Global Robust Stability in a General Price and Assortment Competition Model
In “Technical Note—Global Robust Stability in a General Price and Assortment Competition Model,” Federgruen and Hu analyze a general but parsimonious price competition model for an oligopoly in which each firm offers any number of products. The demand volumes are general piecewise affine functions of the full price vector, generated as the “regular” extension of a base set of affine functions. The model specifies a product assortment, along with their prices and demand volumes, in contrast to most commonly used demand models, such as the multinomial logit model or any of its variants. The authors show that a special equilibrium in this model has global robust stability. This means that, from any starting point, the market converges to this equilibrium when firms use a particular response mapping to dynamically adjust their own prices in response to their competitors’ prices. The mapping requires each firm to only know the demand function and cost structure for its own products (but not for other firms’ products).
How to Price When Customers are Fully Strategic and Choose Both When and What to Buy?
In practice, when thinking about their purchasing decisions, customers usually strategize along two dimensions: (1) when to buy and (2) what to buy. That is, they might delay a purchase in anticipation of future price reductions, and/or they might purchase cheaper substitutes. Despite this, the literature has thus far dealt exclusively with either one of the two extremes whereby one of the two strategic dimension is missing. For example, a large body of work has studied forward-looking customers strategizing on when to buy but has done so merely within models in which customers have no alternatives to choose from. Conversely, another large body of work on assortment optimization and choice modeling has studied customers who choose what to buy from multiple product offerings but acting myopically. In “Technical Note—On Revenue Management with Strategic Customers Choosing When and What to Buy,” Chen and Trichakis take a first step toward analyzing dynamic pricing when customers are fully strategic and choose both when and what to buy. Using a novel decomposition approach for the underlying multidimensional mechanism design problem, the paper presents theoretical and numerical performance analyses of static pricing policies.
Complementing the Literature on Simple vs. Optimal Mechanisms: Considering Complements
Recent literature on approximately optimal revenue maximization has shown that in settings where agent valuations for items are complement free, the better of selling the items separately and bundling them together guarantees a constant fraction of the optimal revenue. However, most real-world settings involve some degree of complementarity among items. The role that complementarity plays in the trade-off of simplicity versus optimality has been an obvious missing piece of the puzzle. In “A Simple and Approximately Optimal Mechanism for a Buyer with Complements,” Eden, Feldman, Friedler, Talgam-Cohen, and Weinberg show that the same simple selling mechanism—the better of selling separately and as a grand bundle—guarantees a $\Theta(d)$ fraction of the optimal revenue, where $d$ is a measure of the degree of complementarity. One key modeling contribution is a tractable notion of “degree of complementarity” that admits meaningful results and insights—they demonstrate that previous definitions fall short in this regard.
Dynamic Pricing with Limited Demand Information
In “On Policies for Single-Leg Revenue Management with Limited Demand Information,” Ma, Simchi-Levi, and Teo revisit the foundational revenue management problem of dynamically pricing the limited seats on a single flight leg. The authors propose a new “Valuation Tracking” policy, which dynamically raises the price within a feasible range as seats get sold but, importantly, does not rely on any information about the remaining demand expected to occur before the flight takes off. This new policy can be seen as an adaptation of historically used “booking limits” policies, designed for flight fare classes that captured independent segments of demand, to modern times, where airlines are frequently adding sophisticated fare classes that capture overlapping demand segments. The new policy achieves the best-possible theoretical competitive ratio and also performs robustly in a comprehensive numerical comparison with all the different policies that have been proposed for single-leg revenue management under limited demand information.
Strategically Set Advertising Budgets: Simple Equilibria and Greedy Allocation Policies
Given the scale of the sponsored search market, it is practically important yet technically difficult to understand the interplay between bidders and the ad network and its effect on the long-run state of the market. Although typical equilibrium models account for bidders strategizing over the individual bids they submit to the auctions, they ignore that bidders also strategically set their campaign budgets. In “Tractable Equilibria in Sponsored Search with Endogenous Budgets,” Ciocan and Iyer ask how this additional strategic layer affects market operation and prove that endogenizing budgets surprisingly yields simple and interpretable equilibria. Namely, these equilibria generate quasi-truthful bidding strategies guaranteeing bidders an ROI exceeding their cost per dollar of committed budget. Additionally, the ad network’s optimal allocation policy becomes greedy with high probability. Thus, in this equilibrium, the ad network need not solve computationally challenging, large-scale linear optimization problems typically required under exogenous budgets.
Pricing Under Time-Varying Valuations
Typically, customers’ valuations, throughout their purchasing journey of a durable good, are assumed constant. In reality, these valuations can be changing through time due to new information gathered or a change in customers’ personal state. In “Intertemporal Price Discrimination with Time-Varying Valuations,” Araman and Fayad suggest a very general model for customers’ valuation process of a durable good. The authors analyze the optimal committed pricing policy the firm should set in this context. Interestingly, they show that cyclic policies, known to be optimal for constant valuations, remain optimal under this general setting, and suggest an algorithm to obtain them. However, the time-varying valuations feature presents a major complexity with respect to the structure and the tractability of the optimal policy. By forcing the firm to keep each price for a minimum amount of time, the authors obtain well-behaved and numerically tractable policies.
A Stochastic Assignment Problem
Consider initially empty boxes, numbered 1 through . Balls arrive sequentially. Each ball has a binary vector attached to it, with the interpretation that the ball is eligible to be put in box if . An arriving ball can be put in any empty box for which it is eligible. Assume that components of the vector are independent Bernoulli random variables with initially unknown probabilities . In “Technical Note—A Stochastic Assignment Problem with Unknown Eligible Probabilities,” Ross, Weiss, and Zhang discuss policies that aim at minimizing the number of balls needed until all boxes are filled. When full memory is allowed, the optimal policy is identified in the sense that it stochastically minimizes the number of balls taken. Two random policies are considered and compared when no memory is allowed. A reordering rule is proposed when one can only keep partial memory.
A Note on the Equivalence of Upper Confidence Bounds and Gittins Indices for Patient Agents
In “Technical Note—A Note on the Equivalence of Upper Confidence Bounds and Gittins Indices for Patient Agents,” Russo gives a short, self-contained proof of a sharp connection between Gittins indices and Bayesian upper confidence bound algorithms. The author considers a Gaussian multiarmed bandit problem with discount factor . The Gittins index of an arm is shown to equal the -quantile of the posterior distribution of the arm's mean plus an error term that vanishes as . In this sense, for sufficiently patient agents, a Gittins index measures the highest plausible mean-reward of an arm in a manner equivalent to an upper confidence bound.
The Discrete Moment Problem with Nonconvex Shape Constraints
The discrete moment problem aims to find a worst-case discrete distribution that satisfies a given set of moments. In “The Discrete Moment Problem with Nonconvex Shape Constraints,” Chen, He, Jiang, Ryan, and Zhang study the discrete moment problems with additional shape constraints that guarantee the worst-case distribution is either log-concave (LC) or has an increasing failure rate (IFR) or increasing generalized failure rate (IGFR). These classes are useful in practice, with applications in revenue management, reliability, and inventory control. The authors characterize the structure of optimal extreme point distributions and show, for example, that an optimal extreme point solution to a moment problem with m moments and LC shape constraints is piecewise geometric with at most m pieces. Using this optimality structure, they design an exact algorithm for computing optimal solutions in a low-dimensional space of parameters. The authors leverage this structure to study a robust newsvendor problem with shape constraints and compute optimal solutions.
How to Learn When the Data Cannot be Trusted?
In many practical settings, the decision makers have to learn their best actions by experimenting with possible options and collecting feedback (data) over time. It is often assumed that the collected data can be trusted as they reflect the ground truth. But this assumption is violated when the data are generated by strategic players. Consider online advertising market in which the ad exchange (decision maker) aims at learning the best reserve prices in the repeated auctions. In this setting, the data are advertisers’ submitted bids. Such data can be strategically corrupted by advertisers to trick the learning algorithm of the ad exchange to offer them lower reserve prices in the future auctions. In “Dynamic Incentive-Aware Learning: Robust Pricing in Contextual Auctions,” Golrezaei, Javanmard, and Mirrokni design effective learning algorithms with sublinear regret in such environments that are robust to the strategic behavior of the players.
Understanding the Regret of Bandit Algorithms in Queueing Systems
Traditional scheduling problems in stochastic queueing systems assume that the statistical parameters are known a priori. In ''Learning Unknown Service Rates in Queues: A Multiarmed Bandit Approach'', Krishnasamy, Sen, Johari, and Shakkottai consider the problem of online scheduling in a parallel-server system when the statistical parameters are unknown. The authors study this question in the stochastic multiarmed bandits framework with the queue length as the performance objective. In contrast to the classic stochastic multiarmed bandits problem, where the regret scales logarithmically with time, they show that the queue regret (difference in expected queue length between a bandit algorithm and a genie policy) exhibits a more complex behavior. It grows logarithmically in the initial stage and eventually decays almost inversely with time. This remarkable behavior is explained through the analysis of regenerative cycle lengths, which shorten with time as the bandit algorithm learns to stabilize the queues.
Descending to Stability: Robust Power Control for Stochastic Wireless Networks
The explosive growth of smart devices together with their dense connections via wireless networks have become a ubiquitous feature of smart cities. These devices, typically light-weight and battery-driven, burn power when they communicate with one another to form a functional ecosystem. As such, it is both theoretically interesting and practically impactful to design robust power control algorithms that operate smoothly under the challenges brought forth by dense networks in our current Internet-of-Things era. In “Robust Power Management via Learning and Game Design,” Zhou, Mertikopoulos, Moustakas, Bambos, and Glynn take a novel hybrid approach that combines learning with game design to build a novel and efficient power control algorithm that is provably stable and optimal, thereby not only contributing deployable algorithms with strong performance but also opening up new avenues for distributed algorithm design at large.
A New Nonsparse Learning Methodology for High-Dimensional Data Analysis Is Coming
As a popular tool for producing meaningful and interpretable models, large-scale sparse learning works efficiently in many optimization applications when the underlying structures are indeed or close to sparse. However, naively applying the existing regularization methods can result in misleading outcomes because of model misspecification. In “Nonsparse Learning with Latent Variables,” Zheng, Lv, and Lin consider nonsparse learning under the factors plus sparsity structure, which yields a joint modeling of sparse individual effects and common latent factors. A new methodology of nonsparse learning with latent variables (NSL) is proposed for joint estimation of the effects of two groups of features, one for individual effects and the other associated with the latent substructures, when the nonsparse effects are captured by the leading population principal component score vectors. The efficiency of NSL is evidenced by simulation studies and nutrient intake and human gut microbiome data analysis.
