{"id":"90f591f2-6573-49c6-b5dd-258dcc4141f6","arxiv_id":"2507.04156","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Under MNL choices, adaptive two-sided assortment with pair-dependent revenues admits a randomized static (1/2 - ε)-approximation, and (1 - 1/e - ε) when each supplier's revenue is uniform; same-order revenues admit a deterministic 1/2 greedy.","lead":"This paper designs polynomial-time algorithms for a platform that sequentially shows customers lists of suppliers and earns revenue only when they both choose each other. Under a logit choice model it proves a (1/2 - ε) revenue guarantee, improved to (1 - 1/e - ε) when a supplier earns the same revenue from every customer.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 3's Ellipsoid proof for solving (LP-II) contains an unsupported inequality (r' ≤ (Dual-II-Aux)) that the polynomial-time claim of Theorem 1 depends on; without a corrected derivation, the main algorithmic result is not established.","rationale":"The reader's weakest assumption (Lemma 6) is a reasonable epistemic concern, but it is less decisive than the internal gap in Lemma 3: Lemma 6 is a published result that applies directly to the MNL revenue function, while Lemma 3's proof is self-contained and contains a step that is not justified in either direction. I therefore make Lemma 3 the primary concern. The rest of the proof of Theorem 1 (correlation gap, Lemma 7, Equation (3)) is coherent conditional on Lemma 3 and Lemma 4. Theorem 2 is a separate contribution that does not use Lemma 3; it relies on Lemma 6 and the interleaved partition argument, which look consistent. Thus the main open condition is the polynomial-time solvability of (LP-II). If a corrected proof of Lemma 3 can be supplied along the lines of Jansen (2003), the central claim stands; otherwise the randomized algorithm has no implementation guarantee. This does not change the reader's CONDITIONAL verdict but sharpens the condition.","tokens_in":30974,"tokens_out":21740,"duration_ms":247548,"concrete_test":"Re-derive Lemma 3 using the proof template in Jansen (2003) or Chen et al. (2025), and check the direction of the inequality between the ellipsoid output r' and (Dual-II-Aux). Concretely: define the approximate feasible region R = {(α,β,γ) : β_j ≥ (1-δ)Sub-Dual_j(γ), α-constraints hold); then show either (i) the returned point is optimal for R intersected with the V_j constraints, or (ii) provide a counterexample to r' ≤ (Dual-II-Aux). Additionally, on a small 2×2 instance with exact enumeration of (Sub-Dual_j), implement Algorithm 3's ellipsoid with the exact oracle, collect V_j, solve (LP-II-Aux) by enumeration, and verify (LP-II-Aux) ≥ (1-δ)(LP-II) for δ = 0.01; if the inequality fails on any instance, Lemma 3 is false as stated.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The most load-bearing point is Lemma 3 (Appendix B.2), the only bridge from the exponentially large (LP-II) to a polynomial-time implementation of the randomized static algorithm. The proof runs the Ellipsoid method on (Dual-II) with a (1-δ)-approximate separation oracle, defines r' as the objective of the point returned, and then asserts r' ≤ (Dual-II-Aux) because the approximate oracle 'expands the feasible region.' This inequality is not established: an infeasible point can have objective on either side of the optimum, and no relaxation of (Dual-II-Aux) is identified whose optimum coincides with r'. The subsequent chain (Dual-II-Aux) ≥ r' ≥ (1-δ)(LP-II) is the entire argument that the restricted primal (LP-II-Aux) is a (1-δ)-approximation. If this inequality is wrong, Lemma 3 is unproved and Theorem 1 loses its polynomial-time solver. By contrast, Lemma 6 is imported from Udwani (2023) in exactly the MNL setting used here, so it is a weaker point; even if it were false, the approximation factor would change, but a missing Lemma 3 removes the algorithm altogether.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":31210,"tokens_out":9395,"duration_ms":114864,"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":[{"comment":"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).","section":"Appendix B.2, Lemma 3, Eq. (7)"},{"comment":"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.","section":"Appendix B.2, Algorithm 3"}],"minor_comments":[{"comment":"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.","section":"Section 3.2, Lemma 6"},{"comment":"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.","section":"Section 4.2, Eq. (4)"},{"comment":"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.","section":"Appendix B.2, Lemma 3 / Algorithm 3"},{"comment":"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.","section":"Algorithm 3"},{"comment":"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.","section":"Section 3.3, Lemma 7"}],"recommendation":"major_revision","confidential_remarks":"The manuscript's central claims are plausible and the non-LP portions are largely coherent, but Lemma 3's proof contains a gap that directly affects the main algorithmic theorem. I do not see this as an irreparable error: standard techniques for approximate separation oracles (e.g., Jansen 2003, Chen et al. 2025) may supply the missing argument. The authors should be asked to provide a corrected proof or a precise citation that covers the exact setting with arbitrary signed costs in (Sub-Dual_j)."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nThe paper does something genuinely new: it moves two-sided assortment optimization from match counts to revenue, and gives constant-factor approximation algorithms for the adaptive setting. The static randomized algorithm (Theorem 1) achieves 1/2−ε for general revenues and 1−1/e−ε when revenue is uniform per supplier, improving the concurrent static guarantee from 1/3 to 1/2−ε. The analysis is not routine: the optimal revenue function is not submodular, so the authors introduce a novel LP relaxation (LP-II) and prove a correlation gap bound via a cost-sharing scheme built on Udwani's submodular-order property. The active-set argument showing (LP-II) and (LP-III) are equivalent is neat, and the same-order greedy (Theorem 2) is a clean primal-dual extension of El Housni et al. with a nice interleaved-partition step. I believe the central approximation results are likely correct.\n\nThe problem is Lemma 3. The proof that (LP-II) is approximately solvable in polynomial time relies on an inequality that is not justified. They run Ellipsoid with a (1−δ)-approximate separation oracle on (Dual-II), get a point with objective r', then assert r' ≤ (Dual-II-Aux) because the approximate oracle 'expands the feasible region.' But an infeasible point for the aux LP can have objective on either side of the aux optimum; no relaxation argument links r' to the aux LP value. The chain (Dual-II-Aux) ≥ r' ≥ (1−δ)(LP-II) is the entire bridge from the exponential LP to a polynomial-time algorithm, so without that fix, Theorem 1 is not established. This is load-bearing, not a cosmetic gap. I'd guess it's fixable—the standard way is to argue the approximate oracle yields a feasible solution to a slightly perturbed dual and then use a perturbation bound—but as written it's a hole.\n\nMinor issues: Algorithm 2's customer-side assortment choice (Step 3) maximizes Σ_j a_j/(1+Σ u_j), which is tractable by sorting a_j/u_j, but the paper never says how to compute it, just asserts polynomial runtime. Lemma 6 is imported from Udwani without proof, but in exactly the right setting, so I'm not worried about that.\n\nOverall: a serious paper with valuable ideas, but it needs a corrected Lemma 3 before the main algorithmic claim is solid. I'd send it to review with the expectation of heavy revision.","headline":"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.","tokens_in":31766,"tokens_out":7678,"would_cite":true,"duration_ms":79169,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W25","90C27","91B26"],"pacs":[],"model":"deepseek-v4-flash","headline":"For any epsilon, a static algorithm captures at least half of the optimal adaptive expected revenue in two-sided assortment.","keywords":["two-sided assortment optimization","revenue maximization","Multinomial Logit (MNL)","adaptive policies","approximation algorithms","correlation gap","LP relaxation","submodular order"],"falsifier":"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.","tokens_in":30747,"feed_emoji":"📈","tokens_out":6560,"duration_ms":71476,"temperature":0.7,"pith_summary":"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.","feed_headline":"A static policy yields half the optimal adaptive revenue","feed_subtitle":"Randomized algorithm achieves (1/2-ε) approximation under MNL choices, with (1-1/e) when supplier revenues are uniform.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies Lemma 9 establishing the submodular-order property of the optimal MNL revenue function, the structural fact behind both the correlation-gap bound and the greedy interleaved-partition argument.","marker":"Udwani (2023)"},{"why":"Provides Theorem 4 bounding correlation gaps by $e/(e-1)$ for monotone submodular functions and by $2\\beta$ for functions admitting a $\\beta$-cost-sharing scheme, the template for Lemma 4.","marker":"Agrawal et al. (2012)"},{"why":"Gives the FPTAS for assortment optimization with arbitrary fixed costs used as the approximate separation oracle inside the Ellipsoid method to solve (LP-II).","marker":"Chen et al. (2025)"},{"why":"Provides the original one-sided adaptive model, the LP relaxation adapted here, and the primal-dual greedy analysis for the matching special case that the same-order greedy proof extends.","marker":"El Housni et al. (2024)"},{"why":"Concurrent static customized-model work whose $1/3$-approximation is the baseline that the static algorithm improves to $(\\frac{1}{2}-\\epsilon)$.","marker":"Nissim et al. (2024)"},{"why":"Founds the static one-sided two-sided assortment model whose LP-rounding approach this line of work builds on.","marker":"Ashlagi et al. (2022)"},{"why":"Shows assortment optimization with fixed costs is NP-complete and gives early approximation results, cited for the hardness of the sub-dual problem.","marker":"Kunnumkal et al. (2010)"},{"why":"Supplies the MNL polyhedron representation used in Lemma 7 to construct an assortment distribution that matches the desired marginal choice probabilities.","marker":"Topaloglu (2013)"}],"fun_headline_variants":["Static policy matches adaptive revenue within factor 2","Half the adaptive revenue is achieved by a static policy","Constant-factor revenue approximation is possible for two-sided matching","Adaptive edge is small because static policy hits half of optimal revenue"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Static policy matches adaptive revenue within factor 2","Half the adaptive revenue is achieved by a static policy","Constant-factor revenue approximation is possible for two-sided matching","Adaptive edge is small because static policy hits half of optimal revenue"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000787,"raw_usage":{"total_tokens":3522,"prompt_tokens":1046,"completion_tokens":2476,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":662,"completion_tokens_details":{"reasoning_tokens":2411}},"tokens_in":662,"tokens_out":2476,"duration_ms":22685,"temperature":1.0,"reasoning_tokens":2411,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T19:56:45.313622+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Submodular order functions and assortment optimization","cited_arxiv_id":null,"evidence_quote":"Supplies Lemma 9 establishing the submodular-order property of the optimal MNL revenue function, the structural fact behind both the correlation-gap bound and the greedy interleaved-partition argument."},{"cited_title":"Price of correlations in stochastic optimization","cited_arxiv_id":null,"evidence_quote":"Provides Theorem 4 bounding correlation gaps by $e/(e-1)$ for monotone submodular functions and by $2\\beta$ for functions admitting a $\\beta$-cost-sharing scheme, the template for Lemma 4."},{"cited_title":"Two-sided Assortment Optimization: Adaptivity Gaps and Approximation Algorithms","cited_arxiv_id":"2403.08929","evidence_quote":"Provides the original one-sided adaptive model, the LP relaxation adapted here, and the primal-dual greedy analysis for the matching special case that the same-order greedy proof extends."},{"cited_title":"Revenue maximization in choice-based matching markets","cited_arxiv_id":null,"evidence_quote":"Concurrent static customized-model work whose $1/3$-approximation is the baseline that the static algorithm improves to $(\\frac{1}{2}-\\epsilon)$."},{"cited_title":"Assortment planning for two-sided sequential matching markets","cited_arxiv_id":null,"evidence_quote":"Founds the static one-sided two-sided assortment model whose LP-rounding approach this line of work builds on."},{"cited_title":"Assortment optimization under multinomial logit model with product costs","cited_arxiv_id":null,"evidence_quote":"Shows assortment optimization with fixed costs is NP-complete and gives early approximation results, cited for the hardness of the sub-dual problem."},{"cited_title":"Joint stocking and product offer decisions under the multinomial logit model","cited_arxiv_id":null,"evidence_quote":"Supplies the MNL polyhedron representation used in Lemma 7 to construct an assortment distribution that matches the desired marginal choice probabilities."}],"review_version":1}