Pith. sign in

REVIEW 2 major objections 5 minor 21 references

Adaptive Two-sided Assortment Optimization: Revenue Maximization

T0 review · 2 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read For any epsilon, a static algorithm captures at least half of the optimal adaptive expected revenue in two-sided assortment.

desk verdict Genuinely new approximation results for revenue in adaptive two-sided assortment, but the polynomial-time solver for the key LP rests on an unjustified inequality in Lemma 3 that needs fixing before the main theorem is solid. read the letter →

arxiv 2507.04156 v3 pith:CFG3Z2AP submitted 2025-07-05 cs.GT math.OC

Mohammadreza Ahmadnejadsaein , Omar El Housni This is my paper · ORCID
classification cs.GTmath.OC MSC 68W2590C2791B26
keywords two-sidedassortmentoptimizationrevenuemaximizationMultinomialLogit(MNL)adaptivepoliciesapproximationalgorithmscorrelationgapLPrelaxationsubmodularorder
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper studies adaptive two-sided assortment optimization where the platform's goal is expected revenue, not the number of matches. The platform sequentially shows each initiating-side agent an assortment of responding-side agents, observes the choices, then lets responding agents pick from those who chose them; a match is mutual and all choices follow individual Multinomial Logit (MNL) models. The paper's central claim is that, even though the revenue objective breaks the submodularity that prior work relied on, polynomial-time constant-factor algorithms exist: a randomized static policy achieves $(1/2 - \epsilon)$ of the optimal adaptive expected revenue for any $\epsilon > 0$, and $(1 - 1/e - \epsilon)$ when each supplier's revenues are uniform across customers. Under a common revenue ordering across suppliers, a deterministic adaptive greedy policy achieves exactly $1/2$. If these results are right, revenue-maximizing platforms can use simple sampling or greedy rules with guaranteed performance, improving on the known $1/3$ guarantee for the static customized model.

What carries the argument

The engine is a linear programming relaxation (LP-II) with exponentially many variables, whose dual separation reduces to assortment optimization with fixed costs and is solved approximately by an FPTAS; the solution's marginals are then converted into a distribution over assortments for each customer using the MNL polyhedron. The loss from replacing the correlated LP solution by independent sampling is controlled by a correlation gap bound on the optimal revenue function $g(A) = \max_{A' \subseteq A} \sum_{i \in A'} r_i \phi(i, A')$. That bound comes from building a cost-sharing scheme on top of the submodular-order property of $g$: telescoping marginal contributions gives budget balance, and the submodular-order inequality gives cross-monotonicity, yielding a correlation gap of at most $2$, or $e/(e-1)$ when revenues are equal. For the same-order case, the same structural property powers an interleaved-partition bound that makes the primal-dual analysis of the deterministic greedy algorithm go through.

What would settle it

