Research

Assortment Optimization for Online Multiplayer Video Games

with Thomas W.M. Vossen and Rui Zhang, under review at Production and Operations Management
We consider an assortment optimization problem for a class of online multiplayer video games where the in-game virtual store has a unique structure with two sections: Featured and Just For You (JFY). All customers (players) are offered the same Featured section assortment, whereas the JFY section is used for personalized recommendations. Our paper is the first to study assortment optimization for the gaming industry under discrete choice models; it is also the first to devise solution approaches for the constrained mixture-of-nested-logit model with performance guarantees. We model customer choice under a constrained mixture-of-nested-logit model and propose a number of solution approaches for the resulting assortment optimization problems, including a fully polynomial time approximation scheme (FPTAS), a mixed-integer linear programming (MILP) formulation, and a fast heuristic algorithm. We also provide an upper-bounding approach that relies on certain key algorithmic enhancements. We provide theoretical performance guarantees for the FPTAS, MILP formulation, and heuristic algorithm. In addition, numerical experiments show that our approaches perform well across a variety of settings. These experiments demonstrate that the MIP formulation outperforms the FPTAS in terms of both efficiency and effectiveness, especially on larger instances. On average, the MIP formulation obtains solutions with a 0.47% optimality gap in a few seconds. In addition, our results show that the aforementioned algorithmic enhancements are critical to generating strong upper bounds. Our work provides guidance for how online video game stores can manage assortments for effective revenue maximization. We propose an ‘‘assortment’’ of solution approaches that allows practitioners to choose a method that best suits their environment.

An Approximate Dynamic Programming Approach to Dynamic Stochastic Matching

with Thomas W.M. Vossen, Accepted at INFORMS Journal on Computing
Dynamic stochastic matching problems arise in a variety of recent applications, ranging from ridesharing and online video games to kidney exchange. Such problems are naturally formulated as Markov decision processes (MDPs) that are, however, intractable in general. To improve tractability, we investigate the linear programming-based approach to approximate dynamic programming. This approach can provide both feasible control policies and bounds on the MDPs’ optimal policy value, which can be used to establish optimality gaps. Still, the approximate linear programs (ALPs) resulting from this approach can often be difficult to solve. To address this computational challenge, we derive novel ALP reformulations that can be used for a broad class of dynamic stochastic matching problems that incorporate, among others, possible match failures and certain restrictions on feasible matchings. We show that these ALP reformulations can be solved efficiently and applied to a broad class of dynamic matching problems. In addition, our numerical results indicate that our ALP reformulations can produce tight bounds that allow us to establish nearoptimal policy performance for a broad set of problem instances. Thus, ALP reformulations can present an attractive alternative for applications that involve dynamic stochastic matching.

Finite-Horizon Approximate Linear Programs for an Infinite-Horizon Resource Allocation Problem

with Thomas W.M. Vossen and Dan Zhang, Production and Operations Management (DOI),
Approximate linear programs have been used extensively to approximately solve stochastic dynamic programs that suffer from the well-known curse of dimensionality. Due to canonical results establishing the optimality of stationary value functions and policies for infinite-horizon dynamic programs, the literature has largely focused on approximation architectures that are stationary over time. In a departure from this literature, we apply a non-stationary approximation architecture to an infinite-dimensional linear programming formulation of the stochastic dynamic programs. We solve the resulting problems using a finite-horizon approximation. Such finite-horizon approximations are common in the theoretical analysis of infinite-horizon linear programs, but have not been considered in the approximate linear programming literature. We illustrate the approach on a rolling-horizon resource allocation problem using an affine approximation architecture. We obtain three main results. First, non-stationary approximations can substantially improve upper bounds on the optimal revenue. Second, the upper bounds from the finite-horizon approximation are monotonically decreasing as the horizon length increases, and converge to the upper bound from the infinite-horizon approximation. Finally, the improvement does not come at the expense of tractability, as the resulting approximate linear programs admit compact representations and can be solved efficiently. The resulting approximations also produce strong heuristic policies and significantly reduce optimality gaps in numerical experiments.