Marouane Ibn Brahim

Papers

Journal Articles

• Maximum load assortment optimization: Approximation algorithms and adaptivity gaps
  with Omar El Housni and Danny Segev.
  Operations Research, Vol. 74, No. 1, pp. 408–429, 2026.
  • ★Finalist, INFORMS George Nicholson Student Paper Competition, 2025
  Abstract

  Motivated by modern-day applications such as attended home delivery and preference-based group scheduling, where decision makers wish to steer a large number of customers toward choosing the exact same alternative, we introduce a novel class of assortment optimization problems, referred to as maximum load assortment optimization. In such settings, given a universe of substitutable products, we are facing a stream of customers, each choosing between either selecting a product out of an offered assortment or opting to leave without making a selection. Assuming that these decisions are governed by the multinomial logit choice model, we define the random load of any underlying product as the total number of customers who select it. Our objective is to offer an assortment of products to each customer so that the expected maximum load across all products is maximized.

  We consider both static and dynamic formulations of the maximum load assortment optimization problem. In the static setting, a single offer set is carried throughout the entire process of customer arrivals, whereas in the dynamic setting, the decision maker offers a personalized assortment to each customer, based on the entire information available at that time. As can only be expected, both formulations present a wide range of computational challenges and analytical questions. The main contribution of this paper resides in proposing efficient algorithmic approaches for computing near-optimal static and dynamic assortment policies. In particular, we develop a polynomial time approximation scheme for the static problem formulation. Additionally, we demonstrate that an elegant policy utilizing weight-ordered assortments yields a 1/2 approximation. Concurrently, we prove that such policies are sufficiently strong to provide a 1/4 approximation with respect to the dynamic formulation, establishing a constant factor bound on its adaptivity gap. Finally, we design an adaptive policy whose expected maximum load is within factor 1 - ε of optimal, admitting a quasi-polynomial time implementation.

• Assortment optimization with visibility constraints
  with Théo Barré, Omar El Housni, Andrea Lodi and Danny Segev.
  Mathematical Programming, Vol. 216, No. 1, pp. 177–220, 2026.
  • ★Selected for presentation, M&SOM Supply Chain Management SIG, 2024
  Abstract

  Motivated by applications in e-retail and online advertising, we study the problem of assortment optimization under visibility constraints (APV). Here, we are given a universe of substitutable products and a stream of customers. The objective is to determine the optimal assortment of products to offer to each customer in order to maximize the total expected revenue, subject to exogenously-given visibility constraints, stating that each product should be shown to a minimum number of customers. We assume that customer choices follow a Multinomial Logit model (MNL). We provide a structural characterization of optimal assortments and present a linear time algorithm for solving APV. To this end, we introduce a novel function called the "expanded revenue" of an assortment and establish its supermodularity; our algorithm takes advantage of this structural property. Additionally, we prove that APV can be formulated as a compact linear program.

  Next, we consider APV with cardinality constraints, which limit the maximum number of products that can be included in an assortment. We prove this problem to be strongly NP-hard and not admitting a Fully Polynomial Time Approximation Scheme (FPTAS), even when all products have identical prices. Subsequently, we devise a Polynomial Time Approximation Scheme (PTAS) for APV under cardinality constraints with identical prices. We also examine the revenue loss resulting from the enforcement of visibility constraints, comparing it to the unconstrained problem. To offset this loss, we propose a novel strategy to distribute the loss incurred among the products subject to visibility constraints, charging each vendor an amount proportional to their product's contribution to the revenue loss.

