Simple Mechanisms for Sequential Capacity Allocations

Introduction

Capacity allocation has been widely practiced in many capacity‐intensive industries including steel, fashion, and high tech (Cachon and Lariviere 1999b). For large multinational firms with many regional retail branches around the world, making smart capacity allocation decisions is particularly an important and challenging problem in maximizing the overall firm profit. In such settings, it is often difficult to align all orders from their retail branches to arrive simultaneously before the allocation begins, and as a result, the allocation decisions have to be made in a sequential manner.

For example, corn seed producers such as Monsanto, which are often large multinational firms selling seed to many countries over various continents through regional branches or subsidiaries, face sequential capacity allocation problems as a result of the following distinctive features of the industry. ¹ First, the production capacity is hardly adjustable because of the long production lead time. Second, the selling seasons of those regional markets may vary depending on weather and soil conditions in different countries. Third, transshipment between the markets is usually not viable as it involves retreating and retesting the seed that result in a long lead time from one market to another. Therefore, orders from various regions and countries to a seed producing firm do not generally arrive at the same time, and the firm has to decide how much of the existing seed to allocate to a country before observing future orders from other countries (Papier 2016).

Virus vaccine manufacturers also face similar problems. For instance, GlaxoSmithKline, one of the largest virus vaccine manufacturers, needs to respond to orders of virus vaccines from a group of countries where the infection of the virus in some countries occurs earlier than others (Reuter 2009). ² Similar to the corn seed case, the allocation decisions for the vaccines also have to be made sequentially because, once an allocation is made, it is too costly or even not viable to move some of the allocated vaccines from one country to another: The selling season of these products is relatively short, and cross‐border transportation of the vaccines may take too long because of formal import procedures that may include new documentation, repackaging, and quality testing. ³

A key question for these types of multinational firms is how to make smart allocation decisions sequentially in order to maximize the overall profit from all the retail branches. For that, it is crucial for the headquarters of the firm to be able to correctly assess the marginal benefit of allocating more capacity to the focal retail branch against the potential benefit of rationing the capacity, that is, saving enough capacity for other retail branches who would order at later time points. In particular, when the capacity is scarce, the role of capacity rationing is vitally important. For this reason, in order for the headquarters of the firm to effectively ration its capacity for the allocation decisions, a precise knowledge about the focal retail branch's local market (e.g., market size) is essential.

An important challenge for sequential capacity allocation problems arises here: The local retail branches may have access to more accurate information about the market conditions (including market sizes) than the headquarters of a large multinational firm, and hence, the local market conditions are often the retail branches’ private information (Alonso et al. 2008). One common practice observed in this type of environments is to delegate the operational decisions on the final products (e.g., order size or capacity request) to each of the retail branches (Schjelderup and Sorgard 1997). But then, these self‐interested retail branches with private information may have incentives to strategically manipulate their order quantities in their favor, anticipating capacity rationing by the headquarters. Indeed, strategic ordering within a multinational firm is commonly observed in many industries (see, e.g., Karabuk and Wu (2005) for the semiconductor industry and Caro and Gallien (2010) for the fashion industry). Such strategic ordering by retail branches makes the headquarters’ capacity rationing and allocation decisions extra challenging as it is not trivial to correctly assess the local retail branch's private market information from the (potentially manipulated) orders.

This is precisely a situation where a mechanism design approach can provide effective solutions for this type of multinational firms to overcome information asymmetry between the headquarters and their local retail branches. ⁴ That is, instead of seeking to elicit true information from the retail branches and use it for decision making, mechanism design aims to incentivize the retail branches to make decisions that are favorable for the firm. Thus, in this study, we design mechanisms for sequential capacity allocations for a firm with self‐interested retail branches. Our main objective is to develop allocation mechanisms that perform well, but more importantly, that are simple enough to be easily implemented in practice.

The essence of our mechanism design approach is to provide an incentive structure so that the allocation outcome from the mechanism would be at least close to the allocation when there is no information asymmetry. For this reason, we first characterize the first‐best optimal solution for our sequential allocation problem: that is, the allocation decision that the headquarters would make when it already knows the focal retail branch's private information. This first‐best optimal solution, which we call Pareto sequential allocation, not only helps us better understand the properties of the optimal capacity rationing, but also provides us with the target allocation outcome that our mechanisms aim at. Furthermore, because it is the optimal allocation without information asymmetry, it serves as the upper bound for the performance of our proposed allocation mechanisms, measuring how effectively our mechanisms overcome the information asymmetry.

Typically, allocation mechanisms within a firm are implemented without any internal side payments, which is partly because of the simplicity of their structures and ease of implementation. ⁵ Thus, we first design a sequential capacity allocation mechanism that effectively implements capacity rationing but does not involve any side payments. One way to implement capacity rationing in such a mechanism would be setting a priori the limit of maximum allocation to the focal retailer. This could work because, by imposing such a threshold of possible allocation, the firm can at least ration the capacity against a retailer with excessively large market size for others who will order later. But at the same time, it can also lead to an inefficient allocation of capacity when a retail branch with relatively small market size places an inflated order. We show that, however, truthful reporting is a dominant strategy in our threshold‐type mechanism which allocates as much as ordered if the order amount is below the pre‐specified allocation limit. Therefore, for retail branches whose market size is too large, this mechanism rations and allocates less than their actual needs; for retail branches with sufficiently small market sizes, it allocates exactly as much as they need.

An important advantage of this mechanism is its practicality due to its extremely simple format—it will be particularly useful when the firm does not have or does not want to change its financial system to allow internal payments among its entities as it does not involve any side payments. Despite its simple format, it is also proven to work well. As we can anticipate truthful ordering, the optimal threshold level can be easily determined for each arriving retail branch, and with the optimal set of thresholds, we show that our threshold‐type mechanism is optimal among all possible allocation mechanisms that do not allow side payments.

When the firm already has such a financial system or it is easy to revise it to allow internal side payments, mechanisms with side payments with improved performance could be designed and implemented. ⁶ Although our threshold‐type mechanism implements capacity rationing, it is not as effective as the one observed in Pareto sequential allocation. It specifies a single fixed upper limit of allocation for the arriving retail branch regardless of its type, resulting in no rationing for the ones with very low market sizes and too much rationing for the ones with very large market sizes. This has motivated us to develop a mechanism with improved performance using side payments imposed on the retail branches to be paid to the headquarters. Specifically, our mechanism specifies a menu of side payments (i.e., as a function of order quantity), and it will allocate the exact order amount as long as the pre‐determined side payment is made. By imposing a side payment whose amount depends on the order quantity, our mechanism induces a certain (target) order amount that favors the firm's overall profit. Moreover, we show that there exists a menu of side payments so that it is optimal for the retail branch to order exactly as much as in Pareto sequential allocation.

One challenge we face in determining an optimal menu of side payments is that Pareto sequential allocation is often not available in closed form. We bypass this challenge by approximating the Pareto sequential allocation with a piecewise linear function when we derive the corresponding menu of side payments. As the number of linear pieces increases, the performance of our payment‐based mechanism converges to the first‐best outcome, fully overcoming information asymmetry. Although (asymptotically) optimal, our allocation mechanism with side payments might not be practically appealing due to its complex structure of order‐dependent menu of side payments. Therefore, we also propose a simple variant of the payment‐based allocation mechanism with only a few parameters. Our extensive numerical study shows that both of our proposed simple threshold‐type and payment‐based mechanisms perform impressively well. In realistic settings where the initial capacity is not extremely scarce, our threshold‐type and simple payment‐based mechanisms achieve, on average, 93% and 99%, respectively, of the first‐best profit of sequential allocation that the firm can achieve without information asymmetry.

To the best of our knowledge, this is the first paper that studies the design of optimal sequential allocation mechanisms for large multinational firms in the presence of the retail branches’ strategic ordering behavior. Our main contributions include characterizing optimal sequential allocation mechanisms with and without side payments, and also proposing easy‐to‐implement simple allocation mechanisms that can perform well. We believe that our results provide useful insights and guidance to capacity allocation decisions when these decisions must be made sequentially in a decentralized system.

Related Literature

This study is closely related to two streams of research: one that studies sequential capacity allocations and the other that studies design of allocation mechanisms under strategic ordering. In this section, we discuss relevant papers in these two streams.

Sequential capacity allocation problems have been mainly studied in the context of inventory routing in the operations management literature. For example, Bassok and Ernst (1995) consider a system where the demand of a customer is observed when a supplier visits the customer. Since each customer has different margin to the supplier, some of the inventory of the supplier may be reserved for potential customers who have higher margins. They show that a threshold‐type policy optimizes the supplier's profit. Kumar et al. (1995) study a routing problem from one warehouse to multiple retailers and compare the optimal static and dynamic allocations of truck's capacity to minimize the total average inventory cost of retailers. Several extensions have also been made by Berman and Larson (2001) and Reiman et al. (1999). Berman and Larson (2001) incorporate the variability in travel times of the vehicle, and Reiman et al. (1999) model the randomness in product (industrial gas) usage of the customers.

Similar to our work, sequential capacity allocation has been studied often in the context of multinational firms, where the headquarters allocates capacity to multiple branches globally. Papier (2016) considers a seed producer that sells its corn seed to multiple countries in a sequential manner where the headquarters updates its demand forecast about each market, and develop an optimal policy to maximize the overall profit of the firm. A key distinction from our work is that this work does not consider strategic ordering behavior by self‐interested retail branches. There are several studies in this context that consider sequential capacity allocation problems under the firms’ objectives other than profit maximization. For example, Lien et al. (2014) and Balcik et al. (2014) investigate sequential allocation in a non‐profit setting where the objective of the allocation is maximizing the minimum fill rate of the retailers to create fair allocations.

