PaperlayerView exact revision on arXiv

Source-linked AI summary

A Unified Framework for Assortment Optimization and Matching under MNL Choice

Omar El Housni, Ulysse Hennebelle

arXiv:2610.35389v1math.OCcs.GT

TL;DR

Assortment and matching decisions under MNL involve uncertainty about which alternatives are available as well as how customers choose among them. The paper analyzes a threshold policy for committing before availability is known, and reports a tight 1/2 guarantee against a benchmark with post-availability customization and control over dependence.

  • Problem

    Assortment and matching models must account for uncertainty in both customer choices and which alternatives are available for a transaction.

    Source: §1 · pp. 1–2

  • Method

    The framework analyzes a threshold policy for committing to eligible products before independent availability is revealed, using a compact LP relaxation.

    Source: §1 · p. 2, §1.1 · p. 2, §8 · p. 28

  • Results

    A tight 1/2 guarantee holds against a benchmark that customizes after availability and controls dependence, even with cardinality constraints and adversarial truncation.

    Source: §8 · p. 28

  • Takeaways & Limitations

    Across applications, the framework provides a common analysis that improves approximation guarantees, extends settings, and retains factors against stronger benchmarks.

    Source: §8 · p. 28

    The core committed-firm setting assumes independent product availabilities and applies a cardinality limit to the realized display, with excess products subject to adversarial truncation.

    Source: §1.1 · p. 2

Abstract

from arXiv · show

We develop a unified framework for assortment optimization and matching under multinomial logit (MNL) choice, yielding simple algorithms and analyses across a broad class of problems. The framework centers on a single-customer assortment problem in which the firm commits to eligible products before their independent availabilities are revealed. A simple threshold policy achieves a tight $1/2$ guarantee against a benchmark that selects its assortment after observing availability and may control dependence subject to the same marginal probability bounds. This guarantee accommodates cardinality constraints and adversarial removal of excess available products. Combined with problem-specific linear programming relaxations, the framework yields $1/2$ guarantees for standard two-sided assortment optimization, customization under mixtures of MNL models, ride-hailing notifications, multi-round broadcast matching, and MNL prophet inequalities, and a $1/4$ guarantee for fully static two-sided assortment optimization. Across these applications, we improve approximation factors, extend guarantees to more general revenues and cardinality constraints, and retain existing factors against stronger benchmarks.

1 Introduction

Assortment and matching decisions under MNL face uncertainty both in what becomes available and in what customers choose. The paper builds a common framework around committing before availability is known, then applies it across assortment and matching settings.

1 Introduction

  • Random availability and choice complicate assortment decisions because alternatives compete for selection, while an added option can both create transaction opportunities and divert existing demand.Uncertainty can also arise when earlier assortment choices determine which potential partners are available.Source: §1 · p. 1

1.1 Problem description

  • The single-customer model commits to eligible products before independent availability is revealed; after availability, a magician may choose a feasible assortment and control dependence subject to marginal probability bounds.The delayed firm can customize its assortment to the realized available set; the committed firm faces adversarial truncation when more than k eligible products are available.Source: §1.1 · pp. 2–3

1.2 Our contributions

  • A tight 1/2 guarantee holds for a committed policy against a benchmark that can customize after availability and control dependence, even with cardinality constraints and adversarial truncation.The paper reports this guarantee as worst-case optimal across committed or delayed policies.Source: §1.2 · p. 3
  • The framework combines a threshold policy with problem-specific linear programming relaxations to analyze applications across static, multi-round, and online settings.The threshold policy commits to products whose distorted revenues meet a common threshold.Source: §1.2 · p. 4

Two-sided assortment optimization.

  • In two-sided assortment optimization, a 1/2 guarantee against an adaptive customized policy extends to cardinality constraints on both sides and arbitrary pair-dependent revenues.For fully static two-sided assortment optimization, the guarantee is 1/4 with pair-dependent revenues and cardinality constraints on both sides.Source: Two-sided assortment optimization · p. 5

Multi-round broadcast matching.

  • For multi-round broadcast matching, a static offer plan fixed before the first round achieves a 1/2 approximation against the optimal adaptive policy.The prior guarantee described for the general multiple-order setting was (1−e−3)/3.Source: Multi-round broadcast matching · p. 5

MNL prophet inequality.

  • For the MNL prophet problem, the paper retains a tight 1/2 guarantee against a stronger magician that may correlate products’ revenue–weight pairs while preserving their distributions.The magician can choose dependence across products in addition to observing all realizations before selecting an assortment.Source: MNL prophet inequality · p. 6

