Karthik Natarajan

Given data on the choices made by consumers for different offer sets, a key challenge is to develop parsimonious models that describe and predict consumer choice behavior while being amenable to prescriptive tasks, such as pricing and assortment optimization. The marginal distribution model (MDM) is one such model, which requires only the specification of marginal distributions of the random utilities. This paper aims to establish necessary and sufficient conditions for given choice data to be consistent with the MDM hypothesis inspired by the usefulness of similar characterizations for the random utility model (RUM). This endeavor leads to an exact characterization of the set of choice probabilities that the MDM can represent. Verifying the consistency of choice data with this characterization is equivalent to solving a polynomial-sized linear program. Because the analogous verification task for RUM is computationally intractable and neither of these models subsume the other, MDM is helpful in striking a balance between tractability and representational power. The characterization is then used with robust optimization for making data-driven sales and revenue predictions for new unseen assortments. When the choice data lack consistency with the MDM hypothesis, finding the best-fitting MDM choice probabilities reduces to solving a mixed-integer convex program. Numerical results using real-world data and synthetic data demonstrate that MDM exhibits competitive representational power and prediction performance compared with RUM and parametric models while being significantly faster in computation than RUM. This paper was accepted by Omar Besbes, revenue management and pricing department. Funding: This work was supported by the Singapore Ministry of Education Academic Research Fund [Grants T2EP20223-0008 and T2MOE1906]. X. Li was supported in part by the Singapore Ministry of Education Academic Research Fund Tier 1 [Grants 23-0619-P0001 and 24-0500-A0001]. The research of K. Murthy was supported by the Singapore Ministry of Education Academic Research Fund [Grants MOE2019-T2-2-163 and MOE-T2EP20223-0017]. The research of K. Natarajan was partly supported by the Singapore Ministry of Education Academic Research Fund Tier 2 [Grant MOE2019-T2-2-138]. Supplemental Material: The online appendix and data files are available at https://doi.org/10.1287/mnsc.2023.02287 .

Given data on the choices made by consumers for different offer sets, a key challenge is to develop parsimonious models that describe and predict consumer choice behavior while being amenable to prescriptive tasks such as pricing and assortment optimization. The marginal distribution model (MDM) is one such model, that requires only the specification of marginal distributions of the random utilities. This paper aims to establish necessary and sufficient conditions for given choice data to be consistent with the MDM hypothesis, inspired by the utility of similar characterizations for the random utility model (RUM). This endeavor leads to an exact characterization of the set of choice probabilities that the MDM can represent. Verifying the consistency of choice data with this characterization is equivalent to solving a polynomial-sized linear program. Since the analogous verification task for RUM is computationally intractable and neither of these models subsumes the other, MDM is helpful in striking a balance between tractability and representational power. The characterization is convenient to be used with robust optimization for making data-driven sales and revenue predictions for new unseen assortments. When the choice data lacks consistency with the MDM hypothesis, finding the best-fitting MDM choice probabilities reduces to solving a mixed integer convex program. The results extend naturally to the case where the alternatives can be grouped based on the similarity of the marginal distributions of the utilities. Numerical experiments show that MDM provides better representational power and prediction accuracy than multinominal logit and significantly better computational performance than RUM.

Given data on choices made by consumers for different assortments, a key challenge is to develop parsimonious models that describe and predict consumer choice behavior. One such choice model is the marginal distribution model (MDM), which requires only the specification of the marginal distributions of the random utilities of the alternatives to explain choice data.

While useful probability bounds for [Formula: see text] pairwise independent Bernoulli random variables adding up to at least an integer [Formula: see text] have been proposed in the literature, none of these bounds are tight in general. In this paper, we provide several results in this direction. First, when [Formula: see text], the tightest upper bound on the probability of the union of [Formula: see text] pairwise independent events is provided in closed-form for any input marginal probability vector [Formula: see text]. To prove the result, we show the existence of a positively correlated Bernoulli random vector with transformed bivariate probabilities, which is of independent interest. Building on this, we show that the ratio of the Boole union bound to the tight pairwise independent bound is upper bounded by [Formula: see text] and that the ratio is attained. Applications of the result in correlation gap analysis and distributionally robust bottleneck optimization are discussed. The result is extended to find the tightest lower bound on the probability of the intersection of [Formula: see text] pairwise independent events. Second, for any [Formula: see text] and input marginal probability vector [Formula: see text], new upper bounds are derived by exploiting ordering of probabilities. Numerical examples are provided to illustrate when the bounds provide improvement over existing bounds. Lastly, we identify specific instances when the existing and the new bounds are tight, for example, with identical marginal probabilities.

In this paper, we compute the tightest possible bounds on the probability that the optimal value of a combinatorial optimization problem in maximization form with a random objective exceeds a given number, assuming only knowledge of the marginal distributions of the objective coefficient vector. The bounds are “extremal' since they are valid across all joint distributions with the given marginals. We analyze the complexity of computing the bounds, assuming discrete marginals, and identify instances when the bounds are computable in polynomial time. For compact 0/1 V-polytopes, we show that the tightest upper bound is weakly NP-hard to compute by providing a pseudopolynomial time algorithm. On the other hand, the tightest lower bound is shown to be strongly NP-hard to compute for compact 0/1 V-polytopes by restricting our attention to Bernoulli random variables. For compact 0/1 H-polytopes, for the special case of PERT networks arising in project management, we show that the tightest upper bound is weakly NP-hard to compute by providing a pseudopolynomial time algorithm. The results in the paper complement existing results in the literature for computing the probability with independent random variables.