Although the above papers all consider sequential capacity allocation problems, their main focus is on the firms’ allocation strategies when the market information of each retail branch is known to the firm at the time of allocation decision. In this study, we incorporate each retailer's self‐interested behavior driven by information asymmetry about the market condition which is commonly observed in practice and also considered in the literature (e.g., Chevaleyre et al. 2006). Under strategic order inflation in the presence of information asymmetry, rationing capacity for the remaining retailers can be challenging due to lack of information about the actual need of the focal retailer. We propose optimal allocation mechanisms that maximize the overall profit of the firm by showing that the headquarters of the firm can effectively ration its capacity in a more delicate way by imposing thresholds or side payments to be paid by the retailers.

In a decentralized multinational firm where local retail branches make pricing and ordering decisions independently, retail branches may have an incentive to inflate their orders to receive more favorable allocations, and there is a stream of related research that studies addressing capacity allocation problems under strategic ordering through a mechanism design approach. For example, Cachon and Lariviere (1999a) consider simultaneous capacity allocation problems and show that the allocation mechanisms that maximize the total profit of the retailers are not truth‐inducing. Liu (2012) considers a supply chain that consists of a supplier and two competing retailers and find that the uniform allocation—which is known to be a truth‐inducing allocation mechanism—is not necessarily truth‐inducing in the presence of competition. Cho and Tang (2014) generalize the work of Liu (2012) to provide the general condition where uniform allocation mechanism fails to remove retailers’ order manipulation incentives. Chen et al. (2013) compare the performance of the lexicographic and proportional allocation mechanisms when a supplier allocates its limited capacity to competing retailers. Their results suggest that the lexicographic allocation mechanism tends to exhibit a higher profit for the supplier, as well as for the supply chain. All the above papers consider “simultaneous” allocation problems where the allocation decisions are made after observing all orders from the retailers. In this study, we consider strategic ordering of self‐interested retailers within a large multinational firm where the orders arrive and allocations decisions are made in a “sequential” manner.

A mechanism design approach has also been widely used in the operations management literature, not only for addressing capacity allocation problems to multiple buyers, but also tackling various problems in the presence of information asymmetry between buyers and suppliers. For example, Wang et al. (2016) analyze the regulator's problem to design a regulation for a firm facing environmental hazards. In a situation where the occurrence of the hazard is the firm's private information, the objective of regulator is to minimize expected social cost in the long run by optimizing its inspection and reward policy for the firm. Zhang (2010) considers a buyer procuring a product from a supplier and selling it to the market. The supplier's cost is its private information, and the buyer's objective is to design a procurement mechanism to maximize its profit. Like we do for our optimal mechanism design, some of the studies in this stream also deploy side payments in their allocation mechanisms. For example, Karabuk and Wu (2005) and Mallik and Harker (2004) impose side payments in their allocation mechanisms to coordinate the supply chain in simultaneous allocations. Similarly, Li et al. (2012) use side payments to better coordinate a two‐tier supply chain in the context of inventory management.

Despite its growing practical and academic significance, sequential allocation mechanisms have not received much attention in the literature, and the main contribution of this work is that we design optimal mechanisms for sequential allocation problems. We discuss key challenges in sequential allocation mechanism design, and we characterize optimal sequential allocation mechanisms that maximize the firm's overall expected profit with and without the use of side payments. More importantly, we also propose sequential allocation mechanisms that have simple formats, and hence, easy to implement in practice, but at the same time, perform well.

The Model

We consider a capacity allocation problem of a firm that needs to allocate its production capacity based on the orders from its N regional retail branches. ⁷ The retail branches’ orders arrive sequentially, and each allocation decision has to be made before the next order arrives. The firm has limited production capacity, denoted by K, which is pre‐determined and cannot be adjusted during the allocation horizon. ⁸ The firm's headquarters adopts an allocation mechanism to distribute the available capacity to each retail branch to maximize its overall profit (i.e., the total profit from the N retail branches). The regional retail branches have access to more accurate information about the local market conditions than the headquarters, and the headquarters delegates the operational decisions on the final products (e.g., order size or capacity request) to each of the retail branches. Accordingly, each retail branch is a self‐interested agent, and hence, determines its order quantity to maximize its own profit. Without loss of generality, we assume Retail Branch i is the one whose order is the i‐th in the sequence of arriving orders.

Information structure. The local market size of each region, denoted by

θ i

f i ( θ i )

[ θ ̲ i , θ ¯ i ]

0 ≤ θ ̲ i < θ ¯ i ≤ ∞

Market structure. The retail branches are located in different geographic regions, and because of geographical separation, these regional markets are segmented, leaving the retail branches free from direct competition among themselves. In addition, we assume further that transshipment and price arbitrage over different markets are not viable. It is because, given the geographical separation, the transshipment among the retail branches can be too costly to offset the price arbitrage of one region. Moreover, while selling seasons of the local markets may vary, transshipping products between markets are often not possible especially when selling season of each local market is short because it often takes extensive logistics and processing time for post‐import testing and treatments for transshipment (Papier 2016).

Allocation outcome. We use a _i to denote the outcome of capacity allocation (i.e., the actual quota) made to Retail Branch i. In addition, we let u _i be the available capacity for Retail Branch i. Hence, u ₁ = K and:

u i : = u i − 1 − a i − 1 = K − ∑ j = 1 i − 1 a j , for i ∈ { 2 , 3 , … , N } .

Sequential allocation game. The firm uses a mechanism to determine the allocation quantities without knowing the arriving retail branch's market size. In this sequential allocation setting, a mechanism can be represented as a sequential allocation game which consists of N sub‐games—in each stage, one retail branch arrives and the firm announces a sub‐mechanism only for the focal retail branch. Then, in response to the sub‐mechanism, the focal retail branch places its order and receives its allocated capacity. Accordingly, we let

m i

The Stage i sub‐mechanism, denoted by h _i , specifies the remaining capacity u _i and maps the retail branch's order

m i

h i : { m i ; u i } → a i

In this study, for practical and technical purposes, we assume that a sequential allocation mechanism satisfies the following continuity assumption between the ordered and the allocated amounts: ¹⁰ (i) The mechanism does not allocate any capacity for zero order quantity (i.e., h _i (0; u _i ) = 0); and (ii) The allocation outcome

h i ( m i ; u i )

m i

Retail branch's profit function. We assume that the market price for Retail Branch i, denoted by p _i , is determined by the inverse demand function,

p i = θ i − a i

π i ( θ i , a i ) = ( θ i − a i ) a i .

1

θ i

θ i / 2

r i ( θ i )

θ i

r i ( θ i )

P ∑ i = 1 N r i ( θ i ) = P ∑ i = 1 N θ i / 2 > K > 0 .

Pareto Sequential Allocation

Before we study optimal mechanisms for our sequential allocation problem, we first characterize the first‐best outcome of the sequential allocation game described above. The first‐best outcome refers to an optimal solution to the sequential allocation problem without information asymmetry, that is, the case where the market size of the focal retail branch,

θ i

, becomes available to the headquarters when it makes the allocation decision at Stage i of the game. In that situation, the headquarters faces a dynamic programming problem. ¹²

Studying the first‐best outcome of sequential allocation is important for our mechanism design because of the following reasons: (i) It shows how the sequential nature of the problem affects the firm's optimal allocation decisions; (ii) It helps us to identify key factors for an effective allocation decision; (iii) It will be useful for performance evaluation of a mechanism as the first‐best outcome provides the upper‐bound of performance; and (iv) The first‐best allocation mapping between the retail branch's type and the optimal allocation will be directly used for our optimal mechanism design in section 5.

While studying simultaneous allocation problems, Cachon and Lariviere (1999a) call the first‐best allocation outcome that maximizes the firm's overall profit under full information setting Pareto allocation. Following this, we call the first‐best allocation outcome in our sequential setting Pareto sequential allocation. The key distinction of Pareto sequential allocation from Pareto allocation is that it is the firm's optimal allocation outcome in each stage of the game when the firm already knows the market size of the focal retail branch that has just placed an order, but still does not know the market sizes of the retail branches who will order later.

We now derive Pareto sequential allocation and discuss its characteristics in details. Pareto sequential allocation is a solution to the following Bellman equation and can be derived by backward induction. First, consider Retail Branch N that arrives last. For given θ _N , the optimal allocation amount to Retail Branch N, denoted by

a N P

, is determined by solving the following profit maximization problem (here, we use superscript P to denote “Pareto” allocation):

a N P ( θ N ; u N ) = arg max 0 ≤ a ≤ u N π N ( θ N , a )

Notice that given Retail Branch i's profit function described in Equation (1), and by the definition of its actual need r _i , the optimal solution for the above profit function is allocating as much as possible up to the retail branch's actual need r _N (θ _N ). Formally, this means:

a N P ( θ N ; u N ) = min { r N θ N , u N } .

To find the optimal allocations for other retail branches, we let

V i P

be the value function for the firm's overall profit from Stage i onwards. This value function depends on private information of Retail Branch i (i.e.,

θ i

) and the remaining capacity u _i . Accordingly, the Bellman equation gives:

V i P ( θ i ; u i ) = max 0 ≤ a ≤ u i { π i θ i , a + E [ V i + 1 P θ i + 1 ; u i − a ] } .

