Mallows assortment optimization leaves quasi-polynomial time: an independent-utility equivalence restores a polynomial-time scheme

Assortment optimization under the Mallows model now has a true polynomial-time approximation scheme rather than relying on quasi-polynomial time or extra structural simplifications. Earlier approximation schemes either required stylized structural simplifications or restrictive parametric assumptions, or, without those levers, used a highly involved quasi-polynomial-time scheme. The scheme gives an $O(n^{\tilde{O}(1/\epsilon^2)})$ running time while allowing arbitrary product prices, concentration parameters, and modal rankings.

The approach rewrites Mallows choice probabilities as one collection of mutually independent utilities that reproduces the same choice probabilities for every offered set. This exact choice equivalence connects pending Mallows-related challenges to the approximation framework of Bowers et al. (FOCS 2025) for assortment optimization under independent random utilities. To make the connection algorithmically feasible, a finite-support reduction produces distributions of polynomial size while controlling revenue loss uniformly over all assortments.

The result addresses assortment optimization under the Mallows model: it gives an $O(n^{\tilde{O}(1/\epsilon^2)})$-time approximation scheme while allowing arbitrary product prices, concentration parameters, and modal rankings. The intended readers are researchers and engineers working on discrete choice, revenue management, and approximation algorithms. The material proposes no next experiment or deployment step.

The material is a summary and provides no experiments or numerical validation, nor does it state constant factors or implementation details. The running-time bound is expressed in terms of $\epsilon$, and the material does not report behavior at specific accuracy values.