Combinatorial assortment optimization

DOI10.1007/978-3-030-04612-5_15zbMATH Open1443.91196arXiv1711.02601OpenAlexW3162861602MaRDI QIDQ2190396FDOQ2190396

Authors: Nicole Immorlica, Brendan Lucier, Jieming Mao, Vasilis Syrgkanis, Christos Tzamos 

Publication date: 18 June 2020

Abstract: Assortment optimization refers to the problem of designing a slate of products to offer potential customers, such as stocking the shelves in a convenience store. The price of each product is fixed in advance, and a probabilistic choice function describes which product a customer will choose from any given subset. We introduce the combinatorial assortment problem, where each customer may select a bundle of products. We consider a model of consumer choice where the relative value of different bundles is described by a valuation function, while individual customers may differ in their absolute willingness to pay, and study the complexity of the resulting optimization problem. We show that any sub-polynomial approximation to the problem requires exponentially many demand queries when the valuation function is XOS, and that no FPTAS exists even for succinctly-representable submodular valuations. On the positive side, we show how to obtain constant approximations under a "well-priced" condition, where each product's price is sufficiently high. We also provide an exact algorithm for $k$-additive valuations, and show how to extend our results to a learning setting where the seller must infer the customers' preferences from their purchasing behavior.

Full work available at URL: https://arxiv.org/abs/1711.02601

Recommendations

• Constrained assortment optimization under the paired combinatorial logit model
• Assortment optimization under the paired combinatorial logit model
• Technical note: Assortment optimization with small consideration sets
• Technical note -- Capacitated assortment optimization: hardness and approximation
• Assortment optimization under variants of the nested logit model

zbMATH Keywords

assortment optimizationchoice modelcomplexity of optimization problemhardness of combinatorial assortment

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Consumer behavior, demand theory (91B42)

Cites Work

• Assortment optimization under variants of the nested logit model
• Dynamic assortment optimization with a multinomial logit choice model and capacity constraint
• A column generation algorithm for choice-based network revenue management
• Revenue Management Under a General Discrete Choice Model of Consumer Behavior
• Combinatorial auctions with decreasing marginal utilities
• Multi-parameter mechanism design and sequential posted pricing
• Dynamic assortment with demand learning for seasonal consumer goods
• A branch-and-cut algorithm for the latent-class logit assortment problem
• On maximizing welfare when utility functions are subadditive
• The exponomial choice model: a new alternative for assortment and price optimization
• Gross substitutability: an algorithmic survey
• Learning consumer tastes through dynamic assortments

Cited In (12)

• Technical note -- Assortment planning for two-sided sequential matching markets
• Technical note: Assortment optimization with small consideration sets
• A characterization of the existence of succinct linear representation of subset-valuations
• The approximability of assortment optimization under ranking preferences
• Optimal assortment with concave cost functions
• Assortment optimization under the multinomial logit model with product synergies
• Sequential Submodular Maximization and Applications to Ranking an Assortment of Products
• Assortment optimisation under a general discrete choice model: a tight analysis of revenue-ordered assortments
• On the sum-product ratio problem and its applications
• Constrained assortment optimization under the paired combinatorial logit model
• Approximation algorithms for dynamic assortment optimization models
• Assortment optimization over time

This page was built for publication: Combinatorial assortment optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2190396)