1.3 Related work

  • The framework distinguishes its cardinality treatment from related LP-based work: feasibility applies to the realized display, with excess available products removed adversarially.The magician selects a feasible assortment without committing in advance to an initial set.Source: §1.3 · p. 6

2 Main result

The section develops a distorted MNL model and LP bound to analyze a threshold policy for committed assortments. The policy gives a half-guarantee and extends to ranked MNL choice.

2.1 Distorted MNL choice model

  • The distorted MNL model handles adversarial truncation by representing the revenue-minimizing displayed subset while bounding each product’s choice probability.When k = ∞, the distorted model coincides with the original MNL model.Source: §2.1 · pp. 7–8

2.2 LP relaxation

  • The LP evaluated at distorted parameters upper-bounds the Magician’s optimal expected revenue.Its primal choice-probability variables obey availability and MNL choice-probability bounds, as well as a total-choice constraint.Source: §2.2 · pp. 9–10

2.3 Threshold policy

  • The threshold τ defines the eligible set H by distorted revenue, and it can be computed in polynomial time by sorting distorted revenues.The policy commits to H before product availabilities are realized.Source: §2.3 · pp. 10, 12
  • A committed threshold policy earns at least half the Magician benchmark’s expected revenue under independent availability and adversarial truncation.The policy commits to eligible products before availability is realized; its guarantee is established using a stronger result for negatively associated availability distributions.Source: §2.3 · pp. 10, 12

2.4 Extension to the ranked MNL choice model

  • The framework’s LP bound and threshold guarantee extend to ranked MNL choice, a generalization of MNL that simplifies analysis of applications.The extension follows by taking limits of standard MNL models with rank-scaled product weights.Source: §2.4 · p. 12

3 Two-sided assortment optimization

The section applies the framework to two-sided assortment optimization with pair-dependent revenues and cardinality constraints. It gives a half-guarantee for standard TSAO and a quarter-guarantee for fully static TSAO.

3 Two-sided assortment optimization

  • TSAO offers agents assortments across two market sides, and a match forms when both agents select each other.The objective is expected total match revenue; maximizing the number of matches is the unit-revenue special case.Source: §3 · p. 13

3.1 Standard two-sided assortment optimization

  • A randomized polynomial-time static policy for constrained standard TSAO earns at least 1/2 of the adaptive customized benchmark, even under adversarial truncation.The setting allows pair-dependent revenues and cardinality constraints on both sides of the market.Source: §3 · p. 13, §3.1 · p. 14

LP relaxation.

  • The LP relaxation upper-bounds the adaptive customized optimum by combining feasible customer choice probabilities with supplier-level bounds.A polynomial-time decomposition samples feasible customer assortments; threshold filtering then implements the static policy while preserving cardinality limits.Source: LP relaxation · pp. 16–17

3.2 Fully static two-sided assortment optimization

  • For constrained fully static TSAO with pair-dependent revenues, a randomized polynomial-time policy earns at least 1/4 of the fully static optimum.The approach applies the threshold guarantee on both sides of the market; supplier-side thresholding is used in the analysis while the algorithm selects optimal supplier assortments.Source: §3.2 · pp. 17–18

4 MMNL with customization

For MMNL assortment optimization with customization, a randomized polynomial-time algorithm achieves a 1/2 approximation, including with cardinality limits and class-dependent revenues. The guarantee also extends to class-dependent display limits.

4 MMNL with customization

  • A randomized polynomial-time algorithm achieves a 1/2 approximation for MMNL customization, including when revenues depend on product and customer class.The guarantee accommodates cardinality constraints on both the initial and displayed assortments.Source: §4 · p. 20
  • The guarantee extends to class-dependent display limits; a common limit k is used only to simplify the exposition.Source: §4 · p. 20
  • The algorithm optimizes shared marginal inclusion probabilities with an LP, samples an initial assortment of size ℓ, then tailors the display after observing the customer class.The sampled indicators are negatively associated, allowing the framework’s guarantee to be applied separately to each class.Source: §4 · p. 20
  • The LP objective is a weighted sum of single-customer bounds and upper-bounds the customized optimum, OPTMMNL.The proof combines this upper bound with the threshold policy’s revenue bound to establish the approximation guarantee.Source: §4 · pp. 20–21

5 Non-exclusive ride-hailing notifications

For non-exclusive ride-hailing notifications, a randomized polynomial-time policy guarantees at least half the optimal expected welfare under Best Acceptance, even when welfare is evaluated under Worst Acceptance. The result follows by reducing the notification problem to constrained two-sided assortment optimization.

