Bundle promotions have become increasingly popular among online retailers due to their potential in increasing revenue and profit. They take various forms depending on how retailers offer them to customers (e.g., after a purchase incidence, as advertised deals, or as personalized promotions) and how they are structured (e.g., buy one get one free, spend $100 get 25% off, or buy 3 get $20 off). Understanding how customers respond to these promotions and designing optimal bundle promotions at scale are relevant but challenging problems due to the non-linearity of these promotions. We study a new class of bundle promotions that are not advertised but are offered after customers make their first purchases on a retailer’s website. In our problem, we determine a subset of products, which we refer to as the bundle set. If a customer purchases a product from the bundle set, she is presented with the promotion. After observing the promotion, if she purchases another product from the bundle set, she receives the bundle discount. We introduce a new customer-choice framework and present a mathematical model to determine an optimal bundle set. We show that our problem is NP-hard in general. Hence, we develop pseudo-polynomial and polynomial-time algorithms for its special cases, and use the insights from these special cases to develop a linear-time approximation with a performance guarantee under some assumptions. We test our approximation algorithm on medium to large instances and show that it finds near-optimal solutions. We present insights on when bundle promotions are most useful to the retailers. In particular, we find that connectivity of product graphs (i.e., products i and j are connected in the graph if they are frequently purchased together) and the strength of the connection (i.e., how often they are purchased together) are the main factors that drive the magnitude of the revenue improvement. We also find that allowing for multiple bundle promotion sets, even with the same promotion terms, can strictly increase the expected revenue, and the increase can be arbitrarily large. Last, we study the problem of offering product-customized bundle promotions and design an algorithm that finds an optimal solution for this problem in polynomial time