Find a single MNL instance (preference weights, outside option normalized to 1, and nonnegative revenues) where the optimal revenue function $g(A)=\max_{A'\subseteq A}\sum_{i\in A'} r_i\phi(i,A')$ violates the submodular-order inequality: for some $A\subseteq B$ and a set $C$ entirely after $B$ in descending revenue order, $g(C\mid B)>g(C\mid A)$. If such an instance exists, the correlation-gap bound of $2$ and the same-order greedy proof both fail, and the approximation ratios would need revisiting.

Watch

Extended reading notes

Core claim

The paper claims that the adaptive revenue-maximization problem (ATAR) admits polynomial-time constant-factor approximations, even though the optimal revenue function $g_j(C)$ is monotone but not submodular under heterogeneous revenues. Its main theorem states that for any $\epsilon > 0$ a randomized static algorithm achieves a $(\frac{1}{2} - \epsilon)$-approximation in general, and a $(1 - \frac{1}{e} - \epsilon)$-approximation when revenues are uniform across all pairs involving a given supplier; because the algorithm is static, the same guarantee holds under fixed-order, simultaneous, and adaptive processing of initiating agents. A second theorem shows that under the same-order condition (all suppliers rank customers identically by revenue), a deterministic adaptive greedy algorithm achieves a $\frac{1}{2}$-approximation. The paper also proves a correlation gap bound of $2$ for the optimal MNL revenue function in general and $e/(e-1)$ for equal revenues, and provides a way to approximately solve the underlying exponentially large LP relaxation in polynomial time.

Load-bearing premise

The load-bearing premise is an imported structural fact: the optimal revenue a supplier can extract from a set of customers has a diminishing-returns-type property when customers are considered in descending revenue order, even though it is not submodular in general; both central theorems rely on that fact.

Editorial extensions

If this is right

  • General heterogeneous revenues are no longer a barrier: a polynomial-time, non-adaptive policy guarantees at least half of the optimal adaptive expected revenue, and about 63 percent when each supplier's revenue is uniform across customers.
  • Because the guarantee is against an LP relaxation of the adaptive problem and the policy is static, the same performance holds whether initiating agents arrive in an adaptive, fixed, or simultaneous order.
  • The uniform-per-supplier bound of $(1 - 1/e - \epsilon)$ improves the known $1/2$ approximation for match-count maximization under MNL choice, since match count is the special case of uniform revenues.
  • For the customized static model with pairwise revenues, the static algorithm gives a $(\frac{1}{2} - \epsilon)$-approximation, improving the previous $1/3$.
  • Under a same-order revenue structure, a deterministic adaptive greedy algorithm attains exactly $\frac{1}{2}$ with much lower computational cost than the LP-based static algorithm.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the submodular-order lemma extends beyond MNL to models like mixtures of MNL, the same LP-plus-correlation-gap template would plausibly give constant-factor revenue guarantees there; the paper leaves that extension open.
  • The experiments suggest the deterministic greedy rule performs well even when the same-order condition is relaxed and customers are ordered by average revenue, but the paper only claims a guarantee under same-order revenues; testing the greedy rule on instances with conflicting revenue rankings would be a natural stress test.
  • The static algorithm's correlation-gap bound of $2$ implies that the value of adaptivity for revenue maximization with heterogeneous pair revenues is at most a factor of $2$, in contrast with the known $1 - 1/e$ adaptivity gap for match-count objectives; settling whether $2$ is tight would quantify how much sequential adaptation is worth in revenue terms.
  • Because the guarantee is worst-case over MNL parameters, an instance-dependent refinement of the correlation-gap analysis, using the actual preference weights, could yield tighter performance bounds in practice.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

Summary. The paper studies adaptive two-sided assortment optimization under MNL choice models with pair-dependent revenues. The main claimed contributions are: (i) a randomized static polynomial-time algorithm achieving a (1/2 - ε)-approximation for general revenues and a (1 - 1/e - ε)-approximation when revenues are uniform per supplier (Theorem 1); and (ii) a deterministic adaptive greedy 1/2-approximation under a same-order revenue condition (Theorem 2). The analysis introduces LP relaxations (LP-I) and (LP-II), an Ellipsoid-based FPTAS for solving (LP-II), a correlation-gap bound for the optimal MNL revenue function, and a primal-dual analysis of the greedy algorithm. Numerical experiments compare the algorithms against an LP benchmark.

Significance. If the results are fully established, they would improve the best-known constant-factor guarantee for static one-sided revenue-maximizing assortment from 1/3 (Nissim et al.) to 1/2, and would improve the match-count one-sided adaptive guarantee from 1/2 to 1 - 1/e in the uniform-revenue case. The LP relaxation (LP-II), the equivalence argument with the active-set reformulation, and the correlation-gap proof for the optimal revenue function are coherent and original contributions. The greedy primal-dual analysis under same-order revenues is also a valuable structural result. The main weakness is that the polynomial-time solvability of (LP-II), on which Theorem 1 rests, depends on a proof gap in Lemma 3.

major comments (2)
  1. [Appendix B.2, Lemma 3, Eq. (7)] The inequality r' ≤ (Dual-II-Aux) is not justified. The approximate separation oracle may fail to detect exact violations of the (Dual-AC_j) constraints, so the point (α', β', γ') returned at termination need not be feasible for (Dual-II-Aux). An infeasible point for a minimization LP can have objective value on either side of the optimum; it is not a valid lower bound merely because the oracle approximated the feasible region. Consequently the chain (Dual-II-Aux) ≥ r' ≥ (1-δ)(LP-II) is unproved, and the conclusion that (LP-II-Aux) is a (1-δ)-approximation to (LP-II) does not follow. Since Lemma 3 is the only bridge from the exponentially large (LP-II) to a polynomial-time implementation, Theorem 1's algorithmic claim is not established by the current proof. A corrected argument should either construct a genuinely feasible dual point with objective at least (1-δ)(LP-II), or prove directly that the restricted primal (LP-II-Aux) approximates (LP-II).
  2. [Appendix B.2, Algorithm 3] The 'best feasible solution' tracking in Algorithm 3 is affected by the same issue: when no violated constraint is found by the (1-δ)-approximate oracle, the algorithm declares the current point feasible, but it may still violate exact constraints. Therefore the returned objective obj is not guaranteed to be attained by a feasible dual solution, and the subsequent use of obj (or r') as a lower bound on (LP-II) is not valid without additional scaling or rounding arguments from the approximate-ellipsoid literature.
minor comments (5)
  1. [Section 3.2, Lemma 6] Lemma 6 is imported from Udwani (2023) and is load-bearing for both the correlation-gap bound (Lemma 4) and the greedy analysis (Theorem 2). Since the manuscript cites the result as Lemma 9 without proof, please state the exact conditions, confirm that they hold for MNL with an outside option, and consider including a short proof or a more precise pointer in an appendix.
  2. [Section 4.2, Eq. (4)] The 'interleaved partition bound' (Eq. (4)) is used as a black box from Udwani (2023). Because it is the key step in proving the first family of dual constraints for the greedy algorithm, the authors should state it as a named lemma with its exact hypotheses and reference, so the proof is self-contained enough to verify.
  3. [Appendix B.2, Lemma 3 / Algorithm 3] The initial feasible solution (0_nm, 1_m, 0_nm) used in Algorithm 3 is feasible only after normalizing revenues so that R_j(C) ≤ 1 for all j and C. This normalization should be stated explicitly in Lemma 3's statement, not only in a footnote inside the algorithm proof.
  4. [Algorithm 3] In Step 2(a), the line 'If Σ_j β_j + Σ_{i,j} α_ij ≥ obj, set a = -d and go to Step 2(b)' is not fully explained; the objective cut used by the Ellipsoid method should be described so that the reader can verify that the separation oracle is complete.
  5. [Section 3.3, Lemma 7] In Lemma 7, the proof that Pi[Si(0)] ≥ 0 relies on the third family of constraints of (LP-II) together with the ordering assumption; spelling this dependence out would make the construction easier to verify.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the main approximation guarantees are derived from explicit LP relaxations and external submodular-order results, not from the target quantities.

full rationale

The central derivation chain is self-contained against external benchmarks. Lemma 1 and Lemma 2 establish that (LP-I)/(LP-II) relax (ATAR) through explicit projection and active-set arguments (Appendix B.1 and Section 3.1.1); no target value is used as an input. Lemma 4's correlation gap bound is proved in the text from a cost-sharing scheme whose budget-balance is verified by telescoping and whose cross-monotonicity uses Lemma 6, imported from Udwani (2023) in exactly the MNL optimal-revenue setting. That is an external, falsifiable result, not a self-citation. Theorem 1 then compares the static algorithm only against the LP upper bound, so the quoted 1/2 and 1-1/e factors are not reverse-engineered from the algorithm's output. Theorem 2's 1/2-approximation is likewise supported by a complete randomized dual-feasibility proof in Section 4.2, with the submodular-order/interleaved-partition facts attributed to Udwani. The only self-citation (El Housni et al. 2024) is used as a source of the LP template and primal-dual technique, but the relevant lemma is proved in the appendix and the dual argument is re-derived, so it is not load-bearing. The one serious caveat found is in Lemma 3 (Appendix B.2): the assertion that the approximate-oracle ellipsoid solution satisfies r' <= (Dual-II-Aux) is not established, and the chain (Dual-II-Aux) >= r' >= (1-delta)(LP-II) would need a corrected argument. This is a potential proof gap in the polynomial-time claim of Theorem 1, but it is a correctness/rigor issue rather than a circularity, since nothing is assumed to equal the target result.

Assumptions & free parameters 0 free parameters · 8 assumptions · 0 invented entities

The report rests on MNL single-choice assumptions plus three external theorems: Agrawal et al.'s correlation gap bounds, Udwani's submodular-order/interleaved-partition results, and Chen et al.'s FPTAS for assortment with arbitrary costs. No data-fitted free parameters appear; accounting parameters epsilon and delta are accuracy controls, not fitted values. The ledger is therefore light for an algorithmic theory paper.

assumptions (8)
  • domain assumption MNL choice with normalized outside option (ui0 = wj0 = 1) for all customers and suppliers
    Defines the choice model in Section 2.1; all results are for MNL only and do not extend to general choice models.
  • domain assumption Each agent selects at most one counterpart from the offered assortment
    Section 1.1; customer backlogs are therefore disjoint, which is used in the dynamic program, in the LP-I relaxation, and in the greedy dual proof.
  • standard math Udwani (2023), Lemma 9: the optimal MNL revenue function g is monotone, subadditive, and submodular order with respect to descending revenue order
    Load-bearing for the correlation gap bound (Lemma 4) and for the same-order greedy analysis (Theorem 2); cited, not reproduced.
  • standard math Agrawal et al. (2012), Theorem 4: correlation gap bounds for monotone submodular functions and for functions admitting a beta-cost-sharing scheme
    Lemma 5 in Section 3.2; imports the key external correlation gap results.
  • standard math Chen et al. (2025): FPTAS for assortment optimization with arbitrary fixed costs, applicable with an arbitrary cardinality constraint
    Used as the separation oracle for (Dual-II) in Section 3.1.2; the theorem's hypotheses are not restated in the paper.
  • standard math Udwani (2023): interleaved partition bound used as Equation (4)
    Used in Theorem 2's proof of the first family of dual constraints (Section 4.2); cited, not reproduced.
  • standard math Under MNL without cardinality constraints, the optimal assortment is revenue-ordered
    Used to justify efficient implementation of Algorithm 2, Step 4 and the supplier-side optimal assortment step.
  • standard math Strong duality holds for the finite-dimensional LPs (LP-I), (LP-II), and their duals
    Invoked in Lemma 3's proof and in Theorem 2's dual argument; standard, with citations to Bertsimas and Tsitsiklis.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Adaptive Two-sided Assortment Optimization: Revenue Maximization." pith.science (2026). https://pith.science/paper/CFG3Z2AP

@misc{pith2026250704156,
  author       = {Pith},
  title        = {Pith review of: Adaptive Two-sided Assortment Optimization: Revenue Maximization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CFG3Z2AP}},
  note         = {Machine review of arXiv:2507.04156}
}
abstract