5 Non-exclusive ride-hailing notifications

  • Drivers accept independently after notifications are fixed, and each driver can be notified about at most one rider.A match yields welfare rij; a rider’s assignment rule selects among accepting drivers.Source: §5 · p. 22
  • A randomized polynomial-time policy achieves at least half the optimal expected welfare under Best Acceptance, even when evaluated under Worst Acceptance.The same guarantee therefore holds under First Acceptance.Source: §5 · pp. 22–23
  • The reduction maps drivers to customers and riders to suppliers, with ranked MNL singleton choices representing acceptance and rider assignment.Customization, adversarial truncation, and uniform selection represent Best, Worst, and First Acceptance, respectively.Source: §5 · pp. 22–23
  • The feasible notification choices have an exact linear representation, and independent sampling followed by threshold filtering produces a polynomial-time policy.The sampled notifications are fixed before acceptances and notify each driver about at most one rider.Source: §5 · p. 23

6 Multi-round broadcast matching

For multi-round broadcast matching, a randomized polynomial-time policy achieves at least half the adaptive optimum. It uses an LP relaxation over driver offer lists and filters sampled lists by order-specific revenue thresholds.

6 Multi-round broadcast matching

  • A randomized polynomial-time policy achieves expected revenue of at least half the adaptive optimum in multi-round broadcast matching.The guarantee matches the paper’s 1/2 bound against the same adaptive benchmark, improving on the stated prior factors for single- and multiple-order settings.Source: §6 · p. 23
  • The policy independently samples a list for each driver and removes entries whose match revenue falls below that order’s threshold.It simulates responses to already-matched orders so drivers’ first acceptance follows the filtered-list law; a driver becomes inactive at its first acceptance.Source: §6 · pp. 24–25
  • The LP relaxation upper-bounds the adaptive optimum and has an optimal solution with polynomially many nonzero coefficients computable in polynomial time.It represents each driver’s matching probabilities by a distribution over offer lists.Source: §6 · p. 24
  • For each order, the expected revenue is at least its threshold; summing these bounds shows the LP value is at most twice the policy revenue.The LP upper bound then yields the 1/2 guarantee against the adaptive optimum.Source: §6 · pp. 25–26

7 MNL prophet inequality

For the MNL prophet problem with a cardinality constraint, a static threshold policy guarantees at least half the magician’s expected revenue, even against an almighty adversary. The magician may choose dependence among parameter pairs while preserving each pair’s marginal distribution.

7 MNL prophet inequality

  • The magician may choose any joint distribution of product parameter pairs that preserves each pair’s prescribed distribution, then select the best feasible assortment.The firm’s parameter pairs remain independent, and the magician’s benchmark is at least the usual prophet’s expected revenue.Source: §7 · p. 27
  • A static threshold policy guarantees at least OPTM /2 under a cardinality constraint, even when an almighty adversary chooses the arrival order.The guarantee retains the 1/2 factor while strengthening the benchmark relative to the usual prophet.Source: §7 · p. 27
  • The policy computes one threshold before arrivals and accepts a product when its distorted revenue meets the threshold and fewer than k products have been accepted.The proof represents each possible parameter realization as a separate product copy, with exactly one copy available per original product.Source: §7 · p. 27

8 Conclusion

The paper develops a unified MNL framework for assortment optimization and choice-based matching, centered on a single-customer assortment problem. Its threshold policy and analysis provide a common tool for applications and may guide future connections to problem-specific LP relaxations.

8 Conclusion

  • The framework unifies assortment optimization and choice-based matching under the MNL model.It centers on a single-customer assortment problem.Source: §8 · p. 28
  • A simple threshold policy achieves a tight 1/2 guarantee against a benchmark that can customize assortments and control dependence, including with cardinality constraints and adversarial truncation.The analysis uses a compact LP relaxation.Source: §8 · p. 28
  • The authors suggest connecting problem-specific LP relaxations to the single-customer model as a starting point for exploring other assortment and matching problems.Such connections may reveal further settings where simple policies achieve strong guarantees.Source: §8 · p. 28

A Tight lower bounds for the pairwise gaps

The section establishes that each of the three pairwise gaps is at most two and gives matching lower bounds.

A Tight lower bounds for the pairwise gaps

A.1 Gap between the committed and delayed firms

The committed-versus-delayed gap is 2 even without a cardinality constraint. A two-product construction shows the ratio can approach that bound as ε decreases to zero.

