pith. sign in

arxiv: 2403.08929 · v6 · submitted 2024-03-13 · 🧮 math.OC · cs.DS

Two-sided Assortment Optimization: Adaptivity Gaps and Approximation Algorithms

Omar El Housni , Ulysse Hennebelle , Alfredo Torrico This is my paper

Pith reviewed 2026-05-24 02:53 UTC · model grok-4.3

classification 🧮 math.OC cs.DS
keywords two-sided assortment optimizationadaptivity gapsapproximation algorithmschoice-based matchingmultinomial logitconstrained assortmentmatching platformspolicy classes
0
0 comments X

The pith

The adaptivity gaps between policy classes in two-sided assortment optimization are exactly e/(e-1) and 2.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes exact adaptivity gaps for different classes of policies in two-sided assortment optimization problems under general choice preferences. These gaps measure the worst-case ratio of optimal expected matches between static and adaptive policies that display assortments to one side first, and between those and fully sequential policies that show assortments to agents one by one. A sympathetic reader would care because it helps platforms decide the level of adaptivity needed in their matching algorithms to balance performance and complexity. The work also develops approximation algorithms for solving the underlying optimization problems within these policy classes, including a 1/4-factor for fully adaptive policies and a 0.067-factor under multinomial logit for simultaneous display.

Core claim

In the two-sided assortment optimization framework, the goal is to maximize the expected number of matches by choosing which assortments to display to agents on both sides and in what order. The paper proves that the adaptivity gap between the class of policies that statically show assortments to one side first and those that adaptively show to one side first is exactly e/(e-1). It further shows that the gap to the fully adaptive class, where assortments are shown to agents one by one, is exactly 2. Polynomial-time approximation algorithms are provided, achieving 1/4 for the fully adaptive class and 0.067 under multinomial logit for simultaneous display, with generalizations to constrained,

What carries the argument

Adaptivity gap, defined as the worst-case ratio between the optimal values of two different policy classes in the two-sided assortment optimization problem.

If this is right

  • A polynomial-time 1/4-approximation algorithm exists for the class of fully adaptive policies that show assortments one by one.
  • Under multinomial logit models, a 0.067-approximation factor holds for the class of policies that show assortments to all agents at once.
  • The results generalize to constrained assortment settings with an upper bound on displayed assortment sizes.
  • Policies that simultaneously show assortments to all agents achieve the worst performance among the classes considered.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The exact gaps provide a benchmark that platforms can use to evaluate whether adding partial adaptivity is worth the implementation cost in specific markets.
  • If choice preferences must be learned rather than known exactly, the reported gaps could serve as a baseline for designing robust variants of the policies.
  • The framework could be tested on data from other two-sided platforms such as ride-sharing or job matching to check if the same gap values appear.
  • The approximation algorithms might be combined with online learning techniques to handle cases where preferences evolve over time.

Load-bearing premise

Agents' choice preferences are known in advance and can be used to compute exact expected match probabilities for any sequence of assortments under the chosen policy class.

What would settle it

A problem instance where the ratio of optimal values between adaptive one-side first policies and static one-side first policies has a supremum different from e/(e-1), or between adaptive one-side and fully adaptive one-by-one policies different from 2.

read the original abstract

To address efficiency and design challenges in choice-based matching platforms, we introduce a two-sided assortment optimization framework under general choice preferences. The goal in this problem is to maximize the expected number of matches by deciding which assortments are displayed to the agents and the order in which they are shown. In this context, we identify several classes of policies that platforms can use in their design. Our goals are: (1) to measure the value that one class of policies has over another one, and (2) to approximately solve the optimization problem itself for a given class. For (1), we define the adaptivity gap as the worst-case ratio between the optimal values of two different policy classes. First, we show that the gap between the class of policies that statically show assortments to one-side first and the class of policies that adaptively show assortments to one-side first is exactly $e/(e-1)$. Second, we show that the gap between the latter class of policies and the fully adaptive class of policies that show assortments to agents one by one is exactly $2$. We also note that the worst policies are those who simultaneously show assortments to all the agents. For (2), we first design a polynomial time algorithm that achieves a $1/4$ approximation factor within the class of policies that adaptively show assortments to agents one by one. Furthermore, when agents' preferences are governed by multinomial-logit models, we show that a 0.067 approximation factor can be obtained within the class of policies that show assortments to all agents at once. We further generalize our results to constrained assortment settings, where we impose an upper bound on the size of the displayed assortments. Finally, we present a computational study to evaluate the empirical performance of our theoretical guarantees.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper introduces a two-sided assortment optimization framework under general choice preferences to maximize expected matches by selecting and ordering assortments displayed to agents on both sides. It defines three policy classes differing in adaptivity (static one-side-first, adaptive one-side-first, and fully adaptive one-by-one), proves exact adaptivity gaps of e/(e-1) and 2 between them, shows that simultaneous display to all agents is worst, provides a 1/4-approximation algorithm for the fully adaptive class and a 0.067-approximation for the simultaneous class under MNL, generalizes results to cardinality-constrained assortments, and includes a computational study.