2

From this, the optimal allocation for Stage i is determined by:

a i P ( θ i ; u i ) = max 0 ≤ a ≤ u i { π i θ i , a + E [ V i + 1 P θ i + 1 ; u i − a ] } , i = 1 , 2 , … , N − 1 .

Together with the last retail branch's allocation,

a N P ( θ N ; u N )

, these optimal allocation solutions form Pareto sequential allocation.

In their study of simultaneous allocation, Cachon and Lariviere (1999a) show that Pareto allocation should have the following properties: (i) it is increasing in demand of each retail branch; and (ii) it should end up with no unallocated capacity. ¹³ These are driven by the firm's objective of maximizing its expected overall profit. Specifically, under simultaneous allocation, since all the retail branches’ demands are available at the same time, more capacity should be given to a more profitable retail branch, and also, there is no benefit of wasting capacity by leaving it unallocated. In Stage i of the sequential allocation problem, on the other hand, the headquarters has to compare the benefit of allocating capacity to the focal retail branch with the expected benefit of reserving capacity for other retail branches who will order later. This may result in reserving some capacity for future orders at the risk of potential capacity waste. This practice, called capacity rationing, is captured in the Bellman Equation (2). Hence, understanding when and how much capacity rationing is necessary is the key for an optimal sequential allocation.

Intuitively, the degree of rationing in the i‐th allocation depends on the profitability of the focal retail branch and the available capacity, u _i . As Retail Branch i gets more profitable (i.e., has larger market size), allocating more capacity to this retail branch can improve the overall profit of the firm, and at the same time, reduces the amount of reserved capacity

u i − a i P ( θ i )

. Our analysis shows that rationing occurs in most cases, whereas in the following two extreme cases, rationing may not occur when the available capacity u _i relative to the market size

θ i

is too small or too large. In the first case when the market of the focal retail branch is significantly profitable and the remaining capacity is too scarce, it can be optimal to allocate all the capacity to this retail branch (hence, no rationing). In contrast, in the second case when the firm has very large remaining capacity—large enough to satisfy the other retail branches who will order later—the firm can satisfy the actual need of the focal retail branch (again, no rationing).

Figure 1 illustrates examples of these two extreme cases of rationing by showing

a 1 P ( θ 1 )

with respect to θ ₁ for a two‐retail branch problem. Part (a) of Figure 1 corresponds to the case where capacity is scarce for Retail Branch 1. In this case, when the focal retail branch is very profitable (high θ ₁), the first case (allocating all the available capacity) occurs. Otherwise, the headquarters chooses to ration. In particular, when the retail branch whose order has just been placed is not profitable, the headquarters may even choose not to allocate any amount (full rationing). As shown in part (b) of Figure 1, when the remaining capacity is relatively very large, the second extreme case may still occur in Pareto sequential allocation. When the actual need of Retail Branch 1 is small enough relative to the remaining capacity, the headquarters chooses to satisfy Retail Branch 1's actual need. In other cases, satisfying its actual need could be too costly: near

r i ( θ i )

, the marginal value of allocating one more unit of capacity to Retail Branch 1 is, in general, much smaller than the marginal benefit of reserving one more unit of capacity for Retail Branch 2. Accordingly, the headquarters does not satisfy Retail Branch 1's actual need and reserves more capacity for Retail Branch 2. Lastly, in both cases, we observe that the degree of capacity rationing (i.e.,

u 1 − a 1 P ( θ 1 )

) is non‐increasing in θ ₁, and is decreasing when

0 < a 1 P ( θ 1 ) < u 1

.

OPEN IN VIEWER

Figure 1

Comparison of Pareto Sequential Allocation, Actual Need, and Available Capacity for Retail Branch 1: In Both Cases,

N = 2 , π i ( θ i , a i ) = ( θ i − a i ) a i

, and

θ i ∼ U ( 0 , 10 )

[Color figure can be viewed at wileyonlinelibrary.com]

Our analysis on Pareto sequential allocation illustrates how challenging the sequential allocation problem could be even when the decision maker has access to the actual need of the focal retail branch that places an order. The complication mainly comes from the firm's incentive to ration, whose degree depends on multiple factors. Under our private information setting, the rationing decision becomes even more challenging as the self‐interested retail branches now have incentives to strategically “inflate” their orders. In section 4, we study how the firm should design a mechanism in order to implement capacity rationing under the private information setting to maximize its overall expected profit.

Sequential Allocation Mechanisms without Side Payments

