Source-linked AI summary
Cardinality-Constrained Randomized Assortments with Balanced Market Share
Xiaotie Deng, Hanyu Li, Chenghua Liu
TL;DR
Randomized BMS assortment optimization must balance aggregate sales while limiting every displayed assortment to K products, a constraint over an exponential policy space. The paper gives an exact compact sales formulation and an FPTAS, while showing that endogenous support selection makes the revenue-threshold decision problem NP-complete even for α = 1 and K = 2.
Problem
Randomized BMS with a per-assortment cardinality limit couples display feasibility with aggregate balance across an exponential policy space.
Source: §1 · pp. 1–2Method
The paper reweights assortments by their MNL denominators to obtain a uniform-matroid sales formulation, then uses a geometric scale search and multiple-choice-knapsack dynamic programming for approximation.
Source: §1 · p. 3, §7 · p. 12Results
The revenue-threshold decision problem is NP-complete even for α = 1 and K = 2, while the FPTAS achieves at least a (1 − ε) fraction of optimal revenue with BMS and cardinality satisfied exactly.
Source: §1 · p. 3Takeaways & Limitations
Every feasible rational sales point has an O(n)-assortment implementation, and approximation can preserve both feasibility requirements exactly.
Source: §7 · p. 12Compact representability does not eliminate the NP-complete revenue-threshold decision problem when the active set is endogenous.
Source: §1 · p. 3
Abstract
from arXiv · showhide
Assortment optimization asks a seller which of $n$ products to display to each customer. Under the multinomial-logit (MNL) model, a revenue-maximizing policy may concentrate most purchases on only a few products. Balanced market share (BMS) limits this disparity by requiring every product to receive either zero aggregate sales or at least an $\alpha$-fraction of the largest product's sales. We study randomized BMS under a per-assortment cardinality constraint: every displayed assortment contains at most $K$ products, although the seller may rotate a larger catalog across customers. This couples per-realization feasibility with aggregate balance over an exponential policy space. We resolve the model on all three algorithmic fronts. First, reweighting assortments by their MNL denominators turns the cardinality restriction into a single uniform-matroid rank inequality, yielding an exact compact sales-space formulation in which every feasible sales vector can be implemented by a policy supported on $O(n)$ assortments. Second, deciding whether there exists a feasible policy attaining a given revenue target is NP-complete even for $\alpha=1$ and $K=2$, whereas optimization is polynomial-time solvable once the set of products with positive sales is prescribed. Third, despite this hardness, BMS confines all positive sales to one multiplicative band, and a geometric scale search combined with a standard multiple-choice-knapsack dynamic program yields an FPTAS. For every $\varepsilon\in(0,1)$, it achieves at least a $(1-\varepsilon)$ fraction of the optimal expected revenue, preserves BMS and per-assortment cardinality exactly, and outputs a rational policy supported on $O(n)$ assortments.
1 Introduction
The paper studies randomized MNL assortments that balance aggregate sales while limiting every displayed assortment to K products. It gives an exact sales-space formulation, establishes the complexity boundary, and develops an FPTAS that preserves both constraints.
1 Introduction
- BMS requires each product with positive aggregate sales to receive at least an α-fraction of the largest product’s sales; α = 1 requires equal sales among active products.The seller may choose which products are active, and the balance condition applies to aggregate purchases rather than display frequencies.Source: §1 · p. 2
- The per-assortment limit is weaker than limiting the total active catalog to K products, since a policy can rotate among small assortments.For K = 2, the paper’s example uses {1, 2}, {2, 3}, and {3, 4}, so four products participate while each display contains at most two.Source: §1 · p. 2
- The paper identifies this cardinality-constrained randomized BMS problem as an open direction and resolves its representability, complexity, and approximation questions.The unrestricted model was polynomial-time solvable, with an optimal active set characterized by revenue and attractiveness thresholds.Source: §1 · p. 2
- The exact sales-space formulation preserves feasibility and objective value, and every feasible rational point has a rational implementation supported on O(n) assortments.The formulation follows from reweighting assortments by inverse MNL denominators, which turns rescaled sales into inclusion marginals under a rank-K uniform matroid.Source: §1 · pp. 2–3
- The revenue-threshold decision problem is NP-complete even when α = 1 and K = 2.The paper also shows that optimization is polynomial-time once the positive-sales product set is prescribed.Source: §1 · p. 3
- The FPTAS returns at least a (1 − ε) fraction of optimal expected revenue while satisfying BMS and per-assortment cardinality exactly.Its output is a rational policy supported on O(n) assortments.Source: §1 · p. 3
2 Related work
The paper situates cardinality-constrained randomized BMS among work on fair and randomized assortment models. Its contribution is an exact synthesis of sales-space, matroid, linear-fractional, and knapsack techniques for this setting.
2 Related work
- Prior BMS work [5] solved the unrestricted static model and distinguished restrictions on the active catalog from limits on every randomized assortment.Related work also studies randomized MNL with pairwise-difference constraints [4], minimum-exposure fairness, and class-level market-share constraints.Source: §2 · p. 4
- Ordinary cardinality-constrained MNL assortment optimization is polynomial-time solvable, while cardinality plus visibility requirements can make a related model strongly NP-hard.Those visibility constraints differ from aggregate relative balance; other cited work considers general discrete-choice models and combinatorial bundle-choice valuations.Source: §2 · p. 4
- The paper’s contribution combines a uniform-matroid rank constraint, NP-complete endogenous support selection, and an exact-feasibility FPTAS with O(n)-support implementation.The cited ingredients include sales-space modeling [5], uniform-matroid polytopes, linear-fractional programming, and profit scaling for multiple-choice knapsack.Source: §2 · p. 4
3 Model and optimization problem
The model assigns each product a revenue and attractiveness under MNL choice, then allows the seller to randomize over assortments of at most K products. It maximizes expected revenue subject to aggregate BMS.
3 Model and optimization problem
- Under MNL, product i has revenue r_i and attractiveness v_i, while the no-purchase option has revenue zero and weight v_0 = 1.The no-purchase option’s choice probability has denominator d(S) and numerator 1.Source: §3 · p. 5
- A randomized policy draws an assortment from those of size at most K, so the limit applies to each display while the union across displays can exceed K.The model uses rational binary-encoded revenues, attractiveness values, and α, with integer K; an output policy lists rational probabilities for its supported assortments.Source: §3 · p. 5
- BMS requires every active product’s aggregate purchase probability to be at least an α-fraction of the largest aggregate purchase probability.The active set consists of products with positive aggregate sales; the objective is to maximize expected revenue over BMS-feasible policies.Source: §3 · p. 5
4 An exact attainable-sales polytope
The section characterizes attainable aggregate sales through a compact rescaled-sales formulation. Its key step maps policies to uniform-matroid marginals and constructs a small-support policy for every feasible point.
4 An exact attainable-sales polytope
- The compact sales variables map a feasible policy into rescaled marginals that lie in the rank-K uniform-matroid independence polytope.The formulation preserves the objective and translates BMS into constraints on those variables.Source: §4 · p. 6
- Conversely, any feasible rescaled-sales point yields marginals that can be expressed as a convex combination of assortments of size at most K.The construction adds dummy coordinates, arranges intervals, and samples labels using a uniform shift; the set changes at only O(n) rational support points.Source: §4 · p. 6
5 Exact optimization reduces to support selection
Fixing the active set makes optimization polynomial, but choosing that set remains hard: revenue-threshold feasibility is NP-complete even for α=1 and K=2. The rank budget also invalidates the unrestricted model’s threshold-shaped supports.
5 Exact optimization reduces to support selection
- The compact formulation removes the exponential policy space but leaves the endogenous choice of which products receive positive sales.Thus, even though each prescribed support is tractable, maximizing over supports remains the combinatorial barrier.Source: §5 · p. 6, §5.2 · p. 9
5.1 A prescribed support is tractable
- For any prescribed nonempty active set, the exact maximum feasible revenue is computable in polynomial time.The BMS constraints become linear on the prescribed support, and a Charnes–Cooper transformation yields a polynomial-size rational linear program.Source: §5.1 · p. 7
5.2 Threshold failure and NP-completeness
- The rank budget destroys the unrestricted model’s revenue-and-attractiveness threshold geometry; a three-product instance has a unique optimal support that is not a northeast rectangle.Its unique optimal active set is {2, 3}; any northeast rectangle containing both products must also contain product 1.Source: §5.2 · p. 8
- Revenue-threshold feasibility is NP-complete even when α=1 and K=2; the reduction makes the constructed instance a yes-instance exactly when a subset sums to B.Membership in NP follows from a polynomial-bit vertex certificate for the bounded rational system.Source: §5.2 · pp. 8–9
6 An exact-feasibility FPTAS
Despite NP-hardness, BMS confines positive sales to a common multiplicative band, which the paper uses to construct a scale search and knapsack-based FPTAS. The algorithm approximates revenue while preserving BMS and assortment cardinality exactly, with a rational policy supported on O(n) assortments.
6.1 Locating and discretizing the balance scale
- Every nonzero discrete coordinate lies in the exact common BMS band [τ, τ/α], and some geometric-grid scale yields a discrete optimum at least OPT/(1 + δ)^2.The scale grid and downward coordinate rounding each incur at most a factor of 1 + δ.Source: §6.1 · p. 10
6.2 Revenue testing and the FPTAS
- For a fixed scale and revenue target, selecting product options reduces to multiple-choice knapsack; profit scaling gives a polynomial dynamic program with an at-least-(1 − δ) approximation.The dynamic program uses O(n^2/δ) profit states, and the complete algorithm tests candidates using unrounded transformed profit.Source: §6.2 · pp. 10–11
6 An exact-feasibility FPTAS
- The FPTAS achieves at least a (1 − ε) fraction of optimal expected revenue while preserving BMS and per-assortment cardinality exactly, and returns a rational policy supported on O(n) assortments.Approximation affects revenue only; both feasibility requirements remain exact.Source: §6.2 · pp. 11–12
7 Conclusion
The paper characterizes attainable sales and separates the complexity of optimizing with a prescribed active set from deciding the revenue threshold when that set is endogenous. It also gives an FPTAS that preserves both BMS and per-assortment cardinality exactly.
7 Conclusion
- A denominator tilt yields an exact compact sales-space formulation, and every feasible rational point has a rational implementation supported on O(n) assortments.The threshold decision problem is NP-complete even for α = 1 and K = 2, while optimization is polynomial-time for a prescribed active set.Source: §7 · p. 12
- A geometric search and profit-scaled dynamic program yield an FPTAS without relaxing BMS or per-realization cardinality.The approach uses the fact that all positive coordinates lie in one balance band.Source: §7 · p. 12
A Certificate for the nonrectangular optimum
For the Proposition 6 instance, support {2, 3} is globally optimal, while the full-support optimum is strictly lower. The certificate compares the best values across singleton, two-product, and full supports.
A Certificate for the nonrectangular optimum
- The best values on singleton and two-product supports are enumerated to certify global optimality and uniqueness.The support values are reported for {1}, {2}, {3}, {1, 2}, {1, 3}, and {2, 3}.Source: A Certificate for the nonrectangular… · p. 14
- For full support, the certificate bounds F(w) by ρ = 11989/195 using an inequality obtained by adding valid inequalities.This gives a full-support optimum below 928/15.Source: A Certificate for the nonrectangular… · p. 14
- 928/15 on support {2, 3} exceeds the full-support optimum 11989/195, certifying the claimed global optimum and failure of rectangular support structure.The listed singleton and two-product support values include 928/15 as the largest.Source: A Certificate for the nonrectangular… · p. 14