Significance. If the exact gaps and approximation ratios hold, the work provides fundamental, tight characterizations of the value of adaptivity in two-sided choice-based matching, which has direct implications for platform design in operations research. The polynomial-time algorithms and constrained generalizations add practical value; the computational study offers empirical grounding for the theoretical bounds.

minor comments (3)
  1. [Abstract] Abstract and introduction: the statement that simultaneous-display policies are 'worst' should include an explicit reference to the theorem or proposition establishing this (e.g., as a corollary of the gap of 2).
  2. [Abstract] The 0.067 factor for the MNL simultaneous case is unusually specific; a brief remark on whether it arises from a particular rounding or LP relaxation (and whether it can be improved) would aid readability.
  3. Notation for policy classes (static vs. adaptive one-side-first) should be introduced with a short table or diagram early in the paper to avoid ambiguity when the gaps are stated.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of our work on two-sided assortment optimization, including the exact adaptivity gaps, approximation algorithms, and computational study. We appreciate the recommendation for minor revision and the recognition of the paper's significance for platform design. No specific major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained

full rationale

The paper establishes exact adaptivity gaps of e/(e-1) and 2 as worst-case ratios between optimal values of three policy classes (static one-side, adaptive one-side, fully adaptive) via analysis under general choice preferences. These ratios are asserted as derived bounds without any reduction to fitted parameters, self-definitional loops, or load-bearing self-citations in the stated claims. The assumption that preferences are known is definitional for computing expectations and does not force the gap values by construction. No steps match the enumerated circularity patterns; the central results remain independent of the paper's own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on the standard domain assumption that choice probabilities are well-defined for any assortment and can be used to compute expected matches; no free parameters or invented entities are introduced in the abstract.

axioms (1)
  • domain assumption Agents follow general choice models that assign selection probabilities to items within any displayed assortment.
    Required to define expected number of matches for any policy.

pith-pipeline@v0.9.0 · 5868 in / 1313 out tokens · 26330 ms · 2026-05-24T02:53:52.564599+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