A.1 Gap between the committed and delayed firms

  • The committed-versus-delayed gap is 2, even without a cardinality constraint.The gap is the supremum of OPTD / OPTC, comparing choosing after observing independent availability with committing beforehand.Source: §A.1 · p. 31
  • For the two-product construction, the best committed assortment contains both products and has value OPTC = 1 + ε(1 − ε) / ((1 + ε)(1 + 2ε)).The construction uses no cardinality constraint and 0 < ε < 1.Source: §A.1 · p. 31
  • The delayed firm selects product 2 alone when available and product 1 otherwise, and the resulting ratio tends to 2 as ε decreases to zero.The singleton revenue of product 2 exceeds the alternatives when it is available.Source: §A.1 · p. 31

A.2 Gap between the delayed firm and the magician

The delayed-versus-magician gap is 2 even without a cardinality constraint. A construction with rare products shows the ratio approaches 2 as the number of products grows.

A.2 Gap between the delayed firm and the magician

  • The delayed-versus-magician gap is 2, even without a cardinality constraint.The gap compares the magician's best joint availability distribution with independent availabilities, while each firm chooses its best feasible subset.Source: §A.2 · pp. 32–33
  • The construction uses m rare products with availability probability m^-1/2 and an always-available product n; under the magician's distribution, all rare products are available together with probability m^-1/2.The joint distribution preserves the products' inclusion marginals.Source: §A.2 · p. 32
  • The resulting gap approaches 2 as m grows, matching the upper bound from Theorem 1.The construction is a variant of the correlation-gap tightness example in Ahmadnejadsaein and El Housni [2025, Appendix D].Source: §A.2 · pp. 32–33

B Proof of Lemma 3

Lemma 3 characterizes the feasible choice-probability vectors as the convex hull of MNL choice vectors from feasible assortments. It also gives a polynomial-time procedure for computing a distribution over assortments with the required marginals.

B Proof of Lemma 3

  • Reweighting the decomposition of a scaled vector produces a distribution over MNL assortment choice vectors.The resulting coefficients are nonnegative and sum to one.Source: B Proof of Lemma 3 · p. 34
  • The feasible choice-probability vectors are exactly the convex hull of the MNL choice vectors of assortments of size at most k.Each feasible assortment's vector lies in the polytope, and the proof establishes the converse through a decomposition into assortment choice vectors.Source: B Proof of Lemma 3 · pp. 33–34
  • A polynomial-time procedure computes the decomposition by sorting dual coefficients and applying optimization–separation equivalence.The resulting assortment distribution has polynomially many nonzero coefficients.Source: B Proof of Lemma 3 · p. 34

C Proof of Theorem 3

The proof bounds the fully static optimum by an LP relaxation and compares Algorithm 2 with that relaxation using customer- and supplier-side guarantees. Together, these bounds establish a 1/4 approximation for the fully static policy.

C Proof of Theorem 3

  • The customer-side analysis applies the threshold policy with independent availabilities and retains at least the revenue under adversarial truncation.The policy keeps min{|Ai ∩ Hi|, k} suppliers; Lemma 2 supplies the guarantee used in the proof.Source: C Proof of Theorem 3 · p. 35
  • The supplier-side threshold policy earns at least half the bound obtained using the distorted revenues.Algorithm 2's best feasible supplier assortment earns at least as much in expectation as this threshold policy.Source: C Proof of Theorem 3 · p. 36
  • LPFS ≤ 4 ALGFS, yielding a 1/4 guarantee for Algorithm 2 against the fully static optimum.The proof first establishes OPTFS ≤ LPFS, so the LP comparison implies the approximation guarantee.Source: C Proof of Theorem 3 · pp. 34–36
  • Algorithm 2 runs in polynomial time using sorting for customer thresholds and cardinality-constrained MNL revenue maximization for supplier assortments.The proof also establishes that its assortments have size at most k and are fixed before agents choose.Source: C Proof of Theorem 3 · p. 36

D Proof of Lemma 4

The proof upper-bounds the adaptive optimum by LP (6.1) using simulated driver-specific lists. It establishes polynomial-time solvability through a dual separation procedure based on sorting and dynamic programming.

D Proof of Lemma 4

  • OPTBM ≤ LPBM, established by simulating the adaptive policy to construct a random list for each driver.The retained acceptance variables remain independent conditional on the list, and the construction couples the simulated and actual executions.Source: D Proof of Lemma 4 · p. 37
  • The dual separation problem orders candidate orders by decreasing rij − βi and uses dynamic programming to select a list.The recursion compares including the current order with omitting it.Source: D Proof of Lemma 4 · p. 38
  • The dynamic program yields a polynomial-time separation procedure, and optimization–separation equivalence solves LP (6.1) in polynomial time.The recovered solution has polynomially many nonzero coefficients.Source: D Proof of Lemma 4 · p. 38
Loading 2610.35389v1…