Improved Approximation Guarantees and Hardness Results for MNL-Driven Product Ranking

In this paper, we address open computational questions regarding the market share ranking problem, recently introduced by Derakhshan et al. (2022). Their modelling framework incorporates the extremely popular Multinomial Logit (MNL) choice model, along with a novel search-based consider-then-choose paradigm. In a nutshell, the authors devised a Pandora's-Box-type search model, where different customer segments sequentially screen through a ranked list of products, one position after the other, forming their consideration set by including all products viewed up until terminating their inspection procedure. Subsequently, a purchasing decision out of this set is made based on a joint MNL choice model. Our main contribution consists in devising a polynomial-time approximation scheme for the market share ranking problem, utilizing fresh technical developments and analytical ideas, in conjunction with revising the original insights of Derakhshan et al. (2022). Along the way, we introduce a black-box reduction, mapping general instances of the market share ranking problem into ``bounded ratio'' instances, showing that this result directly leads to an elegant and easily-implementable quasi-PTAS. Finally, to provide a complete computational characterization, we prove that the market share ranking problem is strongly $\mathrm{NP}$-hard.