15 extracted references · 15 canonical work pages

  1. [1]

    Information Processing Letters 111(15):731–737

    Adamczyk M (2011) Improved analysis of the greedy algorithm for stochastic matching. Information Processing Letters 111(15):731–737. Adamczyk M, Sviridenko M, Ward J (2016) Submodular stochastic probing on matroids. Mathematics of Operations Research 41(3):1022–1038. Agarwal A, Assadi S, Khanna S (2019) Stochastic submodular cover with limited adaptivity....

    work page 2011

  2. [2]

    Manufacturing & Service Operations Manage- ment 23(3):620–636

    Arnosti N, Johari R, Kanoria Y (2021) Managing congestion in matching markets. Manufacturing & Service Operations Manage- ment 23(3):620–636. Asadpour A, Nazerzadeh H (2016) Maximizing stochastic monotone submodular functions. Management Science 62(8):2374–

    work page 2021

  3. [3]

    Management Science 66(5):2163–2193

    Ashlagi I, Braverman M, Kanoria Y , Shi P (2020) Clearing matching markets efficiently: Informative signals and match recommen- dations. Management Science 66(5):2163–2193. Ashlagi I, Krishnaswamy AK, Makhijani R, Saban D, Shiragur K (2022) Technical note—assortment planning for two-sided sequential matching markets. Operations Research 70(5):2784–2803. B...

    work page arXiv 2020

  4. [4]

    Operations research 58(6):1666–1680

    Rusmevichientong P, Shen ZJM, Shmoys DB (2010) Dynamic assortment optimization with a multinomial logit choice model and capacity constraint. Operations research 58(6):1666–1680. Rusmevichientong P, Shmoys D, Tong C, Topaloglu H (2014) Assortment optimization under the multinomial logit model with random choice parameters. Production and Operations Manage...

    work page arXiv 2010

  5. [5]

    Finally, Equality (21) is the linear approximation for the exponential function

    is increasing and that the ri are bounded by n. Finally, Equality (21) is the linear approximation for the exponential function. Therefore, we conclude that E[MC] ≤ 1 − 1 e · n + O(√n). Now, let us look at (S-One-sided Static). We denote asMS the random variable counting the number of matches in that setting, and as ki the random variable counting the num...

    work page 2023

  6. [6]

    Let us denote by C t j the observed backlog of supplier j ∈ S and by Mt the number of matches in the t-th run

    and T independent runs of Algorithm 1, which we will determine later. Let us denote by C t j the observed backlog of supplier j ∈ S and by Mt the number of matches in the t-th run. We would like to estimate the expected total number of matches, which we denote byµ = Eπ hP j∈S fj(C π j ) i where the expectation is over the customers’ choices which are depe...

    work page 2009

  7. [7]

    Denote by C ⋆ 1 ,

    To prove the claim, we construct a feasible policy using an optimal solution of M ⋆. Denote by C ⋆ 1 , . . . , C⋆ |S| an optimal partition for M ⋆ and, for every i ∈ C, denote ji the supplier that verifies i ∈ Cji. Define the one-sided static policy that showsSi = arg maxS⊆S ϕi(ji, S) for each i ∈ C. The objective value of this policy satisfies OPT(C-OA) ...

    work page 2011

  8. [8]

    The proof of Lemma 15 follows the same structure as the proof of Lemma 2, where we show that the LP in (3) is a relaxation of ( C-One-sided Adaptive) in the unconstrained setting

    OPT(25) ≥ OPT(C-OA). The proof of Lemma 15 follows the same structure as the proof of Lemma 2, where we show that the LP in (3) is a relaxation of ( C-One-sided Adaptive) in the unconstrained setting. We do not restate the full argument here, but highlight the main differences: (i) the expected objective now involves the constrained demand functions f K j...

    work page 2011

  9. [9]

    2010), where λ† is a feasible solution of max λ≥0 (X j∈S X C⊆C fj(C) · λj,C : X C⊆C λj,C = 1, ∀j ∈ S, X C:C∋i λj,C = x† ij, ∀i ∈ C, j ∈ S )

    In the fifth inequality, we use the correlation gap for monotone submodular functions (Agrawal et al. 2010), where λ† is a feasible solution of max λ≥0 (X j∈S X C⊆C fj(C) · λj,C : X C⊆C λj,C = 1, ∀j ∈ S, X C:C∋i λj,C = x† ij, ∀i ∈ C, j ∈ S ) . (27) Note that this problem is not the same as (25) since we replaced f K j by fj. Also, it is important to obser...

    work page 2010

  10. [10]

    Point (i) follows by construction, and points (ii) and (iv) by linearity

    We repeat this procedure for every λ⋆ j,C > 0 with |C| > Kj. Point (i) follows by construction, and points (ii) and (iv) by linearity. Finally, point (iii) also follows by linearity, but notice that we may set someλ⋆ to 0, which would decrease the left hand side in (25c). □ Extension to other constraints. Note that if we have a monotone CR scheme that is ...

    work page 2011

  11. [11]

    Under the MNL choice model, the constrained demand function defined in (24) is submodular. Proof. Consider any supplier j ∈ S (a similar argument applies for customers). Then, for every C ⊆ C, we have f K j (C) = max wj(C ′) 1 +wj(C ′) : |C ′| ≤ Kj, C ′ ⊆ C , ∀ C ⊆ C, where wj(C ′) =P i∈C′ wji. Since the function x/(1 + x) is increasing, we note that the ...

    work page 1978

  12. [12]

    Here, it is important to remark that the previous argument is possible because γij ≥ 0 for all i ∈ C , j ∈ S . Then, if αi <P j∈A γij · ϕi(j, A), we include the corresponding constraint; otherwise, there are no constraints to be added; • Second, we can approximately separate Constraints (29b) in polynomial time as follows: Fix j ∈ S and, using the distort...

    work page 2019

  13. [13]

    (31) Given the above, let (Modified Primal) be Problem (25) with the following modified constraints: X C⊆C λj,C = e e − 1 , for all j ∈ S, (32) X S⊆S τi,S = e e − 1 , for all i ∈ C

    and (Jansen 2003)), we can obtain a point (α, β, γ) such that βj + X i∈C γij ≥ (1 − 1/e) · fj(C) for all j ∈ S, C ⊆ C, |C| ≤ Kj, (30) αi − X j∈S γij · ϕi(j, S) ≥ 0 for all i ∈ C, S ⊆ S, |S| ≤ Ki. (31) Given the above, let (Modified Primal) be Problem (25) with the following modified constraints: X C⊆C λj,C = e e − 1 , for all j ∈ S, (32) X S⊆S τi,S = e e ...

    work page 2003

  14. [14]

    (see their Theorem II.4) which, for our problem, guarantees the following: LEMMA 19 (Chekuri et al. (2010)). There exists a randomized polynomial-time algorithm for Problem (37) that achieves a 1 − 1/e approximation factor. Finally, as in Lemma 10, any solution y to Problem (37) with objective value val will have an objective value of at least α 1+α · val...

    work page 2010

  15. [15]

    We can easily verify that x is a solution for Problem (11) with the same objective value as (y, z) for Problem (38). □ F.1.2. Upper Bound for (One-sided Adaptive). Assume that customers and suppliers follow MNL choice mod- els. Consider the following concave program zC = max X j∈S zj 1 +zj (39) yij + X ℓ∈S viℓyiℓ ≤ 1, ∀i ∈ C, ∀j ∈ S, yij ≥ 0, ∀i ∈ C, ∀j ∈...

    work page 2023