Source-linked AI summary
Assortment optimization under the perception-adjusted Luce model
Gerardo Berbeglia, Mashbat Suzuki, Matthew Tam
TL;DR
Whether revenue-ordering remains optimal for PALM with any finite number of perception levels is resolved by analyzing a continuous refinement of the assortment problem. The refined problem has a utility-integral optimum, yielding an optimal revenue-ordered-by-level assortment and a polynomial-time algorithm when the number of levels is fixed.
Problem
Whether PALM has an optimal revenue-ordered-by-level assortment for arbitrary numbers of perception levels remained an open conjecture.
Source: §1 · p. 2Method
The paper studies a continuous refinement of PALM assortment optimization and uses utility-preserving exchanges and first- and second-order optimality conditions.
Source: §4 · p. 14Results
Takeaways & Limitations
The level-specific threshold structure gives a polynomial-time algorithm when the number of perception levels is fixed.
Source: §4 · p. 14Cardinality and shelf-space constraints may prevent including all products above a revenue threshold and may invalidate the proof’s optimality conditions.
Source: §4 · pp. 14–15
Abstract
from arXiv · showhide
The Perception-Adjusted Luce Model (PALM) introduced by by Echenique et al. (2018) is a sequential choice model that can accommodate violations of regularity and choice overload, behaviors not captured by the utility-maximization framework. Flores et al. (2019) studied the assortment problem under the PALM and proved that, for the case of two levels, there is always an optimal solution that is revenue-ordered by level. They also conjectured that revenue-ordered by levels remain optimal for the general PALM with any number of levels. We resolve this question in the affirmative by showing that every PALM instance admits an optimal assortment that includes, within each level, all products at or above a level-specific revenue threshold. The proof involves first showing how the conjecture which deals with a discrete optimization problem, can be reduced to proving certain property of a related continuous optimization problem. Specifically, we study a continuous refinement of the assortment decision under the same PALM choice rule. Although the refinement permits partial utility selections, we prove it always has an optimum that selects complete revenue tiers. This allows us to show that the assortment problem is polynomial-time solvable when the number of levels is fixed.
1 Introduction
The paper resolves whether revenue-ordered assortments remain optimal under PALM with any finite number of perception levels. It uses a continuous refinement to establish the structure needed for a polynomial-time algorithm when the number of levels is fixed.
1 Introduction
- PALM models sequential choices by perception priority and can accommodate violations of regularity and choice overload.These behaviors are not captured by the random-utility framework described in the paper.Source: §1 · p. 2
1.1 Related literature
- Flores et al. (2019) proved revenue-ordering optimal for two PALM levels and conjectured the result for any number of levels.The paper addresses that open general-level conjecture.Source: §1 · p. 2
1 Introduction
- For every finite number of perception levels, PALM admits an optimal assortment that is revenue-ordered within each level.This resolves the conjecture that the two-level result extends to the general PALM.Source: §1 · p. 2
1.2 Paper outline and proof strategy
- Enumerating the resulting level-specific revenue thresholds gives a polynomial-time algorithm when the number of perception levels is fixed.The optimal structure reduces the assortment decision to choosing one threshold per level.Source: §1 · p. 2
- The proof refines assortment choices to continuous utility allocations, orders allocations by revenue within each level, and reduces the problem to jointly optimizing level totals.It then establishes an optimum at revenue-tier boundaries, which corresponds to complete tiers and an ordinary assortment.Source: §1.2 · pp. 4–5
2 Assortment Optimization under the Perception-Adjusted Luce Model
This section formulates traditional and refined assortment optimization under PALM. It shows how a utility-integral optimum of the refined problem yields an optimal assortment ordered by revenue within each level.
2 Assortment Optimization under the Perception-Adjusted Luce Model
- The section formulates PALM and both traditional and refined assortment optimization problems.In the refined version, product utilities may be reduced while revenues, perception levels, and the PALM choice rule remain fixed.Source: §2 · p. 5, §2.2 · p. 6
2.1 Traditional assortment optimization under the PALM
- A product’s purchase probability depends on assortments at its own level and at all preceding and following levels, creating nonlinear interactions across levels.Flores et al. (2019) proved the revenue-ordering result for two levels and left the general PALM case as a conjecture.Source: §2.1 · p. 6
2.2 Refined assortment optimization under the PALM
- For fixed level utilities, the refined problem allocates utility to products in nonincreasing revenue order, making each level’s revenue a concave, piecewise-linear function of its utility total.Utility-integral choices occur at revenue-tier boundaries; Figure 1 illustrates a partial-tier allocation alongside complete-tier choices.Source: §2.2 · pp. 6–7, Figure 1 · p. 7
2.3 From refined integrality to revenue-ordered assortments
- If the refined problem has an optimum at utility-integral level totals, selecting complete tiers produces a revenue-ordered-by-level assortment with the same optimal revenue.The resulting assortment attains the refined upper bound on ordinary-assortment revenue.Source: §2.3 · p. 8
3 Utility-Integrality in the Refined Problem
The refined PALM assortment problem admits an optimal solution selecting complete revenue tiers, so its optimum matches the traditional assortment problem’s revenue. The proof establishes integrality first for local optima with multiple active levels, then handles the remaining cases.
3 Utility-Integrality in the Refined Problem
- The refined problem always has an optimal utility-integral solution, selecting complete revenue tiers at every level.Under PALM, this yields exactly the same revenue as traditional assortment optimization.Source: §3 · pp. 8–9
3.1 Utility-integrality of local optima
- With z > 0, every positive-valued local maximizer having at least two active levels is utility-integral.The proof combines first-order conditions with a curvature argument to rule out fractional coordinates.Source: §3 · p. 9, §3.1 · p. 13
3.2 Proof of Theorem 3.1
- The proof handles boundary cases separately, showing that an optimum can be chosen at revenue-tier boundaries even when only one level is active.On a constant-revenue tier, the objective is monotone or constant, so an optimal interior point has an optimal endpoint.Source: §3.2 · p. 14
4 Concluding remarks and future research
The paper proves that PALM has an optimal assortment with a level-specific revenue threshold at each level, resolving the general-level conjecture and yielding polynomial-time solvability when the number of levels is fixed. The proof uses a continuous refinement, while the authors identify operational constraints and extending the approach beyond PALM as open research directions.
4 Concluding remarks and future research
- Within each PALM level, an optimal assortment offers all products at or above a level-specific revenue threshold, resolving Flores et al. (2019)'s conjecture and yielding polynomial-time solvability for a fixed number of levels.The result extends their two-level result to the general PALM.Source: §4 · p. 14
- A continuous refinement allows partial product-utility selections; utility-preserving exchanges and first- and second-order optimality conditions establish an optimum corresponding to an ordinary assortment with the same optimal revenue.This continuous-optimization proof differs from Flores et al. (2019)'s algebraic proof for k = 2.Source: §4 · p. 14
- Cardinality and shelf-space constraints may prevent offering every product above a revenue threshold and may invalidate the proof's optimality conditions.Characterizing optimal constrained assortments and developing approximation algorithms are identified as future research directions.Source: §4 · pp. 14–15
- The proof relies on the common utility denominator and ordered perception levels, so conditions for extending the argument to other sequential choice models or restricted customer heterogeneity remain open.When a refinement is not exact, quantifying the revenue gap could help assess its use for bounds and approximation algorithms.Source: §4 · p. 15