We now study how the firm should design an allocation mechanism to maximize its profit. This section focuses on the situation where side payments from the retail branches to the headquarters are not allowed (e.g., the firm's financial system does not allow internal side payments among entities and changing the system is too costly). In section 5, we extend our attention to mechanisms with side payments and examine how the performance of the mechanisms can improve.

Retail Branch's Profit‐Maximizing Ordering Strategy

We first characterize the retail branch's optimal ordering strategy in each subgame under allocation mechanism h _i (·; u _i ) without any side payments. Consider Retail Branch i. Given its private information

θ i

, this retail branch's best response

m i h ( θ i )

will be the maximizer of its profit:

m i h ( θ i ) = arg max m π i ( θ i , h i m ; u i ) .

We note that, given the announced mechanism h _i (·;u _i ), it is enough to consider the following two cases in order to characterize its optimal ordering strategy: (i) there exists a finite order amount

m ∼

which results in the retail branch's actual need

r i ( θ i )

, that is,

h i ( m ∼ ; u i ) = r i ( θ i )

; and (ii) no order amount results in the actual need, that is, for any finite value m,

h i ( m ; u i ) < r i ( θ i )

. In case (i), the retail branch's best response is simply placing the order amount of

m ∼

. In case (ii), on the other hand, the best response for the retail branch is to choose m which gives the largest allocation amount, that is,

m ¯ = arg max m h i ( m ; u i )

. Since the retail branch's profit is increasing in the allocation amount until its actual need, we know that m will be the order amount that results in an allocation that is closest to the retail branch's actual need.

Motivated by this observation, we now consider an allocation mechanism with a very simple format in which finding the optimal ordering strategy for each retail branch is straightforward: a mechanism with a pre‐specified threshold that bounds the maximum allocation amount. Under this mechanism, any order below the threshold will receive exactly the order amount; otherwise, it will only receive the maximum amount. We call this type of mechanisms a threshold‐type mechanism. We note that this type of mechanisms is similar to the sequential allocation mechanisms studied in Lien et al. (2014) and Bassok and Ernst (1995) who do not consider strategic ordering for the design of their mechanisms. Since the threshold is determined and announced before the retail branch places its order, it is independent of the retail branch's private information. Indeed, the threshold plays an important role for the performance of the mechanism—it is used to implement capacity rationing. Therefore, it is determined based on the number of retail branches and the distribution of their private information.

Now let us formally describe the threshold‐type mechanisms. We let t _i (u _i ) specify the threshold for Stage i sub‐mechanism given the available capacity u _i . We call a sub‐mechanism threshold type if it can be represented as follows:

g i ( m i ; u i ) = min { m i , t i ( u i ) } .

3

Then, the mechanism for the sequential allocation game, denoted by G, is represented by a set of N threshold‐type sub‐mechanisms, that is, G: = {g ₁, …, g _N }. We use

G

to denote the class of all possible threshold‐type mechanisms which are in the form of G: = {g ₁, …, g _N }. Also, we use

m i g ( θ i )

to denote the best response of Retail Branch i in the sub‐mechanism g _i . Similarly, we use

Q

to define the entire class of allocation mechanisms that do not involve any side payments (i.e., mechanisms that belong to the class of mechanisms specified by the continuity assumption in section 3). Accordingly, we use Q to denote a mechanism in

Q

with a set of N sub‐mechanisms q _i 's.

Our objective in this section is to propose an optimal mechanism over Class

Q

. Our first step is to show that, when finding such an optimal mechanism, it suffices only to consider mechanisms in Class

G

instead of Class

Q

, thanks to the following equivalence theorem. The proof of this theorem as well as all other proofs are provided in the appendix.

Theorem 1

Consider any mechanism

Q : = { q 1 , … , q N } ∈ Q

. Then, we can always find a mechanism

G ∈ G

that generates exactly the same allocation outcome as that of Q for any information profile of the retail branches, Θ: = {θ ₁, …, θ _N }. Moreover, the following relationship holds for Stage i's threshold in G:

t i ( u i ) = sup m q i ( m ; u i ) .

The above theorem ensures that once a mechanism is optimal within Class

G

, it is also optimal among all mechanisms without side payments. To this end, our next result characterizes the optimal ordering strategy under a threshold‐type mechanism.

Proposition 1

Under a threshold‐type mechanism G, reporting the actual need

r i ( θ i )

is an optimal ordering strategy for Retail Branch i with private information

θ i

. That is,

m i g ( θ i ) = r i ( θ i )

.

Remark 1

We note that the optimal ordering strategy may not be unique. For example, when the actual need of Retail Branch i exceeds the allocation threshold (i.e.,

r i ( θ i ) > t i ( u i )

), ordering any quantity above the threshold will lead to the same allocation (i.e., a _i  = t _i (u _i ) for any

m i ≥ t i ( u i )

), which maximizes the retail branch's profit. Hence, a threshold‐type mechanism in the form of Equation (3) is weakly truth‐inducing. For this reason, a threshold‐type mechanism in Class

G

can be particularly useful in practice as it effectively alleviates the burden of finding an optimal ordering strategy for the retail branches.

Based on the above results on the retail branch's ordering strategy, in the next section, we propose an optimal sequential allocation mechanism in the class of mechanisms without side payments.

Profit‐Maximizing Mechanism without Side Payments

Theorem 1 shows that any allocation mechanism without side payments can be represented as a threshold‐type mechanism defined in Equation (3). This enables us to restrict our attention to class

G

when finding a profit‐maximizing mechanism. Based on this, in this section, we propose an allocation mechanism that maximizes the firm's overall profit (i.e., the total profit of all the retail branches) within the class of mechanisms without any side payments to the firm's headquarters by its retail branches. Specifically, our main focus in this section is on finding the optimal threshold t _i (u _i ) for Retail Branch i to maximize the firm's overall expected profit. For this, by backward induction, we start by examining the allocation problem for Retail Branch N.

Since Retail Branch N is the last one, the optimal threshold t _N (u _N ) should be the maximizer of the following expected profit of Retail Branch N:

t N * ( u N ) = arg max 0 ≤ t ≤ u N E [ π N ( θ N , min m N , t ) ] .

4

It is clear that simply setting t _N (u _N ) = u _N maximizes the expected profit of Retail Branch N because imposing any tighter threshold than u _N to Retail Branch N only results in unused capacity at the end of the allocation horizon, reducing the expected profit of Retail Branch N's profit as well as the firm's overall profit.

Now, consider Retail Branch i. Following Proposition 1, we set Retail Branch i's order as

m i g ( θ i ) = r i ( θ i )

, which then results in an allocation of

min { r i ( θ i ) , t i ( u i ) }

. Then, similar to Pareto sequential allocation, we can derive a recursive equation for t _i (u _i ). Specifically, the total expected profit of retail branches whose indices are higher than i, denoted by

V i T ( u i )

, is determined by the following Bellman's recursive equation for i = 1, 2, …, N−1:

V i T ( u i ) = max 0 ≤ t ≤ u i E π i ( θ i , min { r i ( θ i ) , t } ) + V i + 1 T u i − min { r i ( θ i ) , t } .

The optimal threshold

t i * ( u i )

is the solution to the above problem for given u _i as described below.

t i * ( u i ) = arg max 0 ≤ t ≤ u i E π i ( θ i , min { r i ( θ i ) , t } ) + V i + 1 T u i − min { r i ( θ i ) , t } .

5

We call the threshold‐type allocation mechanisms whose thresholds are defined by equations (4) and (5) Allocation Mechanism T. The following result shows that Allocation Mechanism T maximizes the firm's overall profit within the class of allocation mechanisms without side payments.

Corollary 1

Allocation Mechanism T achieves the highest overall expected profit of the firm among all the mechanisms in Class

Q

.

This means that optimizing the thresholds is enough for finding an optimal allocation mechanism (i.e., Allocation Mechanism T) among the entire class of mechanisms without side payments we consider. This is due to the equivalence result of Theorem 1. One important property of Allocation Mechanism T is its simple structure which makes it appealing in practice. In addition, the fact that it does not involve side payments make it particularly useful when the firm does not have or does not want to change their financial systems to allow internal payments among its entities. However, the way it implements capacity rationing can be quite different from Pareto sequential allocation—while in Pareto sequential allocation, the rationing depends on the private information

θ i

, but this is not the case in Allocation Mechanism T. Therefore, when a firm already has such a financial systems, or it is easy to revise it for internal side payments, a mechanism with side payment can be considered as it may have a potential to be more effective in implementing capacity rationing similar to that of Pareto sequential allocation. In the next section, we extend our attention to the class of mechanisms that allow side payments so that capacity rationing depends on the retail branches’ private information.

Remark 2

In this study, we assume that the retail branches’ regional markets have linear demand. However, all the results in this section hold true (i.e., our Allocation Mechanism T is optimal in Class

Q

) as long as the following conditions are satisfied with respect to Retail Branch i's profit function:

∂ 2 ∂ a i ∂ θ i π i ( θ i , a i ) > 0 , ∂ 2 ∂ a i 2 π i ( θ i , a i ) < 0 , and ∂ ∂ θ i π i ( θ i , a i ) > 0 .

These conditions ensure that: (i) There exists a finite and unique actual need, r _i for Retail Branch i, which is increasing in

θ i

; and (ii) If r _i is not feasible (e.g., u _i  < r _i ), the maximizer is the one that is closest to r _i .

Sequential Allocation Mechanisms with Side Payments

In this section, we consider sequential allocation mechanisms in which side payments must be paid by the retail branches to the headquarters in return for the allocated capacity. In practice, mechanisms with side payments are often implemented for capacity allocation decisions, especially to control potential opportunistic behavior of participants. For example, PJM, one of the largest power system operators in the United States uses auction mechanisms to procure power supply resources to meet the predicted demand, where each provider offers its desired price and capacity to PJM. If a provider fails to deliver the promised capacity to the consumers, PJM imposes penalty according to the rule that has been pre‐specified in the auction mechanism (PJM 2019). Such side payment scheme plays an important role in discouraging the providers’ risky bidding behaviors. Similar to our setting, side payments are also often implemented in within‐firm allocation mechanisms. For example, in order to prevent misrepresentation of capacity in allocation, the headquarters of a US‐based semiconductor firm imposes side payments when the realized capacity of the production division is too small compared to the forecast (Mallik and Harker 2004).

Incorporating side payments into the mechanism design has a potential to improve the overall expected profit of the firm because the imposed side payments that depend on the order quantity directly impacts each retail branch's ordering strategy. The imposed payments may not only discourage order inflation but can also provide a way to induce a certain order amount (e.g., Pareto sequential allocation amount) in the favor of the firm. In this regard, the essence of designing an optimal sequential allocation mechanism with side payments is how to determine the menu of side payments so that the retail branch's optimal order quantity is exactly the allocation outcome in Pareto sequential allocation.

The main challenge here, however, is that we do not always have a closed form expression for Pareto sequential allocation. In the following section, we first show that we can derive a menu of side payments in closed form when the target allocation is a linear function. We then show that achieving the expected overall profit under Pareto sequential allocation is theoretically possible by approximating Pareto sequential allocation by a piecewise linear function. Because of the complexity arising from many linear pieces, it might not be practical to implement this (asymptotically) optimal mechanism. Section 5.2 proposes a much simpler variant of the optimal payment‐based mechanism which is easy to implement and has a potential to perform well. We then examine its performance in section 6 via an extensive numerical experiments.

Profit‐Maximizing Mechanism with Side Payments

When implemented, side payments can affect the self‐interested retail branch's ordering decision, but they do not affect the overall firm's profit as they are simply transfers of money within the firm. To show how a mechanism with side payments can improve the allocation outcome, we first examine how the menu of imposed side payments affects the retail branches’ ordering decisions. We define the side payments as a function of the order quantity, denoted by

s i ( m i ) ( ≥ 0 )

, which is the amount that Retail Branch i has to pay to the headquarters to receive the order amount

m i

. ¹⁴ Once the side payment is fully made, then the order amount is allocated to the retail branch. Hence, the mechanism that we consider in this section can be formally described as follows: ¹⁵

h i ( m i ; u i ) : = min { m i , u i } .

Then, Retail Branch i's ordering strategy under this allocation mechanism,

h i ( m i ; u i )

, is characterized as:

m i h ( θ i ) = arg max m i π i ( θ i , h ( m i ; u i ) ) − s i ( m i ) = arg max m i π i ( θ i , min { m i , u i } ) − s i ( m i ) .

6

Now, our objective is to determine the menu of side payments

s i ( m i )

so that ordering the exact amount of Pareto sequential allocation (i.e.,

m i h ( θ i ) = a i P ( θ i )

) would be the optimal strategy for Retail Branch i. To do so, we first need to characterize

a i P ( θ i )

as a function of

θ i

. It is obvious that

a i P ( θ i )

is non‐decreasing in

θ i

. However, the closed‐form expression of Pareto sequential allocation as a function of

θ i

may not always be available. Therefore, we consider a piecewise linear approximation of

a i P ( θ i )

, dented by

a ¯ i ( θ i )

. We then examine the payment function that induces

a ¯ i ( θ i )

as the retail branch's optimal ordering strategy.

Let us explain how we construct

a ¯ i ( θ i )

. Let

( x 0 , y 0 ) : = ( θ ̲ , 0 )

. To set n discrete points on

a i P ( θ i )

, we choose y _j 's on y axis such that

y 1 < y 2 < ⋯ < y n ( : = sup θ i a i P ( θ i ) )

and find corresponding x _j 's that satisfy

y j = a j P ( x j )

for j ∈ {1, 2, …, n}. We then connect these points with straight lines to form the piecewise linear approximation. This gives, for

θ i ∈ [ x j − 1 , x j ]

where j ∈ {1, 2, …, n}:

a ¯ i ( θ i ) : = ξ j − 1 ( θ i − x j − 1 ) + y j − 1 .

7

Here,

ξ j − 1 : = y j − y j − 1 x j − x j − 1

is the slope of the j‐th linear piece.

We now explain how the menu of side payments

s i ( m i )

can be determined. In our linear demand setting, Retail Branch i's profit from ordering

m i

and making the required side payment

s i ( m i )

is as follows. ¹⁶

π i ( θ i , m i ) = ( θ i − m i ) m i − s i ( m i ) .

8

Given this profit function, we now investigate how to design the payment function,

s i ( m i )

, in order to induce

a ¯ i ( θ i )

as the optimal ordering quantity. For that, suppose Retail Branch i's market size

θ i

belongs to [x _j−1,x _j ]. The profit‐maximizing ordering quantity is:

m i h ( θ i ) = arg max m i ∈ [ y j − 1 , y j ] ( θ i − m i ) m i − s i ( m i ) .

We want to set the menu of side payments

s i ( m i )

so that ordering

a ¯ i ( θ i )

maximizes the profit specified in Equation (8), both locally (i.e., for all

m i ∈ [ y j − 1 , y j ]

) and globally (i.e., for all

m i ∈ [ y 0 , y n ]

). Hence, by matching the optimal order

m i h ( θ i )

to be

a ¯ i ( θ i )

(i.e., local optima), we get:

s i ( m i ) = 1 2 ξ j − 1 − 1 m i 2 + x j − 1 − y j − 1 ξ j − 1 m i + e i , j ,

9

where any choice of the constant, e _i,j , makes

a ¯ i ( θ i )

to be a local optima. Then, by suitably setting e _i,j 's to make

a ¯ i ( θ i )

be a global optima, we get the following result.

Proposition 2

Consider Stage i sub‐mechanism

h i ( m i ; u i ) : = min { m i , u i }

whose menu of side payments

s i ( m i )

for

m i ∈ [ y j − 1 , y j ]

, j ∈ {1,2,…,n}, is as described in Equation (9) with the following e _i,j term:

e i , j = 0 for j = 1 , 1 2 ξ j − 1 − 1 y j 2 + x j − 1 − y j − 1 ξ j − 1 y j + e i , j − 1 − 1 2 ξ j − 1 y j 2 + x j − y j ξ j y j for j ≥ 2 .

Then, it is optimal for Retail Branch i to place an order quantity

a ¯ i ( θ i )

, which is the piecewise linear approximation of Pareto Sequential Allocation defined by Equation (7).

When we define

a ¯ i ( θ i )

, we arbitrarily set y _j 's between 0 and

sup θ i a i P ( θ i )

to divide it by n distinct intervals. If they are properly chosen (e.g., with equally spaced n intervals), then it is straightforward that

a ¯ i ( θ i )

converges to

a i P ( θ i )

as n approaches to infinity. This also suggests that Retail Branch i's ordering strategy will converges to

a i P ( θ i )

as the number of linear pieces increases. This implies that the payment‐based allocation mechanism specified by the menu of side payments in Proposition 2 is asymptotically optimal. The following theorem states this result.

Theorem 2

Consider the sequential capacity allocation problem with N retail branches and the payment‐based allocation mechanism described in Proposition 2. The overall expected profit of the firm generated by this payment‐based allocation mechanism with n linear pieces converges to the overall expected profit of Pareto sequential allocation as the number of linear pieces n increases to infinity.

Simple Penalty‐Based Allocation Mechanism

Theorem 2 shows that our proposed mechanism is asymptotically optimal with infinitely many linear pieces. However, it also poses practical challenges for its implementation because of the complexity in the menu of side payments. As seen in the previous section, the approximation of the menu of side payments involves three major steps: (i) calculation of Pareto sequential allocation to be used as the target outcome; (ii) computation of linear pieces for this target outcome; and (iii) finding the menu of side payments for each of the linear pieces so that the target allocation is the globally optimal ordering quantity. Therefore, as the number of pieces increases, its implementation becomes computationally infeasible. In this section, we propose a simpler variant of the previous payment‐based allocation mechanism which is easy to implement in practice. Specifically, to design a mechanism that performs well, we first carefully examine the properties of Pareto sequential allocation and develop a simplified payment function that can capture key properties of it. In the next section, we evaluate the performance of our simple payment‐based mechanism via an extensive numerical study, and the results show it achieves near‐optimal performance despite its simple format.

Analysis of Pareto Sequential Allocation: Two Retailers with Uniform Distribution. When we simplify the menu of side payments in our payment‐based allocation mechanism, it is useful to first understand the main properties of Pareto sequential allocation, which is the optimal allocation outcome when the headquarters of the firm knows the focal retail branch's market size parameter. This will help us identify the key characteristics that make it optimal. Based on this, we will simplify the menu of side payments so that it still effectively captures those key characteristics.

For this purpose, let us consider a sequential allocation problem with two retail branches where their market size parameter

θ i

follows a uniform distribution—for this small problem, we can specify Pareto sequential allocation in closed form. We assume that the uniform distribution is defined on [0,M] and restrict our attention to the case where the initial capacity K is not too large (i.e., K ∈ [0,M]) to avoid situations where the sequential allocation problem becomes trivial.

Table 1 summarizes Pareto sequential allocation to Retail Branch 1. In essence,

a 1 P ( θ 1 )

is determined from the comparison of the marginal benefit of allocating one more unit of capacity to Retail Branch 1 with the marginal cost of reducing one more unit from those reserved for Retail Branch 2. We notice that this marginal benefit depends on the three factors: θ ₁, a ₁, and K. A higher θ ₁ implies a higher market size of Retail Branch 1, and thereby a higher marginal benefit to the overall profit of the firm. The marginal benefit also depends on the actual allocation amount given to Retail Branch 1. It decreases in the allocation amount. In addition, we note that an increase in the total capacity positively impacts the allocation to Retail Branch 1, which is in line with our intuition.

OPEN IN VIEWER

Table 1

Pareto Sequential Allocation under Uniform Distribution

Total capacity	a 1 P ( θ 1 ) ‐ Pareto allocation for retail branch 1
0 ≤ K < M 4	0	for 0 ≤ θ 1 < ( M − 2 K ) 2 2 M
	K − M + M ( − 4 K + 3 M + 2 θ 1 ) 2	for ( M − 2 K ) 2 2 M ≤ θ 1 < 4 K + M 2
	K	for 4 K + M 2 ≤ θ 1 ≤ M
M 4 ≤ K < M 2	0	for 0 ≤ θ 1 < ( M − 2 K ) 2 2 M
	K − M + M ( − 4 K + 3 M + 2 θ 1 ) 2	for ( M − 2 K ) 2 2 M ≤ θ 1 ≤ M
M 2 ≤ K < M	θ 1/2	for 0 ≤ θ 1 < 2K−M
	K − M + M ( − 4 K + 3 M + 2 θ 1 ) 2	for 2K−M ≤ θ 1 ≤ M

Now, let us examine

a 1 P ( θ 1 )

in more detail. First, consider the case where the capacity is very scarce (K < 4/M). This high degree of scarcity of capacity makes rationing very important—since per unit value of the capacity is high, unless the market of Retail Branch 1 is substantially profitable, it is better to ration. So, if the market size θ ₁ is also low, the marginal benefit of capacity allocation to Retail Branch 1 is always lower than its marginal cost, and allocating nothing is optimal. If the market becomes more profitable (i.e., θ ₁ is higher), its marginal benefit starts to outweigh its marginal cost. Accordingly, the headquarters begins to allocate some capacity to Retail Branch 1 (i.e.,

a 1 P ( θ 1 ) > 0

) based on its market size, θ ₁. If θ ₁ belongs to the highest range, the headquarters wants to further increase the allocation to Retail Branch 1. This time, given the extremely scarce capacity relative to the market size of Retail Branch 1, the marginal benefit of additional unit to this retail branch is always higher that its marginal cost of reducing the reserved capacity for Retail Branch 2. Hence, the headquarters allocates all the capacity to Retail Branch 1.

When the available capacity is moderate (M/4 < K < M/2), the marginal cost of rationing becomes relatively cheaper, making the range of zero allocation smaller than the previous case. Furthermore, we see that the range of using up all the capacity for Retail Branch 1 disappears. This is because, when the available capacity is sufficient, it becomes impossible for Retail Branch 1 to be too attractive to take all the capacity. Lastly, when capacity is quite abundant (M/2 < K < M), it is sufficient enough to fulfill Retail Branch 1's actual need if it does not ask too much (i.e., when the market size θ ₁ is relatively small). Once θ ₁ becomes larger, allocation increases but the headquarters also begins to have more incentive to reserve capacity instead of fully satisfying Retail Branch 1's actual need. This is because the marginal benefit of an allocation keeps decreasing in the allocated amount, whereas the actual need is constantly increasing in θ ₁.

Based on the above observations, the following proposition summarizes key insights regarding the impact of the available capacity and the local market condition (market size) on the rationing incentives.

Proposition 3

Assume that there are two retail branches with linear demands, that is,

θ i − p i , i ∈ { 1 , 2 }

, where

θ i ∼ U ( 0 , M )

. Then, the following hold:

∂ 2 a 1 P ( θ 1 ) / ∂ θ 1 2 ≤ 0

. Equality holds if

θ 1 ∉ [ ( M − 2 K ) 2 2 M , min { 4 K + M 2 , M } ]

for the case of K < M/2; or if

θ 1 ∈ [ 0 , 2 K - M ]

for the case of K ≥ M/2.

∂ r 1 ( θ 1 ) / ∂ θ 1 ≥ ∂ a 1 P ( θ 1 ) / ∂ θ 1

. Equality holds if K > M/2 and θ ₁ < 2K−M.

Part (a) of Proposition 3 shows that Pareto sequential allocation is a concave function of θ ₁ except the extreme case (i.e., full rationing or no rationing). Part (b) of Proposition 3 then shows the gap between the retail branch's actual need and Pareto sequential allocation gets wider if the retail branch has a large market size

θ i

except for the case of allocating the actual need. This implies that the slope of Pareto sequential allocation is bounded from above. Hence, these results suggest that, for higher value of

θ i

, the curvature in Pareto sequential allocation might be low (i.e., similar to linear), and hence, it could be well approximated using a small number of linear pieces. On the other hand, when

θ i

is lower, part (b) of Proposition 3 also suggests that it may be necessary to include the case of fulfilling the actual order (and no rationing).

Simple Payment‐Based Allocation Mechanism. Motivated from these observations, we propose a simple variant of payment‐based allocation mechanism as follows: We determine the target allocation quantity and corresponding menu of side payments by separating the “two” cases—one for relatively lower

θ i

and the other for higher

θ i

. For the first part (lower

θ i

, and so lower actual need), we will impose no side payments and allocate exactly as orders (hence, allocate its actual need). For the second part, we approximate Pareto sequential allocation using a single linear function. We now illustrate how to determine the best menu of side payments under this two‐part simplification, under linear demand.

Formally, we consider a payment‐based allocation mechanism defined by

h i ( m i ; u i ) = min { m i , u i }

with the payment

s i ( m i )

as in Equation (10). We use two parameters to specify the menu of side payments: τ _i , the order quantity where the second part begins (with non‐zero side payments); and ξ _i , the slope of the linear target allocation for the second part which approximates Pareto sequential allocation. Clearly, the threshold τ _i can be chosen between 0 and u _i . For ξ _i , we note from Proposition 3 that the slope of Pareto sequential allocation is bounded above by

∂ r i ( θ i ) / ∂ θ i

(= 1/2) and non‐increasing in

θ i

. This suggests that it would be sufficiently effective to focus on the range of ξ _i up to

∂ r i ( θ i ) / ∂ θ i

(= 1/2) for the approximation. Also, we include the point ξ _i  = 0 by defining the menu of side payments at ξ _i  = 0; it can be done by modifying the payment level sufficiently high so that the retail branch chooses not to order beyond τ _i . With these, for our approximation procedure, we limit our attention to

ξ i ∈ [ 0 , 0.5 ]

. ¹⁷ Then, using the same idea discussed around Equation (9), the menu of side payments using these two parameters can be described as follows:

s i ( m i ) = 0 for 0 ≤ m i < τ i , 1 2 ξ i − 1 ( m i 2 − τ i 2 ) + max { θ ̲ , 2 τ i } − τ i ξ i ( m i − τ i ) for τ i ≤ m i ≤ u i .

10

Under this simple payment‐based allocation mechanism, Retail Branch i's ordering strategy (equivalently, allocation to Retail Branch i) is obtained in Equation (11). If the retail branch's market condition is small, there will be no side payment for ordering its actual need, so it is an optimal ordering strategy. If its market size belongs to the intermediate range, the retail branch orders an amount proportional to

θ i

with the slope ξ _i as a result of quadratic payment

s i ( m i )

. Lastly, if the market size is substantially high, the retail branch gets the entire portion of the available capacity, u _i , so no rationing occurs.

m i h ( θ i ) = θ i 2 for θ ̲ ≤ θ i < max { θ ̲ , 2 τ i } , ξ i θ i − max { θ ̲ , 2 τ i } + τ i for max { θ ̲ , 2 τ i } ≤ θ i < min { max { θ ̲ , 2 τ i } + u i − τ i ξ i , θ ¯ } , u i for min { max { θ ̲ , 2 τ i } + u i − τ i ξ i , θ ¯ } ≤ θ i ≤ θ ¯ .

11

We now discuss how to set the two parameters to optimize within the restriction. The optimal values for the two parameters, τ _i and ξ _i , can be obtained by solving Bellman equation for i = 1, 2, …, N. We use

a i ( θ i , τ i , ξ i )

to represent allocation to Retail Branch i. For the last retail branch indexed by N, the headquarters solves the following optimization problem:

( τ N * , ξ N * ) = arg max τ ∈ [ 0 , u N ] , ξ ∈ [ 0 , 0.5 ] E [ π N ( θ N , a N ( θ N , τ , ξ ) ) ] .

It is clear that

( τ N * , ξ N * ) = ( u N , 0 )

since there is no remaining retail branches and no benefit in not allocating capacity. Then, the total expected profit of retail branches whose indices are higher than i, denoted by

V i S ( u i )

, is determined by the following Bellman equation for i = 1, 2, …, N−1:

V i S ( u i ) = max τ ∈ [ 0 , u i ] , ξ ∈ [ 0 , 0.5 ] E π i ( θ i , a i ( θ i , τ , ξ ) ) + V i + 1 S u i - a i ( θ i , τ , ξ ) .

Therefore, for i = 1, 2, …, N−1, the solutions to the above problems for given available capacities u _i 's are determined as follows. ¹⁸

( τ i * , ξ i * ) = arg max τ ∈ [ 0 , u i ] , ξ ∈ [ 0 , 0.5 ] E π i ( θ i , a i ( θ i , τ , ξ ) ) + V i + 1 S u i - a i ( θ i , τ , ξ ) .

These optimal solutions for the two parameters define the optimal menu of side payments for each stage, and hence, the allocation mechanism will achieve the highest expected profit among all such two‐part simplified payment‐based allocation mechanisms. We call this Allocation Mechanism S.

Figure 2 contrasts the allocation outcomes from our two simple mechanisms, threshold‐type T and simple payment‐based S, against Pareto sequential allocation (first‐best), for a case with two retail branches. It clearly shows how closely S replicates the first‐best outcome well with only two simple linear parts. ¹⁹ Hence, an improved performance is expected for Allocation Mechanisms S. ²⁰ In the next section, we evaluate the performance of our two proposed allocation mechanisms through an extensive numerical study.

OPEN IN VIEWER

Figure 2

Comparison of Allocation Outcome for Retail Branch 1 between Allocation Mechanisms T and S: In Both Cases,

N = 2 , π i ( θ i , a i ) = ( θ i − a i ) a i

, and

θ i ∼ U ( 0 , 2 )

, K = 1 [Color figure can be viewed at wileyonlinelibrary.com]

Numerical Analysis

Our proposed mechanisms are designed to effectively capture the key characteristics of the rationing decisions observed in Pareto Sequential Allocation using a simple format. In this section, we study the performance of those two sequential allocation mechanisms via an extensive numerical experiment. We measure their performance relative to the first‐best outcome of sequential allocation (i.e., Pareto Sequential Allocation). In Sections 6.1 and 6.2, we summarize our experiment design and discuss the main results. Then, we analyze the impact of (i) scarcity of the total capacity, K, and (ii) variability in demand, on the performance of the two mechanisms in Sections 6.3 and 6.4, respectively.

Design of Numerical Analysis

In this numerical experiment, we consider problems with N ∈ {2, 3, 4} retail branches whose private information

θ i

follows a uniform distribution. ²¹

We fix the mean of the market size to be

E [ θ i ] = 5

and consider five levels of coefficient of variation (CV) of

θ i

such that CV ∈ {0.35, 0.40, 0.45, 0.50, 0.55}. Note that the CV of a uniform distribution with non‐negative support (i.e.,

θ i ≥ 0

) is bounded from above by 0.577

( = 1 / 3 )

. We thus set 0.55 as a maximum of CV in our experiment. ²²

For given N retail branches, we consider 10 different levels of capacity (K) such that:

K : = α · ∑ i = 1 N E [ r i ( θ i ) ] , where α ∈ { 0.1 , 0.2 , … , 1.0 } .

Note that

∑ i = 1 N E [ r i ( θ i ) ]

is the total expected actual need of all the retail branches. Therefore, α = 1 means that the initial capacity K is enough to satisfy 100% of expected actual needs of all retail branches. When

K > ∑ i = 1 N E [ r i ( θ i ) ]

, the initial capacity is not scarce, and therefore, capacity rationing is not critical for the performance of the allocation mechanisms—in our numerical analysis, if α > 1, expected profits from Allocation Mechanism T and S are at least 99.0% and 99.8% of the first‐best profit, respectively. Hence, we focus on the values of α which are at most 1. We summarize the set of parameters considered in our numerical experiment in Table 2. We examine total of 150 cases for this numerical experiment.

OPEN IN VIEWER

Table 2

The Set of Parameters Considered in Our Numerical Experiment

Number of retail branches (N)	Distribution of θ i	Mean of θ i ( E [ θ i ] )	Coefficient of variation (CV)	Capacity (K)	Number of instances
2				{0.5, 1.0, …, 5.0}
3	Uniform	5	{0.35, 0.40, 0.45, 0.50, 0.55}	{0.75, 1.5, …, 7.5}	50
4				{1.0, 2.0, …, 10.0}

Performance of Allocation Mechanisms T and S

We evaluate the performance of Allocation Mechanisms T and S by comparing the resulting expected profit of the firm against the first‐best outcome of sequential allocation (i.e., the firm's total expected profit under Pareto sequential allocation). ²³ Specifically, we use the following performance measure:

P T = Π T Π P × 100 ( % ) , P S = Π S Π P × 100 ( % ) .

The summary statistics of the above performance measures from our numerical analysis are shown in Table 3. We first observe that the averages of P _T and P _S indicate that both of the mechanisms perform well over many different parameter values. More importantly, they also suggest that the average profit loss is mostly a result of some small portion of extreme outliers. For this reason, we expect their performance in general could be better than what their averages suggest. To better evaluate their performances, it is important to identify what is driving those outlying low performances.

OPEN IN VIEWER

Table 3

Summary Statistics of the Performance of Allocation Mechanisms T and S: Performance is Measured relative to the First‐best Outcome (Pareto sequential allocation)

	Mean	Min	Q 1(25%)	Median	Q 3(75%)	Max
P T : Performance of T	92.83%	74.74%	89.39%	94.38%	97.84%	99.57%
P S : Performance of S	99.08%	91.88%	98.89%	99.84%	99.95%	100.00%

We find that both P _T and P _S are largely affected by the size of initial capacity (K) and number of retail branches (N), whose impact are quite intuitive. First, we see that the performance loss against the first‐best profit of sequential allocation reduces when the initial capacity becomes higher. On the flip side, having more retail branches lowers the performance of the mechanisms. These observations suggest that we might need a new measure that identifies a key factor that drives those variabilities in the performance. What we discuss next is about the new measure we introduce, which represents the scarcity of the initial capacity K relative to the number of retail branches N.

Impact of Scarcity on the Performance of Allocation Mechanisms T and S

Motivated from the previous observations, in this section, we define a measure that combines the impact of the initial capacity K and the number of retail branches N. Specifically, we focus on the impact of the scarcity of capacity that is measured by comparing the total capacity (K) and the total expected needs from N retail branches (

∑ i = 1 N E [ r i ( θ i ) ]

). We use λ to denote this measure, which is formally defined as follows:

λ = K ∑ i = 1 N E [ r i ( θ i ) ] .

From the parameter values used in our numerical experiment (Table 2), we have our scarcity measure λ vary between 0.1 and 1. A larger value of λ means the initial capacity is less scarce to satisfy the retail branches orders. For example, λ = 0.1 refers to an extreme situation where the total capacity satisfies only 10% of the total expected actual need of all retail branches, whereas λ = 0.8 is the case where the firm has the initial capacity that can cover 80% of the total expected actual need.

Figure 3 summarizes the performance of Allocation Mechanisms T (P _T ) and S (P _S ): it shows their average as well as the maximum and minimum performance relative to the first‐best outcome of sequential allocation. Specifically, part (a) of Figure 3 shows that Allocation Mechanism T performs reasonably well. For the scarcity measure higher than 60% (λ > 0.6), it achieves more than 95% of first‐best profit of sequential allocation. For a more scarce situation (0.4 ≤ λ ≤ 0.6), it achieves at least 90% of the first‐best outcome, on average. Our results shows that it may not perform well when the capacity is extremely scarce—when λ < 0.4, it drops below 90% relative to the first‐best profit.

OPEN IN VIEWER

Figure 3

Performance of Allocation Mechanisms T and S against Pareto Sequential Allocation. [Color figure can be viewed at wileyonlinelibrary.com]

The reason for this rapid drop could be explained as follows. Recall that a mechanism's performance loss relative to the first‐best profit is caused by the mismatch between the mechanism's allocation outcome and Pareto sequential allocation. Since lowering λ decreases overall fill rates of the retail branches, it results in a much larger marginal impact of an allocation on the retail branch's profit, hence the firm's profit as well (i.e., an increase in

∂ π i ( θ i , a i ) / ∂ a i

). In this case, the impact of a one‐unit deviation from Pareto sequential allocation on the performance can be intensified as λ decreases, thereby leading to a rapid drop in P _T .

Part (b) of Figure 3 reports the performance of Allocation Mechanism S against the case of the first best of sequential allocation. It shows that the performance of Allocation Mechanism S is quite impressive—except for the extremely scarce cases (where the scarcity is below 40%), it performs almost optimally, achieving more than 99% of the first‐best outcome of sequential allocation. Even in an unrealistic situation where the scarcity is only 10% (λ = 0.1), it achieves more than 95% optimality, on average. Similar to Allocation Mechanism T, we observe that its performance deteriorates rapidly for very small values of λ.

Again, the same argument applies here to explain the rapid drop in Allocation Mechanism S. However, as seen in Figure 2, Allocation Mechanism S is more effective in approximating Pareto sequential allocation, and hence, the degree of mismatch between its allocation outcome and Pareto sequential allocation could be minimal, making Allocation Mechanism S less vulnerable to the capacity reduction since it effectively approximates Pareto sequential allocation.

Remark 3

When a profit‐maximizing firm determines its capacity, it has to consider multiple factors including the profitability of the regional markets (e.g., their optimal demands). ²⁴ In practice, the expected values of the regional market sizes are often available to the firm and therefore, it could be rare that the initial capacity K is far from the expected value of the total actual need of those retail branches. In this regard, our proposed mechanisms are expected to perform well in practical settings. We believe that their good performance, together with their simple formats, make our proposed mechanisms particularly attractive in many practical applications.

Impact of Demand Variability on the Performance of Allocation Mechanisms T and S

We end this section by analyzing the impact of demand variability on the performance of Mechanisms T and S. We do this by comparing the performance over different CV's. Figure 4 summarizes the results of this numerical experiment. ²⁵ From this, we first observe that their performance measures P _T and P _S decrease in CV, which is intuitive as the increased variability with a fixed mean of

θ i

would only negatively affect the performance of a given mechanism. However, it is also observed that the impact is quite sensitive to the type of the mechanism and the scarcity level. Specifically, our Mechanism S which is capable of closely approximating the first‐best outcome has shown much milder impact with respect to CV compared to Mechanism T. In particular, Mechanism S is much less susceptible to CV at various levels of scarcity situations—even with significantly scarce capacity (λ ≤ 0.5), it still shows near‐optimal performance over all CV levels we considered. Mechanism T also reveals that its performance is quite robust to changes in CV unless the available capacity is extremely scarce (e.g., λ ≤ 0.3).

OPEN IN VIEWER

Figure 4

The Impact of CV on the Performance of the Two Allocation Mechanisms [Color figure can be viewed at wileyonlinelibrary.com]

Conclusion

In this study, we consider the capacity allocation problem of a multinational firm that allocates its limited production capacity to its retail branches. The allocation decisions have to be made in a sequential manner to each of the self‐interested retail branches who may strategically manipulate their order quantities. We develop sequential allocation mechanisms that can be effective in maximizing the firm's overall profit.

We first characterize the first‐best outcome of the sequential allocation, referred to as Pareto sequential allocation, by assuming that the firm knows the focal retail branch's private information when making the allocation decision. The first‐best allocation shows capacity rationing is essential for an effective allocation outcome. It also serves as the upper bound for the performance of our allocation mechanisms implemented in private information setting.

We then design a sequential allocation mechanism that does not involve any side payments. We propose a threshold‐type allocation mechanism, which has a simple format but enables the firm to ration capacity for the other retail branches who will order later by setting an upper limit for allocation. We show that this mechanism is optimal within the class of all allocation mechanisms that do not allow side payments. The simple structure of our optimal threshold‐type mechanism makes it practically appealing, and it will be particularly useful when the firm does not have a financial system to allow internal payments among its entities.

When internal payments among entities within the firm is viable, a mechanism with side payments could be implemented, which may achieve improved performance. Therefore, we also propose an allocation mechanism that involves side payments, where the menu of side payments is designed to induce the focal retail branch to order a certain target quantity to favor the firm's overall profit. One important methodological contribution of this work is that we use piecewise linear function to approximate Pareto sequential allocation which may not be available in closed form. Using the piecewise linear approximation, we derive a menu of side payments in closed form which induces a target quantity close to Pareto sequential allocation. We show that the performance of this payment‐based allocation mechanism converges to the first‐best outcome of the sequential allocation as the number of linear pieces increases.

The optimal payment‐based allocation mechanism might not be practical because of its complex structure of order‐dependent menu of side payments. We thus investigate a simplified form of the menu of side payments that may effectively capture key characteristics of the optimal menu of side payments and propose a simple payment‐based allocation mechanism with only a few parameters. Our extensive numerical study shows that this mechanism performs impressively well with over 99% optimality on average in realistic settings where the initial capacity is not extremely scarce.

Our work highlights the importance of understanding the retail branches’ strategic behaviors when the firm has to allocate capacity in a sequential manner. An important contribution of this study is that, our proposed mechanisms—the threshold‐type and simple payment‐based ones—have simple structures, hence, are easy to implement, but they also perform well. We hope that our study motivates subsequent and more active research on sequential allocation mechanisms in the literature.

Footnotes

Acknowledgment

This work was supported by Research Resettlement Fund for the new faculty of Seoul National University. Also, this work was partly supported by the National Research Foundation of Korea(NRF) grant funded by the Korea government(MSIT) (No. 2019R1F1A1047454).

For example, Monsanto operates its business in 66 countries and sells its products to over 160 countries (Dorich ).

When the swine flu was widespread in 2009, the outbreak date of each country varied (e.g., Mexico in May, Japan in June, India in July etc.; see, WHO () and Nature (2010) for the details).

See OECD () for more details.

An allocation scheme with information management could be considered in this type of settings (e.g., a signaling game approach between the headquarters and the retail branches). However, in our sequential setting, such a method is generally not tractable. Moreover, in a much simpler setting where it is tractable, a pooling equilibrium may exist, making it impossible for the headquarters to effectively overcome information asymmetry. Our optimal mechanism, on the other hand, effectively overcomes the information asymmetry, achieving the first‐best outcome.

We have conducted informal interviews with multiple managers in multinational firms in electronics and chemical industries. Many of them who are in charge of the firms’ allocation decisions emphasized the importance of using mechanisms in simple format, because otherwise, it would be too challenging for the retail branches to come up with optimal decisions. Moreover, they added that the use of complicated mechanisms might not be easily justified.

This type of mechanisms is often observed in practice. For example, in the energy industry, a mechanism with side payments is used when PJM Interconnection, a regional transmission organization in the United States, implements an auction to procure capacity of power supplies (PJM 2019). This type of mechanisms is also used within a firm. The headquarters of a US‐based semiconductor company imposes side payments on its production divisions when it matches demand from retail divisions with supply from production divisions (Mallik and Harker ).

Our model is general and also applicable to the problem of allocating a firm's inventory to its retail branches in a sequential manner.

Chen et al. (2013), Mallik and Harker (2004), and Karabuk and Wu () also examine this type of settings.

In our model,

θ i

can be viewed as any parameter specifying the local market condition.

We refer to Juarez () for a discussion about the benefit of assuming continuity in the outcome of a mechanism, for example, mitigating the adverse impact of misestimations. In this study, we develop mechanisms that are optimal in this broad class of mechanisms.

If Stage i sub‐mechanism requires a side payment, the effective profit of Retail Branch i is:

π i ( θ i , a i ) = ( θ i − a i ) a i − s i ( a i ) .

In this study, we focus on the situations where the demand arises sequentially across different retail regions. Hence, we assume that the market conditions of the retail regions are not revealed to the retail branches at time zero. For this reason, we define the first‐best allocation outcome in this way.

They also consider the trivial case that the total actual need is smaller than the initial capacity, that is,

∑ i r i < K

.

In our context, the role of side payments is to be used to ration limited capacity to maximize the overall firm profit by discouraging the retail branches’ order inflation incentive. Hence, it is enough to consider the side payments that are non‐negative.

To simplify the notation, it is implicitly assumed that the side payment of

s i ( m i )

is fully made when the order of

m i

is placed.

It is clear that attaining

a i P ( θ i )

is not possible if the retail branch orders (and receives) beyond y _n . We thus restrict our attention to the order

m i ∈ [ y 0 , y n ]

from this onwards. To do so, it is enough to impose sufficiently high payment for any

m i > y n

.

We also conducted extensive numerical experiment to support this. For all instances in the numerical experiment we considered, we find that approximation over

η i ∈ [ 0 , 0.5 ]

and

η i ∈ [ 0 , M ]

where M is sufficiently large yield the same expected total firm profit.

Both τ _i and ξ _i are independent of

θ i

since they should be determined before Retail Branch i's order is received.

This simplified approximation of the target allocation leads to a simple quadratic form of side payment menu as well. In this example, the side payment will be imposed only if m ₁ > 0.21 where the payment function can be specified with only two parameters, that is, s ₁(m ₁): = 0.34(m ₁−0.21)².

In fact, Allocation Mechanism T is a special case of Allocation S with infinite side payment beyond the threshold. Hence, its performance cannot be better than that of Allocation Mechanism S.

Uniform distribution is one of the commonly used distributions for modeling uncertainty of demand in many operations management literature (e.g., Perakis and Roels ). We have also conducted numerical analysis using truncated normal and gamma distributions, and the performance results are very similar to the uniform distribution case. We report the results from these additional cases in Appendix A.

In the additional numerical experiment with truncated normal and gamma distributions, we consider higher demand variability up to CV of 1.

In Appendix A, we also examine our mechanisms’ worst case performance ex post, which shows that the performance is quite robust over the realized type of the focal retail branch.

The firm's capacity decision is not the main focus of this study—we take it as a given parameter.

As the CV of a uniform distribution with non‐negative support is bounded from above by 0.577, we have also conducted a numerical experiment with truncated normal and gamma distributions to examine the impact of CV in high variation region (up to 1). Although we observe that a higher CV generates a more severe impact on the performances, the overall performance reduction due to increased variation remains not so significant. We provide this additional numerical study in Appendix A.

References

1.

Alonso R. Dessein W. Matouschek N. . 2008. When does coordination require centralization? Am. Econ. Rev. 98(1): 145–179.

Go to Reference

2.

Balcik B. Iravani S. M. R. Smilowitz K. . 2014. Multi‐vehicle sequential resource allocation for a nonprofit distribution system. IIE Trans. 46(12): 1279–1297.

Go to Reference

3.

Bassok Y. Ernst R. . 1995. Dynamic allocations for multi‐product distribution. Transport. Sci. 29(3): 256–266.

+ Show References

4.

Berman O. Larson R. C. . 2001. Deliveries in an inventory/routing problem using stochastic dynamic programming. Transport. Sci. 35(2): 192–213.

+ Show References

5.

Cachon G. P. Lariviere M. A. . 1999a. Capacity choice and allocation: Strategic behavior and supply chain performance. Management Sci. 45(8): 1091–1108.

+ Show References

6.

Cachon G. P. Lariviere M. A. . 1999b. An equilibrium analysis for linear, proportional and uniform allocation of scarce capacity. IIE Trans. 31(9): 835–349.

Go to Reference

7.

Caro F. Gallien J. . 2010. Inventory management of a fast‐fashion retail network. Oper. Res. 58(2): 257–273.

Go to Reference

8.

Chen F. Li J. Zhang H. . 2013. Managing downstream competition via capacity allocation. Prod. Oper. Manag. 22(2): 426–446.

+ Show References

9.

Chevaleyre Y. Dunne P. Endriss U. Lang J. Lemaitre M. Maudet N. Padget J. Phelps S. Rodriguez‐Aguilar J. Sousa P. . 2006. Issues in multiagent resource allocation. Informatica 30(1): 3–13.

Go to Reference

10.

Cho S.‐H. Tang C. S. . 2014. Capacity allocation under retail competition: Uniform and competitive allocations. Oper. Res. 62(1): 72–80.

Go to Reference

11.

Dorich A. 2016. Monsanto Co., Supply Chain World Magazine. Available at http://www.scw‐mag.com/sections/foodbeveragehospitality/698‐monsanto‐co (accessed date October 3, 2019).

Go to Reference

12.

Juarez R. 2018. Continuous mechanism design. Laslier J. F. Moulin H. Sanver R. Zwicker W. S. , eds. Future of Economic Design. Springer, Berlin.

Go to Reference

13.

Karabuk S. Wu S. D. . 2005. Incentive schemes for semiconductor capacity allocation: A game theoretic analysis. Prod. Oper. Manag. 14(2): 175–188.

+ Show References

14.

Kumar A. Schwarz L. B. Ward J. E. . 1995. Risk‐pooling along a fixed delivery route using a dynamic inventoryallocation policy. Management Sci. 41(2): 344–362.

Go to Reference

15.

Li Y. Xu X. Zhao X. Yeung J. H. Y. Ye F. . 2012. Supply chain coordination with controllable lead time and asymmetric information. Eur. J. Oper. Res. 217(1): 108–119.

Go to Reference

16.

Lien R. W. Iravani S. M. R. Smilowitz K. R. . 2014. Sequential resource allocation for nonprofit operations. Oper. Res. 62(2): 301–317.

+ Show References

17.

Liu Z. 2012. Equilibrium analysis of capacity allocation with demand competition. Naval Res. Logist. 59(3): 254–265.

+ Show References

18.

Mallik S. Harker P. T. . 2004. Coordinating supply chains with competition: Capacity allocation in semiconductor manufacturing. Eur. J. Oper. Res. 159(2): 330–347.

+ Show References

19.

Nature . 2010. Timeline: Swine Flu. Available at http://www.nature.com/news/2009/090429/full/news.2009.416.html (accessed date October 3, 2019).

Go to Reference

20.

OECD . 2012. Oecd Seed Schemes–a Synthesis of International Regulatory Aspects that Affect Seed Trade. Available at http://www.oecd.org/tad/code/internationalregulatoryaspectsseedtrade.pdf (accessed date October 3, 2019).

Go to Reference

21.

Papier F. 2016. Supply allocation under sequential advance demand information. Oper. Res. 64(2): 341–361.

+ Show References

22.

Perakis G. Roels G. . 2008. Regret in the newsvendor model with partial information. Oper. Res. 56(1): 188–203.

Go to Reference

23.

PJM . 2019. MJM manual 18: PJM Capacity Market. Available at https://www.pjm.com/‐/media/documents/manuals/m18.ashx (accessed date January 7, 2021).

+ Show References

24.

Reiman M. I. Rubio R. Wein L. M. . 1999. Heavy traffic analysis of the dynamic stochastic inventory‐routing problem. Transport. Sci. 33(4): 361–380.

+ Show References

25.

Reuter . 2009. Glaxo gets H1N1 Vaccine Orders. Available at http://uk.reuters.com/article/uk‐flu‐glaxo‐sbidUKTRE54E29K20090515?mod=related&channelName=worldNews (accessed date October 3, 2019).

Go to Reference

26.

Schjelderup G. Sorgard L. . 1997. Transfer pricing as a strategic device for decentralized multinationals. Int. Tax Publ. Finance 4(3): 277–290.

Go to Reference

27.

Wang S. Sun P. deVéricourt F. . 2016. Inducing environmental disclosures: A dynamic mechanism design approach. Oper. Res. 64(2): 371–389.

Go to Reference

28.

WHO . 2010. Pandemic H1N1 2009 ‐ Weekly Update. Available at http://www.who.int/csr/disease/swineflu/wer/en/ (accessed date October 3, 2019).

Go to Reference

29.

Zhang F. 2010. Procurement mechanism design in a two‐echelon inventory system with price‐sensitive demand. Manuf. Serv. Oper. Manag. 12(4): 608–626.

Go to Reference