Dynamic pricing with (extra) seat reservations under the nested logit model

Barz, Christiane; Gönsch, Jochen; Rauhaus, Davina; He, Siqi Article — Published Version Dynamic pricing with (extra) seat reservations under the nested logit model OR Spectrum Suggested Citation: Barz, Christiane; Gönsch, Jochen; Rauhaus, Davina; He, Siqi (2025) : Dynamic pricing with (extra) seat reservations under the nested logit model, OR Spectrum, ISSN 1436-6304, Springer Berlin Heidelberg, Berlin/Heidelberg, Vol. 47, Iss. 4, pp. 1133-1179, https://doi.org/10.1007/s00291-025-00817-y This Version is available at: https://hdl.handle.net/10419/333239 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. http://creativecommons.org/licenses/by/4.0/ Vol.:(0123456789) OR Spectrum (2025) 47:1133–1179 https://doi.org/10.1007/s00291-025-00817-y ORIGINAL ARTICLE Dynamic pricing with(extra) seat reservations underthenested logit model ChristianeBarz1 · JochenGönsch2· DavinaRauhaus2· SiqiHe1 Received: 16 April 2024 / Accepted: 15 April 2025 / Published online: 27 May 2025 © The Author(s) 2025 Abstract We suggest a dynamic pricing model for selling extra seats - seat reservations for unoccupied seats that provide additional space alongside regular reservations. Such extra space tickets share the resources of the main product and leverage the unused capacity, offering significant revenue-generation opportunities when coaches, trains, or airplanes frequently depart with empty seats. We formulate a Markov decision process (MDP) representing the ticket sales problem of a transportation company that sells tickets for a single leg in a single compartment, offering three options: (1) without seat reservation, (2) with seat reservation, and (3) with seat reservation and extra space. In this framework, seat reservations are integrated into the state space, making the problem a special case of the network dynamic pricing problem. To solve this problem, we draw from established network dynamic pricing methods to derive upper bounds and policies for pricing the three ticket types. These approaches include deterministic approximation, approximate linear programming, and a decomposition method based on seat values provided by the deterministic approximation. Under the nested logit demand model, we demonstrate that the ALP subproblem features a convex objective function in actions and linearity in the state components, enabling efficient solutions. An extensive numerical study highlights the efficiency of the decomposition approach, which delivers a superior revenueto-runtime trade-off compared to more complex methods. This makes it a practical choice for real-world applications. Additionally, our results quantify the significant revenue potential of offering extra seats, particularly in low-demand scenarios. Keywords Revenue management· Extra seats· Empty seats· Approximate dynamic programming· Dynamic pricing· Ancillary products· Nested logit· Customer choice Extended author information available on the last page of the article 1134 C.Barz et al. 1 Introduction In the dynamic landscape of revenue management (RM), innovative practices often emerge in industry applications. This paper presents a modeling approach to address the common practice of selling extra, unoccupied seats adjacent to a customer’s reserved seat. Companies like FlixBus, a leading global long-distance bus company and parent of the US Greyhound, with over 60 million passengers in 2022 (Flix 2023), have adopted this practice. They offer passengers the “Travel neighbour-free” option to reserve an adjacent seat for their exclusive use, thus ensuring extra space and comfort during their journeys (see Fig.1). Given the low average occupancy rates in some transportation sectors using revenue management, this approach seems to have significant potential. For example, the average coach occupancy rate in France ranged from 29.8 percent to 53.8 percent between 2015 and 2017, according to Statista (2022). This issue was further exacerbated during the COVID-19 pandemic, which led to a dramatic decline in travel demand (Dhital etal. 2022). And on the demand-side, Mumbower etal. (2015) shows what seasoned travelers know instinctively: customers value extra space for long-haul travel and are willing to pay for it under certain circumstances. But extra seat reservation has seen widespread implementation in the aviation industry as well, with examples like the “Neighbour-Free” seating program introduced by Qantas Airlines and Eurowings or “Extra Seats” by Air China, All Nippon Airways, EL AL, and Turkish Airlines. These programs allow passengers to ensure an empty middle seat for more convenience for a small fee, compared to the whole ticket price. This approach enables operators to capitalize on the sale of seats that might otherwise remain unsold, thereby increasing revenue. In addition, offering such an additional option can expand the market and attract more customers, as people are inclined to choose travel options that prioritize comfort. The market demand for additional space has become even more pronounced during the COVID-19 pandemic, where social distancing was considered a high Fig. 1 Example from booking process (FlixBus website, 28th October 2024) 1135 Dynamic pricing with(extra) seat reservations underthenested… priority. However, to the best of our knowledge, no research exists on when to offer and how to price these extra seats. Despite these prominent implementations in industry practice, academia has remained relatively silent on optimal strategies for offering and pricing extra seats. Instead, industry practitioners seem to often rely on basic rules of thumb. Our research aims to bridge this gap by leveraging state-of-the-art RM techniques to inform industry practices and shed light on optimal pricing strategies in this complex ecosystem. In this paper, we use the example of a bus company like FlixBus to illustrate our ideas. More specifically, we consider the following optimization problem of an expected revenue-maximizing firm that operates a coach on a single leg. Seats are specific, i.e., customers may have preferences for specific seats (e.g., first row, left window seat). As usual in dynamic pricing settings, the company’s decision is to adjust its products’ prices throughout the finite selling horizon in order to maximize expected revenue. Customers arrive sequentially, observe the prices of all products, and then stochastically choose a product type or leave without a purchase. In particular, there are three types of products. (1) Tickets without seat reservation, where customers pick a free seat when boarding or are randomly assigned one at this time. (2) Tickets with a seat reservation, where customers choose a specific seat when booking. We subsequently refer to this as (single-) seat reservation. (3) Tickets with an extra seat reservation, where customers choose a specific pair of seats. Only after the product type is chosen, the customer selects a specific seat or a pair of neighboring seats. Since the nested logit (NL) model naturally describes the hierarchy in the purchase decisions regarding product type and specific seat in case of a reservation, we assume this model throughout. On a more technical level, the NL is a tractable model that captures different pairwise similarities as products are arranged in nests and two products sharing a common nest are more similar than two products in different nests. This is exactly what we have here: for example, for most customers, a reservation for a fourth row seat is very similar to a reservation for a fifth row set, but different from a ticket without reservation. In our numerical study, we also consider preferences for different seat types, e.g. aisle or window seat. However, the general ideas introduced here carry over to other choice models as well. Our contributions can be summarized as follows: • Novel formulation as network revenue management problem: We are the first, to our knowledge, to frame the problem of maximizing expected revenue from selling tickets with and without reservations via dynamic pricing as a network revenue management problem. This novel formulation allows us to address ticket sales in three contexts: without reservations, with single-seat reservations, and with extra-seat reservations. • Application of established solution techniques to obtain upper bounds and pricing heuristics: We apply three established approaches to determine upper bounds on expected revenue and suggest related pricing heuristics for the network revenue management problem: 1136 C.Barz et al. • A static deterministic pricing problem (DPP), providing a straightforward and computationally efficient path towards an upper bound and bid prices that can be used to determine a static pricing policy. • A semi-infinite linear program inspired by Ke et al. (2019), based on an approximate linear programming (ALP) approach. We demonstrate that, under a NL choice model, the row-generation subproblem can be reformulated as a tractable optimization problem, where the objective function is convex in the action and linear in the components of the state. Its solution can also be used to construct a dynamic pricing heuristic. • A decomposition heuristic based on bid-prices obtained by the DPP or ALP approach, solving several one-dimensional Bellman equations, yielding tighter bounds and typically better pricing policies than their counterparts. • Enhanced decomposition heuristic: Exploiting the unique structure of our problem, we introduce a modified decomposition heuristic that focuses on decomposing only the component representing the total number of remaining seats. This targeted decomposition reduces complexity while maintaining solution quality. • Computational comparisons of bounds and pricing policies: We conduct a comprehensive numerical study to compare the performance and runtime of the upper bounds and several pricing policies, including a simulation-based approximate dynamic programming (ADP) policy. The results reveal that our enhanced decomposition heuristic seems to provide the best trade-off between between tightness and computational effort both with respect to the upper bound as well as the resulting pricing. • Sensitivity analysis: Lastly, we investigate (1) if our results depend on the attractiveness of extra seat reservations and (2) when selling extra space is beneficial from a business perspective. The paper is structured as follows: Sect.2 reviews the related literature. In Sect.3, we present the dynamic programming model and the customer choice model in detail. Since the model suffers from the curse of dimensionality even for single-leg problems, Sect.4introduces three upper bound problems. We introduce dynamic pricing policies based on these upper bound problems in Sect.5. Section6 reports numerical results and Sect.7 concludes the paper. 2 Literature In classical dynamic pricing models, a manager owns a finite inventory of resources that perish after a finite selling horizon. The products offered are composed of these resources. Customers arrive stochastically and sequentially over time. Time is often discretized into a set of time periods such that there is at most one arrival within a given time period. Given the prices, customers can decide to buy one of the products offered or leave without purchasing anything. The objective is to find a set of prices for the products for each time period and inventory state such that the expected 1137 Dynamic pricing with(extra) seat reservations underthenested… revenue is maximized. Dynamic pricing is widely applied across a variety of sectors, includinghospitality, retailing, airtravel, andpublic transportation. The dynamic pricing problem was first described by Gallego and van Ryzin (1994), who address a scenario with one product consuming a single resource over a finite continuous-time selling horizon. Demand is stochastic and the demand rate is time-invariant and depends only on price, which is a continuous variable. They reformulate it as an intensity/demand rate control problem and obtain an exact solution when the selling probability is an exponential function of price. Building on this, Gallego and van Ryzin (1997) extend the model to multiple products consuming a set of resources. Since the computational complexity prohibitively increases in the number of products and resources, they propose two solution heuristics. For excellent comprehensive reviews on dynamic pricing, we refer to the review papers of den Boer (2015) and Chen and Chen (2015), as well as the books by Talluri and Van Ryzin (2004) and Gallego and Topaloglu (2019). At first glance, extra seat reservations may also seem related to group bookings, see, e.g., Haensel and Koole (2013). While both scenarios involve the simultaneous booking of two or more seats, there are important differences in customer choices and willingness-to-pay considerations. In our setting, a customer can freely choose whether to reserve one or two seats (i.e., an extra seat). By contrast, a group of two will usually either purchase two seats or none. Moreover, for a group of two, the willingness to pay for both seats is often modeled as twice the willingness to pay for a single seat for a single customer. In contrast, for extra seat reservations, the willingness to pay for the extra seat is typically much lower than the willingness to pay for the primary seat. Since we do not consider group bookings in this paper, we do not discuss the literature in this area in detail. In this paper, we dynamically price regular tickets, seat reservations and extra seats. Since extra seats can be viewed as ancillary products that share resources with the core product, we discuss literature about pricing of ancillary products in Sect.2.1. On the other hand, regular tickets without seat reservations could be viewed as selling flexible products because the seat that can fulfill this request can be assigned later. Therefore, we discuss literature discussing pricing of flexible products in Sect.2.2. Section2.3 outlines the nested logit model and why it is naturally suited to model seat reservation choice behavior. Since our model formulation suffers from the well-known curse of dimensionality, we apply methods from approximate dynamic programming (ADP) to obtain upper bounds and heuristics. We discuss literature on dynamic pricing models solved via approximate linear programming (ALP) and decomposition methods in Sect.2.4. 2.1 Pricing ofancillary products Seat reservations and extra adjacent seat reservations are often categorized as ancillary products in RM, alongside services such as in-flight meals and checked baggage. A simple ticket without any seat reservation, on the other hand, is categorized as the primary product. For a comprehensive review of ancillary products, we recommend Ozmec-Ban etal. (2022). 1138 C.Barz et al. However, compared to in-flight meals and checked baggage, seat reservations are characterized by the fact that they have a direct impact on seat capacity. Existing studies on dynamic pricing and ancillary products have primarily focused on ancillary products that do not consume the capacity of the primary product. For instance, Wilson (2016) discusses a fluid model for pricing a primary product and multiple ancillary products which refer mostly to warranty, checked baggage, etc., with linear expected demand functions. Similarly, Ødegaard and Wilson (2016) present a dynamic program considering the pricing of a primary product (specifically a flight) along with checked baggage fees as an ancillary product. Demand is stochastic and varies over time. Building on the model of Wilson (2016); Zhao etal. (2021) incorporates a time-heterogeneous linear demand function into the fluid model. As these studies focus on ancillary products that do not have the same capacity constraints as the primary product, they have less impact on pricing decisions. To the best of our knowledge, there is a paucity of literature on dynamic pricing of ancillary products that consume capacity, despite the widespread implementation of such a business idea in industry. This gap highlights the need for further research in this specific area. 2.2 Flexible products A flexible product is a menu of two or more alternatives which the seller chooses from after the sale. The concept was introduced to network RM by Gallego etal. (2004) and Gallego and Phillips (2004). Gönsch (2020) provides a detailed introduction to the associated supply-side flexibility as well as modeling approaches and reviews the work of different research communities. This stream of research is relevant because, technically, a ticket without a reservation is a flexible product: It allows the seller to allocate a designated seat at a later stage. Accordingly, the dynamic program presented in Sect.3.3 technically describes a special case of a RM problem with a flexible product that comprises a lot of alternatives (all seats). Moreover, Koch etal. (2017) have shown that every setting with arbitrary flexible products can be modeled as an equivalent (albeit often very large) standard network revenue management setting (without flexible products). For our setting, this transformation is easy and intuitive, and we directly state the problem as a network revenue management problem in Sect.3.3. The literature on dynamic pricing with flexible products is scarce. Sierag (2017) extends the multi-product dynamic pricing formulation of Gallego and van Ryzin (1997) to flexible products with arbitrary regular demand functions. However, he focuses on a deterministic model that serves as an upper bound on the DP. Analogous to the well-known deterministic pricing formulation as stated e.g. in Talluri and Van Ryzin (2004), the stochastic demand is replaced by its expected values and the integrality constraints are relaxed. The resulting solution is then used in two heuristics, a make-to-stock heuristic and a make-to-order heuristic. Our nested logit demand model fulfills the required regularity conditions stated by Sierag (2017). But since his deterministic formulation is equivalent to the well-known deterministic 1139 Dynamic pricing with(extra) seat reservations underthenested… pricing problem for network revenue management in our case, we do not discuss details of his problem formulation in the following. We are only aware of one more paper dynamically pricing flexible products: Ceryan etal. (2018) are further away from our setting as they consider replenishment decisions and upgrades in a multi-period retail framework. They model customer choice through valuations and propose a two-stage MDP as well as a heuristic to solve the problem. They also include an upgrade fee in their model to monetize upgrades. 2.3 The nested logit model indynamic pricing We assume that customer choice can be modeled by a nested logit model. The NL model is an extension of the multinomial logit model (MNL). The MNL, originally proposed by Luce (1959), has become a well-established choice model in RM over the past 40 years, see, e.g., Strauss etal. (2018) for an overview. It is a simple and flexible choice model with origins in marketing and RM (e.g., Anderson and Xie (2012)). Both NL and MNL models belong to the class of random utility models. These models assume that a given customer n possesses a random utility, denoted as un,j , for each product j. Among the set of available alternatives, he chooses the one with the highest utility. The MNL model assumes that this utility consists of a deterministic part vn,j and an i.i.d. Gumbel-distributed noise 𝜖n,j . In the dynamic pricing setting, vn,j obviously depends on the price for product j, besides other product characteristics. The MNL model has been widely adopted in dynamic pricing models, however, it suffers from the well-known independence from irrelevant alternatives (IIA) property. The IIA assumption states that the ratio of the probabilities of two alternatives does not depend on any other alternative, but solely on the utilities of these two alternatives. In our setting, IIA implies that if the number of free seats (that are available for singleseat reservations) doubles, then the probability that a given customer chooses a singleseat reservation doubles as well. However, this is not intuitive. For most customers, the number of available seats only marginally increases the probability that any reservation is bought - especially if many seats are still available. To overcome IIA’s limitation, McFadden (1973) introduced the NL model. The NL allows related alternatives to be grouped in the same nest and their Gumbeldistributed noises are no longer independent. Under the NL, customers first choose a nest from several given nests and then proceed to choose a product within the chosen nest, making each choice along the line according to the MNL. This structure alleviates the IIA concern associated with MNL. Li and Huh (2011) apply NL to dynamic pricing and demonstrate that the total profit function exhibits concavity. This property holds significant implications for our work, contributing to the effectiveness of our proposed heuristic approach. Gallego and Wang (2014) use NL in an oligopolistic multi-product dynamic pricing setting. They simplify the problem twice by showing that the so-called adjusted markup is constant for all products and that the adjusted nest-level markup is nest-invariant. Li etal. (2015) extend the paper of Gallego and Wang (2014) by generalizing the nesting structure to more than two stages. Davis etal. (2017) transform a static 1140 C.Barz et al. pricing problem with quality consistency constraints into a linear program, but consider the decision stages as part of a dynamic program in some settings. 2.4 ADP Methods indynamic pricing Since our model can be viewed as a network problem with c+1 resources, where resources 1, …,c represent individual seats with an initial capacity of 1 and the last resource represents the total number of tickets that can be bought, our work can also be viewed as a special case of a network dynamic pricing problem with nested logit demand. Common heuristic approaches to solve network RM problems include both ALP as well as decomposition-based approaches. The basic idea in ALP is to reformulate the dynamic program as an equivalent linear program (LP). In this LP, each decision alternative leads to a constraint and each state corresponds to a decision variable, which makes the LP prohibitively large to solve. Thus, a standard approach is to replace the decision variables by an approximation consisting of affine (basis) functions. It then uses row generation or reductions to determine the parameters of this affine approximation. The objective value of this approximated linear program then provides an upper bound on the optimal expected revenue. The optimal solution, i.e. the parameters often have intuitive interpretations and can be used to construct policies for the control problem. The formal introduction of ALP into network RM was pioneered by Adelman (2007), who applies it to solve capacity control problems. Ke etal. (2019) extended his framework to the dynamic pricing problem described in Gallego and van Ryzin (1997), where time is discrete and pricing variables are continuous. They approximate the decision variables using affine functions, demonstrating that for an affine approximation under a linear demand function, ALP can be effectively used with column generation. Even thoughKe etal. (2019)do not analyze the sale of extra adjactent seats, their work is closely connected to our work since they discuss a network dynamic pricing problem with general demand structure. They develop a tighter upper bound for this network pricing problem and suggest efficient solution methods in the case of linear demand. In addition, they suggest a decomposition that provides an upper bound. Other work applying decomposition methods to revenue management problems includes (Liu and van Ryzin 2008) and Zhang (2011). 3 The (extra) seat reservation andpricing model In this section, we present the mathematical model used to investigate dynamic pricing of both tickets and (extra) seat reservations. In particular, Sect.3.1 introduces the setting and the notation. While we will always use bus terminology, our proposed problem formulation is quite general and can be used for single-leg train rides or flights without changes. Section3.2 then discusses the nested logit model used to 1147 Dynamic pricing with(extra) seat reservations underthenested… and wt−1≤wt for all t. In addition, they prove that (AFF) provides a bound that is at least as tight as (DPP), i.e. V∗≤VAFF ≤VDPP . Ke etal. (2019) suggest to solve (AFF) via row generation. However, solving the row generation algorithm for (AFF) can be computationally expensive. This is because the algorithm iteratively finds the largest discrepancy between the leftand right-hand sides of the constraints across all state-action pairs and time periods.. Using the nested logit model, however, subproblems are relatively easy to solve since for fixed state (x,y) the subproblem is convex. A mathematical formulation of that subproblem and proof of the following theorem can be found in Appendix B.1. Theorem1 For a given state (x,y)∈S , the subproblem of a row-generation algorithm solving (AFF) for a given time period t is a convex optimization problem in p . Since the subproblem is a convex problem in p and linear in all state variables xi and y, the subproblem can be solved using a straightforward branch-and-bound algorithm. 4.3 A Decomposition The value function approximation with vi representing exogenously given time-independent values of reserved seats i=1, …,c represents a dynamic programming decomposition. Fixing  V0 (y)= 0 for all y and plugging this into the Bellman equations, we obtain where we used that P(1,y)⊇P(x,y) for all x∈{0, 1}c . The iterative solution of (DPD-BE) via backward induction only implies the solution of convex optimization problems for each time period and seat occupancy level y. The result also provides an upper bound that is tighter than the bound provided by the deterministic pricing problem (DPP). Theorem2 Independent of the choice of vi , V∗≤VDPD . Denoting the solution of (DPD-BE) with values vi given by the optimal solution of (DPP) by VDPD* =  VT(c) , we further have (APPROX-DPD) V t(x,y)≈  Vt(y)+ c ∑ i=1 vixi , (DPD-BE)  V t(y)= max p∈P(1,y) { p0  Vt−1(y)+p1(r1(p)+  Vt−1(y−1 )) +∑ i p2,i(r2,i(p)+  Vt−1(y−1)−vi) + ∑ i p3,i(r3,i(p)+  Vt−1(y−2)−vi−vi∗) } , V∗≤VDPD* ≤VDPP. 1148 C.Barz et al. The proof of Theorem2, highlighting the connection to Proposition 5 in Ke etal. (2019), can be found in Appendix B.2. Note that in typical network pricing problems, it is unclear which component of the state space should be modeled by a value function and which ones should be assumed linear. In our special case, however, the seat reservations only have values 0 and 1, so a linear approximation is not restrictive. What is restrictive is that we do not allow the value of a seat reservation for seat i, vi , to depend on time. We discuss a time-dependent version in Appendix C. 5 Pricing policies The optimal prices in state (x,y) at time t are given by the argument r maximizing the right-hand side of the Bellman equation (BE). Substituting p0=1−p1−p2−p3 and applying Lemma 1, we can reformulate the Bellman equations maximizing over the purchasing probabilities p and the optimal probabilities in state (x,y) at time t are given by The above optimization problem is convex in p as shown in Theorem1. In addition, the first term, Vt−1(x,y) is a constant that does not change in p and can hence be dropped when finding the arg max . In a final step, we translate p∗ t(x,y) into optimal prices applying Lemma 1 again. However, this approach relies on determining all values of the value function V, which is computationally infeasible due to the large state space, even for moderate (3) V t(x,y)=Vt−1(x,y)+ max p∈P(x,y) { p1 ( r1(p)− [ Vt−1(x,y)−Vt−1(x,y−1)) ]) +∑ i p2,i(r2,i(p)−[Vt−1(x,y)−Vt−1(x−ei,y−1)]) + ∑ i p3,i ( r3,i(p)− [ Vt−1(x,y)−Vt−1(x−ei−ei∗,y−2) ])} (BE-RHS) p ∗ t(x,y) =argmax p∈P(x,y)�p1 ⎛ ⎜⎜⎜⎝ r1(p)−�Vt−1(x,y)) − Vt−1(x,y−1)� ⏟⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏟⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏟ Value of 1 seat ⎞ ⎟⎟⎟⎠ +� i p2,i⎛⎜⎜⎜⎝ r2,i(p)−�Vt−1(x,y)−Vt−1(x−ei,y−1)� ⏟⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏟⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏟ Value of 1 seat and a reservation for seat i ⎞⎟⎟⎟⎠ +� i p3,i⎛ ⎜⎜⎜⎝ r3,i(p)− � Vt−1(x,y)−Vt−1(x−ei−ei∗,y−2) � ⏟⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏟⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏟ Value of 2 seats and reservations for seats iand i ∗ ⎞ ⎟⎟⎟⎠ � . 1149 Dynamic pricing with(extra) seat reservations underthenested… capacity levels. This is why, in the following, we discuss various pricing heuristics for our pricing problem with reservations and extra seats. The core idea of these policies is to estimate the true value functions above by the approximations provided by our upper bound problems. 5.1 A policy based onthedeterministic pricing problem Let w∗ be the (time-independent) dual value of the capacity constraint for y in (DPP) and the values v∗ i be the corresponding dual values of the capacity constraints for the xi s in (DPP). Using these, we approximate the value of each seat by w∗ and the value of a reservation for seat i by v∗ i . This is equivalent to assuming Vt (x,y)≈ ∑i x i v ∗ i +w ∗y and replacing (BE-RHS) by We will refer to this static pricing policy as (Policy-DPP). The price provided by this policy only depends on the current state solely to determine the set of feasible actions. 5.2 A policy based ontheaffine approximation Similarly, a straightforward approach to approximating (BE-RHS) is to replace all occurrences of the value function by the affine approximation (APPROX-AFF) using parameters given by the optimal solution of (AFF). Denoting the optimal values of vit s and wt s in (AFF) as v∗ i,t s and w∗ t s, will refer to the dynamic pricing policy solving for given state (x,y) at time t as (Policy-AFF) in the following. This pricing policy is now time-dependent but still only depends on the current state through the definition of feasible actions. 5.3 A policy based ondecompositions Similarly, replacing the value functions in (BE-RHS) by the decomposition (APPROX-DPD), we obtain (Policy-DPP) p ∗ t(x,y) =argmax p∈P(x,y) { p1 ( r1(p)−w∗ ) + ∑ i p2,i ( r2,i(p)−(w∗+v∗ i) ) + ∑ i p3,i ( r3,i(p)−(2w∗+v∗ i+v∗ i∗) )} . (Policy-AFF) argmax p∈P(x,y) { p1 ( r1(p)−w∗ t−1 ) + ∑ i p2,i ( r2,i(p)−(w∗ t−1+v∗ i,t) ) + ∑ i p3,i ( r3,i(p)−(2w∗ t−1+v∗ i,t+v∗ i∗,t) )} 1150 C.Barz et al. Using value functions  Vt−1( y ) provided by (DPD-BE) and vi given by the deterministic pricing problem (DPP), we obtain a pricing policy that now explicitly depends on the current state and time until departure. This pricing policy is referred to as (Policy-DPD). 6 Numerical study In following numerical study, we first (Sect.6.1) compare the quality of the upper bounds we suggested in Sect.4. In Sect.6.2, we then analyze the performance of the pricing policies presented in Sect.5. To investigate the reasons for performance differences, we analyze the prices set in Sect.6.3. Then, we look at how the results depend on the attractiveness of product type 3, i.e. a seat with an extra empty seat (Sect.6.4). Finally, in Sect.6.5, we quantify the business impact of selling extra seats compared to not doing so. Appendices C and D present a decomposition approach based on time-dependent seat values, as defined in AFF, along with a pricing policy generated using simulation-based ADP. Even though these policies provide large expected revenues, they are not discussed in the main text because they are computationally expensive and offer little managerial insight. Throughout, we consider a bus that has a total of c seats where c∈{8, 16, 24, 32, 40, 48, 56, 64, 72, 80} . The length of the time horizon is dependent on the number of seats and equals T=2⋅c . The product with index 0 denotes the no-purchase alternative. The NL model described in Sect.3.2 incorporates three sets of customer choice parameters. Quality indices ( a1,a2,i,a3.i ), represent the utility associated with choosing specific seats or products. Nest similarities ( 𝜏1,𝜏2,𝜏3 ) measure the degree of similarity among alternatives within a given choice nest. Finally, price sensitivities ( b1,b2,b3 ) capture the influence of price on the probability of customer choice, reflecting how price changes affect decision-making. We assume a1=0.2 , 𝜏1=1 , 𝜏2=0.4 , 𝜏3=0.6 , b1=0.2 , b2=0.4 , and b3=0.6 , and model different customer preferences with respect to single or double seat reservations by varying the settingspecific choice behavior parameters a2,i and a3,i . In particular, we distinguish three settings: • HOMOG (homogeneous customer preferences): Quality indices are set to a2,i=0.4 and a3,i=0.6 for all seats i. (Policy-DPD) argmax p∈P(x,y) { p1 ( r1(p)− [  Vt−1(y)−  Vt−1(y−1) ]) +∑ i p2,i(r2,i(p)−[ Vt−1(y)−  Vt−1(y−1)+vi]) + ∑ i p3,i ( r3,i(p)− [  Vt−1(y)−  Vt−1(y−2)+vi+vi∗ ])} 1151 Dynamic pricing with(extra) seat reservations underthenested… • AW (preferences for aisle and window seats differ): Let Ia be the set of indices of aisle seats and Iw the indices of window seats. We assign quality indices for window seats as a2,i=0.5 for all i∈Iw and for aisle seats as a2,i=0.4 for all i∈Ia . Double reservations include one aisle and one window seat, and we assign them the same quality index as in the HOMOG setting: a3,i=0.6 for all i . • HET (heterogeneous seat preferences): In this setting, seat preferences increase with seat number, reflecting a preference for the back of the coach. Thus, we choose a2,i=0.39 +0.01i . Similar to product 2, we use a3,i=0.585 +0.02 ⋅ ⌈i∕2⌉ such that the value increases by 0.02 for every seat pair and the increment on two seats for product 2 equals the increment on these seats for product 3. To further explore the implications of differentiated preferences, we present an additional setting in Appendix E where only product type 3 exhibits varying seat preferences. The results are almost the same as in the above settings. We used CVX 1.1.18 in Python 3.8.10 to solve convex optimization problems and CPLEX 22.1.1 for linear programming problems. For non-convex mixed-integer programming problems, we implemented a custom branch-and-bound algorithm based on CVX. All computations were performed on a system running Microsoft Windows 11 Enterprise Standard 64-bit, equipped with an AMD Ryzen 7 PRO 5850U processor with 8 CPU cores and 30.8 GB of RAM. We used common random numbers to compare different pricing policies and customer preference settings. 6.1 Comparison ofupper bounds In this section, we investigate the performance of the upper bounds discussed in Sect.4. In particular, we consider the following bounds: • UB DPP: objective value of (DPP) (Sect.4.1). • UB AFF: objective value of ALP (AFF) (Sect.4.2). • UB DPD: dynamic programming decomposition (DPD-BE) (Sect.4.3). • UB DPD-Benchmark: bid price decomposition heuristic introduced in Ke etal. (2019) The benchmark introduced in Ke etal. (2019) was designed for the general network pricing problem. Its core idea is the same as the idea presented in (DPD-BE) but it computes both  Vt(y) and  Vt(xi) for all components xi . The upper bound, UB DPDBenchmark is then derived by taking the minimum of the bounds obtained from  Vt(y) and  Vt(xi) . As a consequence, we expect this benchmark to be at least as good as our (DPD-BE) problem but computationally much more expensive, Figure3a, c and e show the values of these upper bounds relative to UB DPDBenchmark for the three customer choice settings. Figure3b, d and f show the corresponding runtime necessary to calculate these bounds. Missing values indicate that the run-time exceeded 50,000s. 1152 C.Barz et al. We observe that the quality of the upper bounds, as well as their runtimes, are strikingly similar across all demand settings. Comparing our decomposition heuristic with its benchmark, we observe that our hypotheses are true: The value of UB DPD is identical to the benchmark upper bound UB DPD-Benchmark introduced in Ke etal. (2019). This can be intuitively explained by the fact that, as xi only takes binary values,  Vt (x i) can be closely approximated by an affine function. By contrast,  Vt (y ) takes input y∈{0, 1, ..., c} , making it harder to be approximated by an affine function. Numerical results underpin that  Vt (y ) typically provides a tighter upper bound than the ones provided by  Vt (x i) . So while the solution quality is similar, UB DPD is much faster than UB DPD-Benchmark. UB DPP is provably the weakest bound among the four. It is unclear a priory, however, how large the difference is (or if there even is one) and how UB AFF and UB DPD compare. Our numerical results show that UB DPP is always slightly worse than UB AFF and both are considerably worse than both UB DPD and UB DPD-Benchmark. The difference decreases with bus size from about 12% for small busses to 2% for larger ones. Comparing the runtimes of our upper bound problems, UB AFF is the most expensive upper bound problem, exceeding our 50,000s cutoff even for moderate bus sizes. The solution of the semi-infinite linear program UB AFF uses a row generation algorithm that requires the solution of a branch-and-bound algorithm for every time period in the selling horizon for each subproblem. The bounds based on the convex optimization problem UB DPP are much faster to solve. Unsurprisingly, UB DPP is faster than the decoposition approaches, as its solution serves as an initial step for both. Comparing the runtimes of UB DPD and UB DPD-Benchmark, the computation of UB DPD is considerably shorter (roughly 50%), especially for larger instances. This is expected since the benchmark heuristic computes multiple upper bounds and reports the minimum. For a problem of bus size c and time horizon T, UB DPD has to solve cT convex optimization problems and the benchmark heuristic 3cT. In comparison with the other upper bounds, UB DPD provides a low upper bound, and performs the second best in runtime. For a bus with 80 seats, it takes less than 10,000s to compute UB DPD. This makes it easy to use in practice. UB DPP performs the best in terms of runtime. However, it also provides the worst upper bound due to the simplicity in the structure of this approach. 6.2 Comparison ofexpected revenues frompricing policies Tight bounds are of great interest as empirical studies and practical experience suggest that models that give tighter bounds often lead to better controls (leading to higher expected revenue), but there is no guarantee, see (Talluri 2009). Thus, in the following, we investigate the performance of the policies discussed in Sect.5. In particular, we investigate the pricing policies (Policy-DPP), (Policy-AFF), 1153 Dynamic pricing with(extra) seat reservations underthenested… (Policy-DPD) and the bid-price decomposition described in Ke etal. (2019) as a benchmark (Policy-DPD-Benchmark), with 100 simulation runs each. The additional runtime for the policies is negligible and comparable for all policies. Once the upper bounds are calculated, in each time period only one convex optimization problem has to be solved to determine the prices for the current state. Figure4a, b and c show the performances of all pricing policies relative to UB DPD. The pricing policy based on the deterministic pricing problem, (Policy-DPP), tends to perform worst, with (Policy-AFF) being only slightly better in most cases. The gap to the upper bound varies between 6% and 12% for both policies. Pricing via (Policy-DPD) tends to improve expected revenue by 1–5 percentage points (pp) compared to (Policy-DPP), depending on the bus size. Similar revenues are obtained using the benchmark pricing heuristic (Policy-DPD-Benchmark). Fig. 3 Upper bounds for optimal expected revenue, 1.00 = UB DPD and runtime (seconds) necessary to calculate upper bounds. UB DPD and UB DPD-Benchmark yield identical results. Missing values for large bus sizes are caused by runtime limit violations 1154 C.Barz et al. 6.3 Comparison ofpricing policies We introduced the upper bounds and pricing heuristics because the curse of dimensionality prevents an exact solution in instances with large capacities. To disentangle the effects of selling extra seats from the effects of our heuristics, we now focus on an instance that can be solved exactly, i.e., with a bus size of c=8 . In our dynamic pricing problem, prices for all products are determined at the beginning of each time period t depending on the current number of seats sold y, and the reservations x . To simplify the exposition, we only discuss the homogeneous seat preference setting since all prices for products of types 2 and 3 are identical. In other words, for each t,y and x , there is a p2=p2,i and a p3=p3,i for all i. Solving (BE), we can determine the optimal prices of all three product types for each state and time period. Figure5 shows median prices for t=1, …, 16 and y=1, …,8 . Given t and y, the median prices over all possible reservation states x are displayed. No prices are displayed for product type 3 given y=1 since it requires two units of this resource. Unsurprisingly, the price of a type 1 product is cheaper than the corresponding type 2 product, which is cheaper than the corresponding type 3 product. A type 3 product is almost twice the price of a type 2 product early on, since there is no advantage of selling to a type 3 customer with scarce capacity. The differences get much smaller close to departure, especially if extra seats are available, since the opportunity cost of one extra seat decreases in time. Moreover, prices demonstrate the typical monotone behavior in t and y. Note that optimal prices, however, do depend not only on t and y but on x as well. Consider, e.g., a bus with only two specific seats left to sell, y = ∑i x i = 2 . Only if the two remaining seats available are adjacent, customers requesting product type 3 can still be served. Since future demand is higher in this case, we expect higher prices for type 1 and type 2 products. We demonstrate this by depicting the optimal prices of product types 1, 2 and 3 for all t=1, …, 16 in Fig.6. As expected, the prices of product types 1 and 2 are higher given two free adjacent seats than the corresponding products’ prices in the non-adjacent seat case. Again, product type 1 is always priced lower than product type 2. If product type 3 is available, it is even more expensive than type 2. Again, we can see that early in the booking horizon, the price of product 3 is almost twice the price of product 2 in the case of adjacent seats. The price difference between product types 2 and 3 decreases as departure approaches. To compare the performance of our heuristics with the optimal pricing policy, Fig. 7 illustrates the prices obtained from (Policy-AFF), (Policy-DPP), (PolicyDPD) and (Policy-DPD-Benchmark) given y = ∑i x i = 2 . Prices provided by the static problem (Policy-DPP) are constant over time and are lower than the prices of all other policies. In contrast, the affine approximation policy (Policy-AFF) suggests offering higher prices early in the selling horizon and reducing them only during the final time periods, particularly for product type 3. Both (Policy-DPD) and (Policy-DPD-Benchmark) recommend starting with significantly higher prices and 1155 Dynamic pricing with(extra) seat reservations underthenested… decreasing them more substantially over time. Prices for product type 1 with available adjacent seats are very similar to (and sometimes the same as) prices for product Fig. 4 Average revenue of pricing policies, 1.00 = UB DPD. Missing values for large bus sizes are caused by runtime limit violations 1156 C.Barz et al. type 2 without available adjacent seats for (Policy-DPD) and (Policy-DPD-Benchmark). Although the price structures of (Policy-DPD) and (Policy DPD-Benchmark) are similar, the latter consistently recommends slightly higher prices. When compared to the optimal prices (Fig.6), the price curves produced by (Policy-DPD) and (Policy-DPD-Benchmark) exhibit a comparable shape but start at higher price levels. 6.4 Impact oftheattractiveness ofproduct type 3 To examine the impact of product type 3 attractiveness, we solved for optimal prices via (BE) in the HOMOG setting given a bus with c=8 seats varying the attractiveness of extra seat reservations, a3,i=a3∈{0, 0.1, …, 4.9, 5} for i=1, …,c . Figure8 compares the mean revenue obtained applying the pricing policies mentioned above over 100 simulations. These results are compared to the mean revenue from applying the optimal policy and the tightest upper bound, UB DPD. As expected, both the upper bound and the mean revenues increase as the attractiveness of product type 3 rises. This is intuitive because, for a fixed price vector p , increasing the value of a3 while keeping a1 and a2 constant reduces the no-purchase probability. We observe that (Policy-DPP) and (Policy-AFF) consistently perform the Fig. 5 Heatmap of median optimal prices of available seats for each product type over the booking horizon given y 1163 Dynamic pricing with(extra) seat reservations underthenested… literature. In contrast, policies based on static problems like the deterministic pricing problem or the affine approximation deliver lower revenues, with gaps of around 6–12% relative to the best upper bounds. The introduction of extra seat reservations (our product type 3) shows notable revenue improvements, especially in low-demand scenarios, where revenue increases by up to 63.8%. Even in high-demand conditions, selling extra seats provides modest benefits, ensuring its value across different demand levels. Our sensitivity analysis modeling customers who derive little extra utility from extra seats when the bus is empty reveals that revenue gains diminish with increasing customer sensitivity to bus occupancy but remain significant, exceeding 8% even in the most adversarial cases. In a nushell, our findings emphasize the importance of adaptive pricing and leveraging extra seat reservations to maximize revenue under varying market conditions. To our knowledge, this is the first paper discussing a mathematical model to dynamically price extra seats as well as regular tickets and seat reservations. As a consequence, we see ample opportunities for future research. Since each seat is treated as an individual resource, our proposed model is highly flexible and can accommodate various seating configurations. If extra seats are strictly assigned to reservations (e.g., for personal items), the model can be directly applied with minor adjustments. An intuitive extension would be a business model where only an empty adjacent seat is guaranteed, but its use is restricted. For instance, three adjacent seats could be sold as two type-3 products, provided the empty seat is the middle one. Within our framework, this can be modeled such that a regular seat reservation for seat i requires 1 unit of resource i, while selling seat i as an empty seat would require 0.5 units of resource i. Although this adjustment introduces additional complexity to the affine approximation—since the xi variables are no longer binary—we anticipate that the decomposition approach would still perform effectively with these modifications. Empirical studies could validate our approaches against industry practices, suggest parameter estimates for our NL choice model, or suggest other choice models that should be considered. To facilitate industry implementation, our work could also be extended to account for a small, discrete set of prices only. In addition, simple heuristics to allow for the analysis of a network of connecting legs could be developed for applications with many stops, e.g., bus or rail services. In conclusion, we hope that our research inspires more work on this important industry practice and paves the way for complementary empirical research to assist companies in implementing revenue management in the face of low-demand scenarios. Appendix A: Proof ofLemma 1 We first show (1). According to the definitions of the NL choice probabilities, we have Since 𝜏j > 0 , this yields pj(r) p0(r)=pj(r) 1− ∑ l=1,2,3 pl(r)=e𝜏jIj= ⎡ ⎢ ⎢ ⎣� i∈Nj eaj,i−bjrj,i ⎤ ⎥ ⎥ ⎦ 𝜏 j ∀j= 2, 3. 1164 C.Barz et al. At the same time, the definition of pj,i(r) implies Multiplication by ∑ k∈N j e a j,k −b j r j, k gives Substituting ∑ i∈N j e a j,i −b j r j, i by (A1) and rearranging terms yields: Taking the natural logarithm leads to: Solving for rj,i , we obtain equation (1) of Lemma 1 and can interpret rj,i as a function of p : (A1) � i ∈N j eaj,i−bjrj,i= � pj(r) 1− ∑ l=1,2,3 pl(r) � 1 𝜏j ∀j= 2, 3. pi � j(r)= p j,i (r) pj(r)=eaj,i−bjrj,i ∑ k∈N j eaj,k−bjrj,k ∀j=2, 3, i=1, ..., c . e aj,i−bjrj,i= p j,i (r) pj(r) ∑ i∈N j eaj,i−bjrj,i∀j=2, 3, i=1, ..., c . e aj,i−bjrj,i=pj,i(r) pj(r)(r) � pj(r) 1−∑l=1,2,3 pl(r) � 1 𝜏j =pj,i(r) 1− ∑ l=1,2,3 pl(r) � pj(r) 1− ∑ l=1,2,3 pl(r) � 1 𝜏j −1 ∀j=2, 3, i=1, ..., c . log �eaj,i−bjrj,i�=log ⎛ ⎜⎜⎝ pj,i(r) 1−∑l=1,2,3 pl(r) � pj(r) 1−∑l=1,2,3 pl(r) �1 𝜏j −1 ⎞ ⎟⎟⎠ ∀j=2, 3, i=1, ..., c ⇔ aj,i−bjrj,i=log �pj,i(r) 1−∑l=1,2,3 pl(r)�+1−𝜏j 𝜏j log �pj(r) 1−∑l=1,2,3 pl(r)� =log pj,i(r)−log �1−� l=1,2,3 pl(r)� +1−𝜏j 𝜏j�log pj(r)−log �1−� l=1,2,3 pl(r)�� ∀j=2, 3, i=1, ..., c. 1165 Dynamic pricing with(extra) seat reservations underthenested… The proof of equation (2) can be derived along the same lines. Appendix B: Proofs aboutupper bound problems based onalinear program It is well-known, see e.g. Adelman (2007), that the following semi-infinite linear program also provides V∗ Note that problem (LP) has an infinite number of constraints and one variable for each potential state in each time period. To reduce the number of states, the value function is often replaced by a linear combination of so-called basis functions, yielding an approximation. This method of approximating the solution of a MDP is often referred to as approximate linear programming. B.1: Proof ofTheorem1 Using the value function approximation (APPROX-AFF) in (LP) yields (Policy-AFF). Applying the transformation from Lemma 1, the subproblem of the corresponding row generation problem is r j,i(p)=aj,i bj +1 bj [ log ( 1− ∑ l=1,2,3 pl ) −log pj,i ] +1 bj 1−𝜏j 𝜏j [ log ( 1− ∑ l=1,2,3 pl ) −log pj ] ,∀j=2, 3, i=1, ..., c . (LP) V∗=min Vt(⋅),t=1,…,T V T (1,c) s. t. Vt(x,y)≥p0(r)Vt−1(x,y)+p1(r)(r1+Vt−1(x,y−1)) +∑ i p2,i(r)(r2,i+Vt−1(x−𝐞𝐢,y−1) +∑ i p3,i(r)(r3,i+Vt−1(x−𝐞𝐢−𝐞𝐢∗,y−2 )) ∀t=T, ..., 1, (x,y)∈St,r∈R(x,y) V 0 (x,y)≥0∀(x,y)∈S t , 1166 C.Barz et al. with If there are time periods t with 𝜋t>0 , the optimal objective value of (P1-AFF) might be lower than the corresponding value of (AFF). Ke etal. (2019) prove, however, that the difference will never exceed ∑t 𝜋 t , which can be used in a stopping criterion or to bound VAFF and, thus, V∗ . We use (AFF-sub) to repeat Theorem1 with more precise notation: Theorem1 For a given state (x,y)∈S , subproblem (AFF-sub) is a convex optimization problem. Proof First, note that the feasible set of p , P(x,y) , is linear and thus convex. In addition, the only terms in (AFF-sub) depending on p in a non-linear way are To prove that the optimization problem is convex, it hence suffices to show that f, and hence the objective function to be minimized, is concave in p . Explicitly writing the dependence of price on p , (1), in f(p) yields The first two terms, p1 a1 b1 and pj,i a j, i b j , are linear in p . To show that the next two terms are concave, we mimic the proof of Li and Huh (2011): Let g(x,y)=x(log x−log(1−y)) . The Hessian matrix of g(x,y) is: (AFF-sub) 𝜋 t∶= max (x,y)∈St,p∈P(x,y) 𝜋t∶=p1(r1(p)−wt−1)+ ∑ i p2,i(r2,i(p)−vi,t−1−wt−1 ) +∑ i p3,i(r3,i(p)−vi,t−1−vi∗,t−1−2wt−1) −𝜃t+𝜃t−1−(wt−wt−1)y− ∑ i (vi,t−vi,t−1)xj P (x,y)= � p∈P∶p1≤y,p2,i≤xi,p2,i≤y, p3,i≤xi,p3,i≤xi∗,p3,i≤ ⌊ y∕2 ⌋ ∀i=1, …,c �. f(p)=p1r1(p)+ ∑ i p2,ir2,i(p)+ ∑ i p3,ir3,i(p) . f(p)=p1 a1 b1 + ∑ j=2,3 ∑ i pj,i aj,i bj +p1 ( 1 b1 1 𝜏1 [ log ( 1− ∑ j=1,2,3 pj ) −log p1 ]) +∑ j=2,3 ∑ i pj,i(1 bj[log (1−∑ j=1,2,3 pj)−log pj,i] +1 bj 1−𝜏j 𝜏j [ log ( 1− ∑ j=1,2,3 pj ) −log pj ]) 1167 Dynamic pricing with(extra) seat reservations underthenested… We can show that this Hessian is positive semi-definite by computing ( 𝛼,𝛽∈ℝ ): Therefore, g is convex. Since an affine function of a convex function is still convex, the functions g=g(p1,∑ipi) and  g( pj,i, ∑i,j pi,j ) are also convex. Using the same argument for the third term and noticing that f is a function of −g and −g shows the concavity of f. ◻ B.2: Proof ofTheorem2 Plugging with  V0 (y)= 0 for all y into (LP) yields The resulting problem hence mirrors the one described in Ke etal. (2019) and Zhang and Adelman (2009) and we prove the result accordingly: V∗≤VDPD holds because every feasible solution to (DPD) is also feasible in the original problem (LP). This inequality also implies the first inequality in the sequence V∗≤VDPD* ≤VDPP. The second inequality follows from the fact that (DPP) is equivalent to assuming the time-independent value function approximation Vt(x,y)=𝜃+∑ivixi+wy , see e.g. Adelman (2007). Using this equivalence, every feasible solution of (DPP) with vi=v∗ i corresponds to a feasible solution of (DPD) choosing  V(y)=𝜃+wy . As a consequence, the second inequality holds. H g(x,y)= [1 x 1 1−y 1 1−y x (1−y) 2 ] � 𝛼𝛽 � ⋅Hg(x,y)⋅ � 𝛼 𝛽 � = � 𝛼 √ x +𝛽 √ x 1−y �2 ≥ 0. V t(x,y)≈  Vt(y)+ c ∑ i=1 vixi , (DPD) V DPD =min  Vt(⋅),t=1,…,T  VT(y)+ c ∑ i=1 vi s. t.  Vt(y)≥&p0(r)  Vt−1(y)+p1(r)(r1+  Vt−1(y−1 )) +∑ i p2,i(r)(r2,i+  Vt−1(y−1)−vi) +∑ i p3,i(r)(r3,i+  Vt−1(y−2)−vi−vi∗,t−1) ∀t=T , ..., 1, ( x, y)∈  t ,r ∈  ( x, y) . 1168 C.Barz et al. Appendix C: Adecomposition based ontime‑dependent seat‑values In this section of the appendix, we introduce a decomposition based on timedependent seat-values. A short numerical study shows that runtimes of this heuristic are large and extra benefits are small when compared to the corresponding decomposition based upper bound (DPD-BE) and pricing policy (Policy-DPD). C.1: The decomposition approach The value function approximation with  vi,t representing exogenously given values of a non-reserved seat i at time t, represents another dynamic programming decomposition. In contrast to the decomposition we presented in the main text, the values of v may now be time-dependent. Fixing  V0 (y)= 0 for all y and plugging this approximation into (LP) yields A straightforward way to solve (TD-DPD) is via backward induction. Starting with  V0(y)=0 for all y, letting X( y )={ x ∈{ 0, 1 }c�∑i x i ≥y } , and using probabilities as the variables, the recursion is As in the previous section, the maximization over the right hand side can be done via branch-and-bound over the state variables taking advantage of the concavity in (p) . V t(x,y)≈  Vt(y)+ c ∑ i=1 vi,txi , (TD-DPD) VDPD =min  Vt(⋅),t=1,…,T  VT(y)+ c ∑ i=1 vi,T s. t.  Vt(y)≥p0(r)  Vt−1(y)+p1(r)(r1+  Vt−1(y−1)) +∑ i p2,i(r)(r2,i+  Vt−1(y−1)−vi,t−1) +∑ i p3,i(r)(r3,i+  Vt−1(y−2)−vi,t−1−vi∗,t−1) + ∑ i (vi,t−1−vi,t)xi∀t=T, ..., 1, (x,y)∈St,r∈R(x,y) . (TD-DPD-BE)  V t(y)= max x∈X(y),p∈P(x,y) { p0  Vt−1(y)+p1(r1(p)+  Vt−1(y−1)) +∑ i p2,i(r2,i(p)+  Vt−1(y−1)−vi,t−1) + ∑ i p3,i(r3,i(p)+  Vt−1(y−2)−vi,t−1−vi∗,t−1)+ ∑ i (vi,t−1−vi,t)xi } 1169 Dynamic pricing with(extra) seat reservations underthenested… Since we again restrict the shape of the value function, any feasible solution to (TD-DPD) yields an upper bound to the original problem (BE). In addition, it is easy to see that if we choose vi,t -values equal to the optimal solution of (AFF), the optimal solution of (AFF) is also a feasible solution in (TD-DPD). So it is not surprising that (TD-DPD) provides a tighter bound than (AFF) in this case. Theorem3 Independent of the choice of vi,t , V∗≤VDPD . Denoting the solution of (TD-DPD) with values vi,t given by the optimal solution of (AFF) by VTD-DPD* , we further have Proof V∗≤VTD-DPD holds because every feasible solution to (TD-DPD) is also feasible in the original problem (LP). This inequality also implies the first inequality in the sequence V∗≤VTD-DPD* ≤VAFF ≤VDPP. The last inequality of that sequence is a direct consequence of Proposition 5 in Ke etal. (2019). The second inequality follows from Proposition 2 in Zhang and Adelman (2009). ◻ C.2: Numerical results We compare the performance of the bound and pricing policy based on (TD-DPDBE). Figure13a–f show a comparison of the runtime and upper bound with those obtained by solving (DPD-BE) and (DPP) under the HOMOG, AW, and HET settings. While the upper bounds are identical across these methods, the runtimes for (TD-DPD-BE) are significantly longer. Notably, problems involving bus sizes of 48 seats or more could not be solved within 50,000s and are therefore not displayed. Regarding the corresponding policy, Fig. 14 compares the expected revenue achieved by the pricing policy based on (TD-DPD-BE) with (Policy-DPD) and a simulation-based approach (Policy-sbADP), which we introduce and discuss in Appendix D. Again, the decomposition based on time-independent seat values, (Policy-DPD), produces very similar expected revenues as the policy policy based on (TD-DPD-BE) while being much faster to compute. In summary, the additional computational effort does not appear to yield significantly better results. Appendix D: Simulation‑based approximate dynamic programming In this section of the appendix, we introduce a pricing policy obtained by simulation-based ADP. After a short literature review, we explain the method and highlight advantages and disadvantages in a numerical study. V∗≤VTD-DPD* ≤VAFF ≤VDPP. 1170 C.Barz et al. D.1: Related literature In contrast to ALP and decomposition methods based on ALP, simulation-based ADP (see, e.g., the textbooks by Powell (2007), (2021) and Bertsekas (2012)) provides no theoretical guarantees or intuitive interpretations. But if the associated computational burden is accepted, a large number of arbitrarily difficult basis functions can be chosen to yield very good approximations and corresponding policies. Since this approach is closely connected to the area of reinforcement learning, we also mention papers at this intersection here. Schwind (2007) formulates a dynamic pricing model for network RM as a pricecontrolled resource allocation problem. In particular, he considers an information service and information product setting and uses Q-learning and temporal-difference Fig. 13 Upper bounds for optimal expected revenue, 1.00 = UB DPD and runtime (seconds) necessary to calculate upper bounds. UB DPD, UB TD-DPD, UB TD-DPD-Benchmark, and UB DPD-Benchmark yield (almost) identical results, and are not distinguishable in the figure. Missing values for large bus sizes are caused by runtime limit violations 1171 Dynamic pricing with(extra) seat reservations underthenested… learning as solution methods, which perform better than genetic algorithms. Rana and Oliveira (2014) learn demand by a so-called Q(𝜆) algorithm based on Q-learning and update prices in real-time. Balashov etal. (2021) consider dynamic pricing of a product at an automatic gas station with discrete prices and compare several reinforcement learning algorithms. All three papers suggest algorithms that work in a model-free environment and consider an aggregated resource capacity to be sold. Maestre et al. (2019) use Q-learning and neural network approximations to dynamically price a single product. Their focus lies on fairness in pricing which is based on Jain’s index. Raju etal. (2003) consider a single-seller and a two-seller setting in which they try to learn a policy by Q-learning. Kim etal. (2014) consider a single-product case in the context of smart electricity grids. They use Q-learning without information on transition probabilities. Forootani etal. (2018) use a Least Squares Temporal Difference algorithm. Kastius and Schlosser (2022) review dynamic pricing in competitive markets using reinforcement learning. Fig. 14 Comparison of pricing policies for different seat configurations 1172 C.Barz et al. D.2: Asimulation‑based ADP dynamic pricing policy Using our problem knowledge, two adjacent non-reserved seats tend to be more valuable than two similar non-reserved but non-adjacent seats because product 3 can only be sold with adjacent seats. Intuitively, the quality of the VFA should hence improve if we include the number of available adjacent seat pairs, (Note that the division by two avoids counting two adjacent seats i and i∗ twice.) Including such multiplicative terms in our approximate linear programs complicates the resulting subproblems and prevents the solution of problems of realistic size. However, simulation-based ADP can typically provide approximations based on VFAs composed of a larger number of potentially non-linear basis functions, thus increasing the potential to produce better policies. Thus, to leverage the above observation and include further non-linear terms in the VFA, we use simulation-based ADP in addition to the aforementioned policies that rely on a numerical computation of upper bound problems. In particular, for a given partition of the set of seats { 1, …,c}= ⋃P p=1 I p into P disjoint sets, we consider the following extension of (APPROX-AFF): To see that this is indeed a generalization of (APPROX-AFF), choose P=c,Ip={p} and letting vp,t=0 for all p>c , as well as w2t=w3t=z2t=z3t=0 for all t to recover (APPROX-AFF). But we will consider more general cases in the following. To do so, we summarize the set of coefficients for a given time t in the vector 𝜹t=(v1,1,…,v3P,t,w1t,w2t,w3t,z1t,z2t,z3t) . We approximately solve (3) by backward ADP (BADP) upfront using approximation (D2) in an offline training phase, similar to the solution of the upper bound problem for the aforementioned policies. Mimicking the classical dynamic programming recursion, the idea is to go backward in time. But instead of evaluating all states exactly at each time period, only a subset is evaluated using the approximation  Vt−1( ⋅ , ⋅ ) . These values are then used to estimate the coefficients 𝜹t of  Vt . Later, to calculate online the prices for state (x,y) in period t we use the approximation  Vt−1(x,y) in (BE-RHS) and obtain the policy (Policy sbADP). In more detail, our simulation-based ADP algorithm, Algorithm1, works as follows. First, we set the approximation to 0 in t=0 , because no more revenue can be obtained, reflecting the boundary condition (see line 1). We then loop over q = 1 2 ∑ i xi⋅xi∗ . (D2) V t(x,y)≈  Vt(x,y) ∶= 𝜃t+ P � p=1 vp,t � i∈Ip xi+w1ty+z1tq+ P � p=1 vP+p,t �� i∈Ip xi +w2t √ y+z2t √ q+ P � p=1 v2P+p,t ⎛⎜⎜⎝� i∈Ip xi ⎞⎟⎟⎠ 2 +w3ty2+z3tq2. 1179 Dynamic pricing with(extra) seat reservations underthenested… Raju C, Narahari Y, Ravikumar K (2003) Reinforcement learning applications in dynamic pricing of retail markets. In: EEE international conference on e-commerce, 2003. CEC 2003. IEEE, pp 339– 346. https:// doi. org/ 10. 1109/ COEC. 2003. 12102 69 Rana R, Oliveira FS (2014) Real-time dynamic pricing in a non-stationary environment using model-free reinforcement learning. Omega 47:116–126. https:// doi. org/ 10. 1016/j. omega. 2013. 10. 004 Schwind M (2007) Dynamic pricing and automated resource allocation for complex information services: reinforcement learning and combinatorial auctions, vol 589. Springer, Berlin Sierag D (2017) Pricing-based revenue management for flexible products on a network. J Revenue Pric Manag 16:325–339. https:// doi. org/ 10. 1057/ s412720160061-1 Statista (2022) Average coach occupancy rate in France 2015–2017. https:// www. stati sta. com/ stati stics/ 11310 45/ rateoccup ationcoachfrance/ Strauss AK, Klein R, Steinhardt C (2018) A review of choice-based revenue management: theory and methods. Eur J Oper Res 271(2):375–387. https:// doi. org/ 10. 1016/j. ejor. 2018. 01. 011 Talluri KT (2009) On bounds for network revenue management. Universitat Pompeu Fabra, Barcelona Talluri KT, Van Ryzin G (2004) The theory and practice of revenue management, vol 1. Springer, New York Wilson JG (2016) Jointly optimising prices for primary and multiple ancillary products. IFAC-PapersOnLine 49(12):267–270. https:// doi. org/ 10. 1016/j. ifacol. 2016. 07. 615 Zhang D (2011) An improved dynamic programming decomposition approach for network revenue management. Manuf Serv Oper Manag 13(1):35–52 Zhang D, Adelman D (2009) An approximate dynamic programming approach to network revenue management with customer choice. Transp Sci 43(3):381–394. https:// doi. org/ 10. 1287/ trsc. 1090. 0262 Zhao G, Cui Y, Cheng S (2021) Dynamic pricing of ancillary services based on passenger choice behavior. J Air Transp Manag 94:102058. https:// doi. org/ 10. 1016/j. jairt raman. 2021. 102058 Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. Authors and Affiliations ChristianeBarz1 · JochenGönsch2· DavinaRauhaus2· SiqiHe1 * Christiane Barz [email protected] Jochen Gönsch jochen.goensc[email protected] Davina Rauhaus da[email protected] Siqi He [email protected] 1 Chair ofMathematics forBusiness andEconomics, Department ofBusiness Administration, University ofZurich, Plattenstrasse 14, 8032Zurich, Switzerland 2 Chair forService Operations, Mercator School ofManagement, University Duisburg-Essen, Lotharstr. 65, 47057Duisburg, Germany