We study adaptive two-sided assortment optimization for revenue maximization in choice-based matching platforms. The platform has two sides of agents, an initiating side, and a responding side. The decision-maker sequentially selects agents from the initiating side, shows each an assortment of agents from the responding side, and observes their choices. After processing all initiating agents, the responding agents are shown assortments and make their selections. A match occurs when two agents mutually select each other, generating pair-dependent revenue. Choices follow Multinomial Logit (MNL) models. This setting generalizes prior work focused on maximizing the number of matches under submodular demand assumptions, which do not hold in our revenue-maximization context. Our main contribution is the design of polynomial-time approximation algorithms with constant-factor guarantees. In particular, for general pairwise revenues, we develop a randomized algorithm that achieves a $(\frac{1}{2} - \epsilon)$-approximation in expectation for any $\epsilon > 0$. The algorithm is static and provides guarantees under various agent arrival settings, including fixed order, simultaneous processing, and adaptive selection. When revenues are uniform across all pairs involving any given responding-side agent, the guarantee improves to $(1 - \frac{1}{e} - \epsilon)$. In structural settings where responding-side agents share a common revenue-based ranking, we design a simpler adaptive deterministic algorithm achieving a $\frac{1}{2}$-approximation. Our approach leverages novel linear programming relaxations, correlation gap arguments, and structural properties of the revenue functions.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