• Runtime analysis for permutation-based evolutionary algorithms.
  with Benjamin Doerr and Yassine Ghannane.
  Algorithmica, Vol. 86, pp. 90–129, 2024.
  • Earlier version: Preliminary version appeared in the Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '22)
  Abstract

  While the theoretical analysis of evolutionary algorithms (EAs) has made significant progress for pseudo-Boolean optimization problems in the last 25 years, only sporadic theoretical results exist on how EAs solve permutation-based problems. To overcome the lack of permutation-based benchmark problems, we propose a general way to transfer the classic pseudo-Boolean benchmarks into benchmarks defined on sets of permutations. We then conduct a rigorous runtime analysis of the permutation-based (1+1) EA proposed by Scharnow et al. (J Math Model Algorithm 3:349-366, 2004) on the analogues of the LeadingOnes and Jump benchmarks. The latter shows that, different from bit-strings, it is not only the Hamming distance that determines how difficult it is to mutate a permutation σ into another one τ, but also the precise cycle structure of στ^-1.

  For this reason, we also regard the more symmetric scramble mutation operator. We observe that it not only leads to simpler proofs, but also reduces the runtime on jump functions with odd jump size by a factor of Θ(n). Finally, we show that a heavy-tailed version of the scramble operator, as in the bit-string case, leads to a speed-up of order m^Θ(m) on jump functions with jump size m. A short empirical analysis confirms these findings, but also reveals that small implementation details like the rate of void mutations can make an important difference.

Working Papers

• AI-Mediation in Retail Markets: Revenue Effects and Assortment Optimization
  with Omar El Housni.
  Abstract

  AI shopping assistants increasingly influence which products consumers consider. We study retail assortment planning under AI mediation, where a retailer chooses a catalog, an AI intermediary forms a customer-facing shortlist, and the customer chooses from that shortlist according to a multinomial logit model. We consider both deterministic mediation, in which the AI follows a fixed segment-specific ranking, and stochastic mediation based on the Plackett–Luce model.

  Empirically, we construct a dataset of product rankings from leading AI models, estimate Plackett–Luce ranking models, and evaluate their predictive performance on held-out assortments. Combining these estimates with synthetic customer preferences, we find that accounting for AI mediation can materially change optimal assortments and revenue. Across the tested capacity configurations, ignoring mediation yields mean revenue losses between 2.52% and 11.37% relative to the PL optimum. A much simpler deterministic plug-in, based only on the ordering of fitted AI utilities, performs substantially better, with mean losses of at most 0.53%.

  Motivated by this performance, we study assortment optimization under deterministic mediation. We characterize its computational complexity and show that, for any fixed number of customer segments, the problem admits a fully polynomial-time approximation scheme.

• When Is Less Choice Enough? Simple Menus in Multi-Item Pricing
  with Omar El Housni.
  Draft available upon request.
  Abstract

  We study the revenue loss from replacing a multi-item price menu by a single item-price offer. Under decentralized pricing, the seller posts item-specific prices and customers choose utility-maximizing items; under centralized pricing, the seller chooses one item and one price. We ask when this restriction preserves revenue, and when it is costly.

  We show that the answer is governed by the geometry of preference heterogeneity. In finite-support markets, centralized revenue can be a factor equal to the number of customer segments below decentralized revenue, and this is tight. The loss is driven by horizontal heterogeneity: different segments prefer different items. By contrast, if all valuation vectors lie on a common nonnegative ray, customers may differ in willingness to pay but agree on relative item values, and centralized and decentralized pricing have the same optimal revenue. With k aligned preference blocks, a centralized offer obtains at least a 1/k fraction of decentralized revenue.

  We prove that this no-gap result is robust to approximate alignment. If a valuation matrix is within entrywise distance ε of the nonnegative rank-one cone, the decentralized revenue advantage is at most O(nε), and this dependence is tight. We also extend the analysis to stochastic environments around a common aligned core and to additive item-level shocks. Overall, centralization can be costly under horizontal heterogeneity, but is revenue-safe when preferences are mostly aligned or vertical.

Work in Progress

• To Disclose or Not to Disclose? Seller Incentives in AI-Mediated Markets
  with Omar Mouchtaki.
• Clearance Assortment Optimization
  with Omar El Housni, Yibo Ji, and Matthieu Palanchon.