Combinatorial assortment optimization

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

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

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 (3)

• A characterization of the existence of succinct linear representation of subset-valuations
• Optimal assortment with concave cost functions
• Technical Note—Assortment Planning for Two-Sided Sequential Matching Markets

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)