21 extracted references · 19 canonical work pages

  1. [1]

    Price of correlations in stochastic optimization

    Shipra Agrawal, Yichuan Ding, Amin Saberi, and Yinyu Ye. Price of correlations in stochastic optimization. Operations Research, 60 0 (1): 0 150--162, 2012

    work page 2012

  2. [2]

    Parameterized approximations for the two-sided assortment optimization

    Asrar Ahmed, Milind G Sohoni, and Chaithanya Bandi. Parameterized approximations for the two-sided assortment optimization. Operations Research Letters, 50 0 (4): 0 399--406, 2022

    work page 2022

  3. [3]

    Online Assortment Optimization for Two-Sided Matching Platforms

    Ali Aouad and Daniela Saban. Online Assortment Optimization for Two-Sided Matching Platforms . Management Science, 69 0 (4): 0 2069--2087, 2023

    work page 2023

  4. [4]

    Assortment planning for two-sided sequential matching markets

    Itai Ashlagi, Anilesh K Krishnaswamy, Rahul Makhijani, Daniela Saban, and Kirankumar Shiragur. Assortment planning for two-sided sequential matching markets. Operations Research, 70 0 (5): 0 2784--2803, 2022

    work page 2022

  5. [5]

    Tsitsiklis

    Dimitris Bertsimas and John N. Tsitsiklis. Introduction to linear optimization. In Athena scientific optimization and computation series, 1997

    work page 1997

  6. [6]

    Fair assortment planning

    Qinyi Chen, Negin Golrezaei, and Fransisca Susan. Fair assortment planning. 2025. arXiv preprint arXiv:2208.07341

    arXiv 2025

  7. [7]

    Capacitated assortment optimization: Hardness and approximation

    Antoine Désir, Vineet Goyal, and Jiawei Zhang. Capacitated assortment optimization: Hardness and approximation. 2020. Available at SSRN 2543309

    work page 2020

  8. [8]

    Two-sided Assortment Optimization: Adaptivity Gaps and Approximation Algorithms

    Omar El Housni, Alfredo Torrico, and Ulysse Hennebelle. Two-sided assortment optimization: Adaptivity gaps and approximation algorithms. 2024. arXiv preprint arXiv:2403.08929

    work page Pith review arXiv 2024

