Display Optimization for Vertically Differentiated Locations Under Multinomial Logit Preferences
研究如何优化产品、网页链接等物品在垂直差异化位置上的展示顺序，以影响顾客选择行为，并提出了一个多项式时间近似方案，在酒店预订数据上验证了模型预测精度优于传统方法。
We introduce a new optimization model, dubbed the display optimization problem, that captures a common aspect of choice behavior, known as the framing bias. In this setting, the objective is to optimize how distinct items (corresponding to products, web links, ads, etc.) are being displayed to a heterogeneous audience, whose choice preferences are influenced by the relative locations of items. Once items are assigned to vertically differentiated locations, customers consider a subset of the items displayed in the most favorable locations before picking an alternative through multinomial logit choice probabilities. The main contribution of this paper is to derive a polynomial-time approximation scheme for the display optimization problem. Our algorithm is based on an approximate dynamic programming formulation that exploits various structural properties to derive a compact state space representation of provably near-optimal item-to-position assignment decisions. As a byproduct, our results improve on existing constant-factor approximations for closely related models and apply to general distributions over consideration sets. We develop the notion of approximate assortments that may be of independent interest and applicable in additional revenue management settings. Lastly, we conduct extensive numerical studies to validate the proposed modeling approach and algorithm. Experiments on a public hotel booking data set demonstrate the superior predictive accuracy of our choice model vis-à-vis the multinomial logit choice model with location bias, proposed in earlier literature. In synthetic computational experiments, our approximation scheme dominates various benchmarks, including natural heuristics—greedy methods, local search, priority rules—and state-of-the-art algorithms developed for closely related models. This paper was accepted by Yinyu Ye, optimization.