Show all 21 references
  1. [9]

    Search frictions and the design of online marketplaces

    Andrey Fradkin. Search frictions and the design of online marketplaces. The Third Conference on Auctions, Market Mechanisms and Their Applications, 2015

    2015

  2. [10]

    Approximate strong separation with application in fractional graph coloring and preemptive scheduling

    Klaus Jansen. Approximate strong separation with application in fractional graph coloring and preemptive scheduling. Theoretical Computer Science, 302 0 (1-3): 0 239--256, 2003

    2003

  3. [11]

    Assortment optimization under multinomial logit model with product costs

    Sumit Kunnumkal, Paat Rusmevichientong, and Huseyin Topaloglu. Assortment optimization under multinomial logit model with product costs. 2010. Available at https://drive.google.com/file/d/1fkGNk_7sPdo24T7WZAE51isRvm4vzjVR

    2010

  4. [12]

    A step towards fairer assortments: Algorithms and welfare implications

    Wentao Lu, Ozge Sahin, and Ruxian Wang. A step towards fairer assortments: Algorithms and welfare implications. 2023. Available at SSRN 4514495

    2023

  5. [13]

    Online Policies for Efficient Volunteer Crowdsourcing

    Vahideh Manshadi and Scott Rodilitz. Online Policies for Efficient Volunteer Crowdsourcing . Management Science, 68 0 (9): 0 6572--6590, 2022

    2022

  6. [14]

    Revenue maximization in choice-based matching markets

    Dan Nissim, Danny Segev, and Alfredo Torrico. Revenue maximization in choice-based matching markets. 2024. Available at SSRN 5016287

    2024

  7. [15]

    Platform design in curated dating markets

    Ignacio Rios and Alfredo Torrico. Platform design in curated dating markets. 2024. arXiv preprint arXiv:2308.02584

    2024

  8. [16]

    Improving match rates in dating markets through assortment optimization

    Ignacio Rios, Daniela Saban, and Fanyin Zheng. Improving match rates in dating markets through assortment optimization. Manufacturing & Service Operations Management, 25 0 (4): 0 1304--1323, 2023

    2023

  9. [17]

    Platform competition in two-sided markets

    Jean-Charles Rochet and Jean Tirole. Platform competition in two-sided markets. Journal of the european economic association, 1 0 (4): 0 990--1029, 2003

    2003

  10. [18]

    Optimal match recommendations in two-sided marketplaces with endogenous prices

    Peng Shi. Optimal match recommendations in two-sided marketplaces with endogenous prices. 2022. Available at SSRN 4037114

    2022

  11. [19]

    Joint stocking and product offer decisions under the multinomial logit model

    Huseyin Topaloglu. Joint stocking and product offer decisions under the multinomial logit model. Production and Operations Management, 22 0 (5): 0 1182--1199, 2013

    2013

  12. [20]

    Multi-agent assortment optimization in sequential matching markets

    Alfredo Torrico, Margarida Carvalho, and Andrea Lodi. Multi-agent assortment optimization in sequential matching markets. 2023. arXiv preprint arXiv:2006.04313

    2023 arXiv

  13. [21]

    Submodular order functions and assortment optimization

    Rajan Udwani. Submodular order functions and assortment optimization. International Conference on Machine Learning, pages 34584--34614, 2023

    2023

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.