UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Three essays in operations management Geng, Xin 2015

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
24-ubc_2015_september_geng_xin.pdf [ 941.64kB ]
Metadata
JSON: 24-1.0132752.json
JSON-LD: 24-1.0132752-ld.json
RDF/XML (Pretty): 24-1.0132752-rdf.xml
RDF/JSON: 24-1.0132752-rdf.json
Turtle: 24-1.0132752-turtle.txt
N-Triples: 24-1.0132752-rdf-ntriples.txt
Original Record: 24-1.0132752-source.json
Full Text
24-1.0132752-fulltext.txt
Citation
24-1.0132752.ris

Full Text

Three Essays in OperationsManagementbyXin GengB.Sc. (Mathematics), Zhejiang University, 2008M.Sc. (Mathematics), The University of British Columbia, 2010A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFDOCTOR OF PHILOSOPHYinThe Faculty of Graduate and Postdoctoral Studies(Business Administration)THE UNIVERSITY OF BRITISH COLUMBIA(Vancouver)June 2015c© Xin Geng 2015AbstractThere are three topics in operations management presented in this dissertation. Each topicdeals with a specific issue encountered by managers from various organizations.In the context of non-profit operations, we study a two-customer sequential resource al-location problem whose objective function has a max-min form. For finite discrete demanddistribution, we give a sufficient and necessary condition under which the optimal solution hasmonotonicity property. However, this property never holds with unbounded discrete distribu-tions.Then, we look at a service system with two servers serving arriving single class jobs. Serverscare about fairness, and they can endogenously choose capacities in response to the routingpolicy. We focus on four commonly seen policies and examine the two-server game where theservers’ objective functions have a term that reflects fairness. Theoretical results concerningthe existence and uniqueness of the Nash equilibrium are proved for some policies. Numericalstudies also provide insights on servers’ off-equilibrium behaviours and the system efficiencyunder different policies.Finally, suppose that a firm has heterogeneous servers who provide service with differentquality levels, and that there exists a learning curve of the servers so that the quality can beimproved by accumulating experience in serving customers. As customers decide their serviceprocurement based on the quality and system congestion, what pricing scheme should the firmadopt to achieve optimal revenue in the long run? We compare a traditional pricing schemewith a proposed one, and theoretically establish the superiority of the proposed pricing scheme.Based on both theoretical and numerical evidence, we characterize the sensitivity of someparameters with respect to the comparison.iiPrefaceChapter 2 and Chapter 3 are co-authored by my supervisors Tim Huh and Mahesh Nagarajan.In both chapters, I made the main contribution, which includes identifying the topics, developingthe models, carrying out the analysis and presenting them. A version of Chapter 2 has beenpublished (Geng, Huh, and Nagarajan, 2014a); Chapter 3 is forthcoming (Geng, Huh, andNagarajan, 2014b). Chapter 4 is authored by myself, but is also greatly benefited from mysupervisors’ insightful comments. This chapter will be modified and submitted for publicationin academic peer reviewed journals.iiiTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiAcknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiiDedication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 Sequential Resource Allocation With Constraints: Two-Customer Case . . 32.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32.2 Model Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.3 Structure of Optimal Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82.3.1 Example: Non-Monotonicity of x∗1(d1) . . . . . . . . . . . . . . . . . . . . 82.3.2 Bounded Discrete Distribution . . . . . . . . . . . . . . . . . . . . . . . . 112.3.3 Unbounded Discrete Distribution . . . . . . . . . . . . . . . . . . . . . . 162.4 Sensitivity in Initial Supply . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 Fairness Among Servers When Capacity Decisions Are Endogenous . . . . 193.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193.1.1 Literature Review . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213.2 Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233.2.1 Basic Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233.2.2 Individual Server’s Objective . . . . . . . . . . . . . . . . . . . . . . . . . 233.2.3 Routing Policies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263.3 Two-Server Game: Analysis and Results . . . . . . . . . . . . . . . . . . . . . . 283.4 Simulations and Discussions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313.4.1 Best Response Functions and Off-Equilibrium Behaviors . . . . . . . . . 31ivTable of Contents3.4.2 Comparison of Equilibria . . . . . . . . . . . . . . . . . . . . . . . . . . . 333.4.3 Comparison in Policy Performance . . . . . . . . . . . . . . . . . . . . . . 343.5 Summary and Extensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 364 Uniform Pricing in Service Systems With Experience Based Quality Im-provement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 384.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 384.2 Related Literature and Positioning . . . . . . . . . . . . . . . . . . . . . . . . . . 404.2.1 Our Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 424.3 Basic Model and Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 424.3.1 Customers’ Behavior . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 434.3.2 Firm’s Decision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 444.3.3 Assumptions in Multi-Server Case . . . . . . . . . . . . . . . . . . . . . . 454.4 Static Model Without Learning Effect . . . . . . . . . . . . . . . . . . . . . . . . 464.4.1 Differentiated Pricing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 464.4.2 Uniform Pricing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 474.4.3 Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 484.5 Dynamic Model With Learning Effect . . . . . . . . . . . . . . . . . . . . . . . . 494.5.1 Model Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 504.5.2 Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 524.5.3 Discussions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 534.6 How Do Parameters Affect the Revenue Difference? . . . . . . . . . . . . . . . . 554.6.1 Asymptotic Behavior . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 564.6.2 Impact of Learning Speed . . . . . . . . . . . . . . . . . . . . . . . . . . . 574.6.3 Impact of Heterogeneity . . . . . . . . . . . . . . . . . . . . . . . . . . . 594.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63AppendicesA Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70A.1 Proofs of Results in Chapter 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70A.2 Proofs of Results in Chapter 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72A.3 Proofs of Results in Chapter 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80B Detailed Computations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85vList of Tables3.1 Possible game outcomes. Entries with square brackets represent the intervalwhile those with parentheses represent the equilibrium. . . . . . . . . . . . . . . . 34viList of Figures2.1 Illustration of optimal allocations with different d1 . . . . . . . . . . . . . . . . . 92.2 Illustration for non-monotonicity of x∗1(d1) in d1 with three different ρ values.Second customer demand D2 is discrete uniform on {1, 4}, and s = 1. . . . . . . 102.3 Illustration for discontinuities in φ(d1) as a function of d1. Second customerdemand D2 is discrete uniform on {1, 2, 3}, and s = 1. . . . . . . . . . . . . . . . 142.4 Illustration for the monotonicity and lack of monotonicity. Second customerdemand D2 is discrete uniform on {1, 2, 3}, and s = 10 or s = 5. . . . . . . . . . . 153.1 Best response functions (Prop and HH). . . . . . . . . . . . . . . . . . . . . . . . 323.2 Best response functions (FSF and SSF). Linear segments on 45◦ line are not partof the functions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323.3 Performance of policies against fairness weight α(1)f with different costs. . . . . . 353.4 Performance of policies against extra cost ∆t. . . . . . . . . . . . . . . . . . . . . 364.1 The impact of servers’ learning speed on the revenue advantage: Dependence onT . Fix a1 = 1 and a2 = 7. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 584.2 The impact of servers’ heterogeneity on the revenue advantage. Fix T = 3 andδ = 1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 594.3 The importance of servers’ potential of improvement. Fix T = 3 and δ = 1. . . . 60viiAcknowledgementsThe research I have been involved for the past five years has been a great treasure for me.This dissertation, although hefty in weight, is merely a small portion of the product of thoseresearch activities. The largest and the most precious portion, however, is the issuing of anongoing professional and personal growth. Much of this growth is credited to the vast resourcesin the Operations and Logistic Division in Sauder School of Business at UBC. Indeed, I amgreatly thankful to many past/present faculties, staffs and graduate students in the division,who have been altogether my friends, teachers and mentors.I want to extend my gratitude to my dear supervisors, Tim Huh and Mahesh Nagarajan.From the very beginning, before I have any clue, they have designed an academic training forme that eventually turns out to be quite successful. Moreover, they have endured my stupidityand patiently supervised me in the course of all my research projects. I also appreciate all theencouraging words they spoke to me to keep me positive. Their generous financial support,even in my last year, is definitely a priceless contribution that I am deeply indebted to. Inall, they have been very inspiring role models to me. I wish that our friendship continues andmatures beyond my time at UBC.I also would like to thank Maurice Queyranne, Hong Chen, Martin Puterman and StevenShechter for offering the fundamental courses during my first year, which are quite helpful tome. In addition, I thank Harish Krishnan, Yichuan Ding and Hao Zhang for their insightfulcomments on my research; I thank Danielle van Jaarsveld for her willingness to serve as adissertation committee member; and I thank Anming Zhang for caring me and always superwarmly greeting me in the hall way.My final yet most important gratitude goes to my loving family. My wife has supportedme in every possible ways and sacrificed a lot so that I could pursue the doctoral degree. Herwillingness to talk about my research and even discuss ideas with me is truly precious to me.My parents also loved me without holding back. Even though they are thousands miles awayfrom me, I am certain that their hearts are with me and mine with them.viiiDedicationTo my wife 于湉and my parents 耿全合, 王亞萍ixChapter 1IntroductionThe area of operations management sees many interesting and challenging problems, whichattracts both researchers and practitioners. It is indeed an area where practical issues resort totheoretical resolution and the development of relevant theories is driven by real-life applications.In this dissertation, we focus on three topics in operations management that arise in practice.Each topic deals with a specific issue (resource allocation; employee fairness; pricing strategies)that is encountered by managers from either non-profit or profit-seeking organizations. Weapply analytical and numerical tools and methodologies to tackle these issues in order to gainuseful managerial insights. Moreover, we try to approach an operations management problemfrom an interdisciplinary standpoint, where concepts and assumptions from other managementareas, e.g. organizational behaviour and marketing, are introduced and utilized.In the first part of this dissertation, we study a two-customer sequential resource allocationproblem in the context of non-profit operations. Different from a profit maximizing goal, thenon-profit organization’s objective is to make the minimum fill rate (ratio of allocated amount todemand) of all agencies as large as possible. Given that the resource is limited and the agencies’demands are random and arrive sequentially in time, the manager’s decision is subject to a tradeoff: If he satisfies the current demand, then there may not be enough resource for the laterdemand, which could be large; if he reserve much resource, then the later demand may be smalland the left-over resource would be wasted.For this sequential resource allocation problem with a max-min objective function, we areprimarily interested in the structural properties of the optimal allocation policy, which is fullycharacterized by the allocation to the first agency as a function of its demand realization.Particularly, we ask the following question: If the realized demand is higher, do we alwaysallocate more? For finite discrete demand distribution, we give a sufficient and necessarycondition under which the optimal solution has monotonicity property. However, this propertynever holds with unbounded discrete distributions.The second part of this dissertation looks at a simple service system with two servers servingarriving jobs (single class). Our interest is in examining the effect of routing policies on serverswhen they care about fairness among themselves, and when they can endogenously choosecapacities in response to the routing policy. Therefore, we study the two-server game wherethe servers’ objective functions have a term explicitly modeling fairness. To mathematicallymeasure fairness, we turn to the equity theory, which was established in organizational behaviorand human resource literature. The application of equity theory in our setting epitomizes the1Chapter 1. Introductioninteresting research area at the interface of OM and OBHR.Focusing on four commonly seen policies that are from one general class, we theoreticallyprove the existence and uniqueness of the Nash equilibrium under two policies. By numericalmethods, we also draw several general conclusions concerning servers’ off-equilibrium behavioursunder the other two policies. In addition, we obtain some empirical patterns/properties for thegame outcome under these policies. Finally, we study, again numerically, how servers’ attitudestowards fairness and servers’ heterogeneity affect a policy’s performance in system efficiency.Finally, we study the revenue management problem for a service firm facing time-sensitivecustomers. The firm has heterogeneous servers who provide quality-differentiated services,where the quality can be improved based on accumulated experience. That is, servers learn bydoing and improve quality as serving more customers. Risk neutral customers decide whetherto procure the service based on the expected quality and congestion cost. In such settings, thetraditional pricing scheme, which we call differentiated pricing, posts prices on each servers andcustomers queue in front of their chosen servers. One unavoidable pitfall of this pricing schemeis that the low quality servers will suffer from slow improvement due to limited customervolume induced. To resolve this issue and take advantage of the servers’ learning effect, wepropose another pricing scheme, called uniform pricing, and prove that it collects equal orhigher revenue compared to differentiated pricing. Furthermore, we scrutinize the impact ofservers’ learning speed and their heterogeneity on the relative revenue advantage. Interestingand counter-intuitive results are shown by analytical and numerical approaches.The proposed uniform pricing scheme is essentially a type of probabilistic (opaque) sellingstrategy, which has recently been extensively studied in the marketing literature. By probabilis-tic (opaque) selling, the firm hides one or more attributes of the product until the transactionis complete. It has been commonly used in travel industries (hotel and airline) where customersmake purchases via an intermediary platform, e.g. Priceline and Hotwire, without prior knowl-edge of the brand name. In our study, the service attribute that uniform pricing hides fromthe customers is the quality. Our work is among the first to introduce probabilistic (opaque)selling to time-sensitive service settings; besides, we provide a new reason to advocate this newpricing strategy.Each of these three parts is self-contained and is developed based on different sets of assump-tions. The literature reviews, model formulations and conclusions are not repeated in separateparts. Yet, they all represent some interesting directions in the research body of operationsmanagement. The rest of the dissertation is organized so that each part is presented in onechapter, in the same order as in this chapter. All proofs are delayed to Appendix A.2Chapter 2Sequential Resource Allocation WithConstraints: Two-Customer Case2.1 BackgroundThe sequential resource allocation (SRA) problem has received much attention in literature. Inthis problem, a supplier has a limited but known quantity of resource available for allocation.Independent random demands arrive sequentially from a number of customers (or agencies),and the supplier needs to sequentially allocate the resource for each customer at a time. Whenallocating resource to a customer, the supplier sees the realization of the customer’s demand,but not the realization of remaining demands (the supplier knows only the distributions ofthe remaining demands). In other words, the decision of how much to allocate to the currentcustomer is made one at a time. Since the total amount of the resource is limited, the trade-offis usually whether to allocate it to the current customer or save it for future demands.Two types of objectives are commonly studied in this research area. The first type involvesmaximizing profit/revenue. The single resource capacity allocation problem in revenue manage-ment is a good example; see the first chapter of Talluri and Van Ryzin (2005) for the detailedstudy on the theoretical properties as well as useful heuristics. One specific such problem studiesairline seat allocation to customers with different fare classes. Brumelle and McGill (1993) andRobinson (1995) have provided a structural characterization for this problem, and approximatesolutions have been proposed, such as EMSR-a Belobaba (1987) and EMSR-b Belobaba (1989).The second type of objective in SRA problem does not explicitly model monetary pay-off.In such contexts, government-run companies or non-profit organizations often play the role ofsupplier, and they aim at enhancing the satisfaction level of the overall society rather thanprofit. While there are few papers taking such a perspective compared to the more typicalprofit-maximizing objective, there have been a number of papers advocating the necessity andurgency of studying non-profit logistics in the past couple of decades. In the context of publicservice such as education, emergent medical care and library supplies, Savas (1978) proposesand studies three measures of performance: effectiveness (how well the service is rendered),efficiency (ratio of service outputs to inputs) and equity (fairness or impartiality of service). Infact, the SRA problem arises naturally in the contexts such as healthcare allocation and fooddistribution. For example, Campbell et al. (2008) stress effectiveness by optimizing the arrivaltimes of the relief efforts in the aftermath of server disasters; Solak et al. (2012), focusing32.1. Backgroundon efficiency, minimize the service inputs of non-profit food distribution networks under aconstraint of fixed service output.In particular, Savas (1978) further claims that equity, among others, is of growing impor-tance that deserves more attention. This statement is still valid today, especially for resourceallocation problems; Bertsimas et al. (2012) study a class of efficiency-fairness objective func-tions and indicate applications in several contexts involving allocating resources. However, onlya limited number of papers incorporate fairness into the decision making on allocating capaci-ties. For instance, Alkan et al. (1991) explicitly bring up and discuss the fairness in allocationof indivisible goods. They consider a static (instead of sequential) allocation problem and theyinclude two kinds of resources. In the sequential allocation context, Swaminathan (2003) stud-ies the decision making in allocating scarce drugs, attempting to equalize the distribution ofdrugs amongst clinics without undermining the effectiveness and efficiency. More recently, LienLien (2008) models food donation delivery scheme over multiple customers as an SRA problem,and incorporates into the objective both equity and effectiveness. In this paper, we focus ourattention to SRA problems with equity (fairness) as the objective, and we refer to our problemthe equity based SRA problem.As one may imagine, the term equity is amorphous and its measurement varies according tothe context. There are numerous criteria of fairness in allocation problems proposed in manyliteratures. Although no single criterion is universally accepted in every setting, there are somegeneral theories on justice and fairness that serve as the basis of most fairness measures; seeBertsimas et al. (2012). We discuss three of them used in welfare economics. In welfare eco-nomics, the social welfare function (SWF) is a function from the vector space of feasible utilitycombinations of all the agents to the real numbers. A general form of SWF that incorporatesfairness measure is introduced in Atkinson (1970) and studied in many classic textbooks Barr(1993); Mas-Collel et al. (1995). It is parametrized by an real number ρ ≤ 1. To be specific, letU = (u1, · · · , un) be a utility vector of n agents, then this SWF has the formW (U) =(∑iuρi)1/ρfor ρ 6= 0, (2.1)andW (U) =∑ilog ui for ρ = 0.Searching for an allocation of utility to maximize W (U) is closely related to the three generaltheories and fairness criteria. The first one is utilitarianism. The key idea is simply to maximizethe summation of utilities, which corresponds to the case ρ = 1 in the above general SWF. Thiscriterion is criticised by some scholars (Young, 1995) as having ethical issues. Indeed, althoughit maximizes average utility, utilitarianism sometimes manipulates the allocation among agentsin a way that is contrary to the common sense of fairness. The second general theory originatesfrom game theory. Nash (1950) uses an axiomatic approach to characterize a cooperative two-42.1. Backgroundplayer bargaining game. The Nash solution, which is proposed in Nash (1950), is to maximizethe product of all the utilities (assuming that all utilities are positive). Hence, the general formof SWF with ρ = 0 is exactly this criterion. This criterion is discussed in many literatures. Forexample, Chevaleyre et al. (2005) call it Nash product and consider it better than utilitarianismin achieving fairness; Kelly et al. (1998) and Bertsimas et al. (2011) name it proportional fairnessand analyze it in telecommunication settings and resource allocation problems, respectively.The last general theory is proposed by Rawls (1971); hence the name Rawlsian justice. Theprinciple of Rawlsian justice is to make the minimum utility as large as possible. Note thatwhen ρ → −∞ in (2.1), W (U) equals the minimum utility. Therefore, maximizing the SWFin this case is to apply Rawlsian justice. This max-min criterion has been widely used in datanetwork (Bertsekas et al., 1992) and has initiated applications in bandwidth allocation problems(Bonald and Massoulie´, 2001; Luss, 1999) as well as general resource allocation problems (Alkanet al., 1991; Lien et al., 2008).In general, the different values of ρ indicate the different levels of inequity. The aversion toinequity increases as ρ decreases to negative infinity (Bertsimas et al., 2012; Lan et al., 2010;Mas-Collel et al., 1995). Hence, in the above three general theories, Rawlsian justice retains themost fairness. Moreover, Chevaleyre et al. (2005) define the worst utility as egalitarian socialwelfare, and they claim that it “offers a level of fairness and may be a suitable performanceindicator when we have to satisfy the minimum needs of a large number of customers” (p.17).This fits to our setting of non-profit food allocation very well. Consequently, we will use amax-min objective which is in line with the commonly used Rawlsian justice. In other words,our objective function is based on (2.1) with ρ → −∞. We will consider more general casesin Section 2.3.1 to show that our result also holds for finite negative ρ values; but we will notconsider the cases 0 ≤ ρ ≤ 1. Furthermore, we model the customer’s utility as the ratio of theallocated amount to the demand, which is named fill rate. Fill rate captures the proportionof demand satisfied for each customer, and customers tend to compare this measure with oneanother after allocation is completed. Indeed, both Lien (2008) and Swaminathan (2003) adoptthis measurement in their models, and we believe it is a suitable candidate and we employ itin our model as well.The SRA problem over multiple (more than two) periods is hard to solve in exact form due tothe curse of dimensionality. Many related works in literature search for reasonable heuristics bystudying the two-period special case. The doctoral thesis Lien (2008) is an example and is closestto our work. Lien formulates the SRA problem with an equity based objective as a dynamicprogram and develop some structural properties for the two-period case. Then, he proposes a“two-node-decomposition” heuristic which solves the large size problem by decomposing it intoseveral two-period subproblems. Using the structural results discovered, he manages to solvethose subproblems. In this paper we explore the two-customer case in great detail. We presentan exact expression of the optimal solution when demand follows a discrete distribution. Ourpurpose here is to study the properties of this special case as it is important for gaining insight52.2. Model Formulationand generating heuristics - our results can be used, for example, in each two-period subproblemof Lien’s decomposition heuristic.Therefore, our work adds to this body of research by providing more theoretical resultsconcerning the basic structure of the optimal solutions. The limitation of two-customer specialcase notwithstanding, our results provide a reference for further theoretical studies as well asheuristic development. In addition, our contribution differs from that of the theoretical work onprofit-based SRA, e.g. Brumelle and McGill (1993); since the objective functions have differentforms and properties, their results or methods are not directly applicable in studying equitybased SRA.2.2 Model FormulationIn this section, we formulate the SRA model. A supplier needs to allocate to N customerswith a fixed amount s of resource. The customers are sequentially ordered. Each customer’sdemand is random and will be known to the supplier only after all demands of the previouscustomers have been realized and allocation decisions to those customers have been made, butbefore the allocated amount to him is decided. As discussed in the previous section, we aim tomaximize the minimal fill rate of all customers to achieve Rawlsian justice. Since the demandsare random, our objective is therefore to maximize the expected minimum fill rate over allthe customers. In this paper, we focus on the two-customer case only. Studying this specialcase simplifies the problem while keeping the inherent challenges of sequential decision making.Besides, it is straightforward to extend some of the main results to multiple customers. Hence,we aim at finding structural properties that help understanding the N -customer case.As a result, the optimization problem has one decision variable: the allocation to customer1. The second customer will receive what is left. Let xi (i = 1, 2) be the allocation to customeri. Since x2 = s − x1, x1 is the only decision. Let Di (i = 1, 2) be the random variablerepresenting demand from customer and di (i = 1, 2) be the realized demand. Throughout thispaper we assume that the two demands are independent (but not necessarily identical), whichis commonly assumed in literature. Moreover, we assume that Di > 0 (i = 1, 2) almost surely.Then, the fill rate takes the form of xi/Di (i = 1, 2).Let a∧ b represents min{a, b}. Given an initial supply s > 0 and a realized first demand d1,defineR(x1, d1) = ED2(x1d1∧ s− x1D2)(2.2)to be the expectation of the minimum of the two fill rates, where 0 ≤ x1 ≤ d1 and theexpectation is taken with respect to D2. It is straightforward to see that function R(x1, d1) isjointly concave in x1 and s. Further, letv(s, d1) = max0≤x1≤min{s,d1}R(x1, d1) , (2.3)62.2. Model Formulationthen the optimal expected minimum fill rate is given byu(s) = ED1v(s,D1) .Since x1 is decided after D1 is realized, we need only to focus our attention on the randomvariable D2 and how it affects the structure of the optimal decision conditioned on the therealized value of the first demand d1.Our interest, therefore, is in solving (2.3). Let x∗1 = x∗1(d1) be an optimal solution to (2.3).Note that the constraint x1 ≤ d1 simply says that there is no need to give the first customermore than demanded. As a result, v(s, d1) cannot exceed 1. Equivalently, one can remove theconstraint x1 ≤ d1 and modify the objective function as ED2(1 ∧ x1d1 ∧s−x1D2)(see Lien (2008)for an example). Although they are equivalent formulation, we will use the former objectivefunction, which turns out to be easier to work with. To further simplify the problem, we enlargethe feasible region for x1 in (2.3), and consider the following relaxed problem.v˜(s, d1) = max0≤x1≤sR(x1, d1) . (2.4)Let φ(d1) be an optimal solution to (2.4),φ(d1) ∈ arg max0≤x1≤sR(x1, d1).Comparing the two problems, the feasible region in (2.4) is not bounded by d1. Therefore,x∗1(d1) is at most d1 while φ(d1) may exceed d1; similarly, v(s, d1) is bounded above by 1 whilev˜(s, d1) may exceed 1. However, the two problems are closely related. In fact, if φ(d1) ≤ d1,then it is easy to see that the relaxed problem has an optimum that is feasible for the originalproblem so x∗1(d1) = φ(d1). Otherwise, if s ≥ φ(d1) > d1, then by concavity of R(x1, d1), theobjective function is increasing in x1 on the interval [0, φ(d1)]. Hence it is also increasing on[0, d1], which implies that the optimum of the original problem is achieved at the boundary d1,i.e., x∗1(d1) = d1. To summarize, we always have v(s, d1) ≤ v˜(s, d1) andx∗1(d1) = φ(d1) ∧ d1. (2.5)For our SRA problem, we are primarily interested in the optimal allocation policy ratherthan the optimal value of the objective function. To understand the structure of x∗1(d1), it isconvenient for us to first study φ(d1) in the relaxed problem (2.4) since we can recover theinformation about the optimal allocation through (2.5). To the best of our knowledge, thismethod of relaxation has not been used in such equity based SRA problem before. It bearsnoting that it is possible that, for fixed s, φ(d1) has multiple values for a specified d1. This isbecause the objective function is not strictly concave. However, we need φ(d1) to be a functionof d1 so that we can perform analysis on the structural properties. To circumvent the difficulty,we have to predefine which optimal value φ(d1) takes if there are many. One way of doing this72.3. Structure of Optimal Solutionis to assign the smallest value of all the optima to φ(d1).From the formulation of problem (2.4), we make several observations. First, the predeter-mined distribution of D2 plays an important role in that it completely determines φ(d1) withfixed s and d1. Second, if we increase the supply s, we not only increase the objective valuebut also increase the feasible region. It then follows that the optimal value v(s, d1) is increas-ing in s. This makes sense in the context. The more the initial supply is, the more we cangive to satisfy the two demands, and thus the larger the fill rates. Third, if the realized valued1 become higher, then R(x1, d1) and subsequently v˜(s, d1) become lower. Other comparativestatics results may not be obvious, and one of the questions that we are interested is: whathappens to the optimal allocation as d1 increases? In other words, if the realized demand d1 ishigher, do we always allocate more to the first customer? This is one of the research questionsanalysed in this paper, and is discussed in the next section. All detailed proofs of our resultsare presented in Appendix A.1.2.3 Structure of Optimal SolutionSince the optimal allocation x∗1 depends on the realization of the first demand d1 and the initialsupply s, we now study the structure of x∗1(d1). To simplify analysis and notation, we supposethe supply s is fixed throughout this section, and omit s in the functions defined in Section 2.2;for example, we write x∗1(d1) instead of x∗1(d1). We then ask how x∗1 depends on d1. Preliminaryintuition drives us to believe that the larger d1 is, the more we should allocate to it, resultingin larger x∗1. This is asserted as being true in Lien (2008) and later corrected in Lien et al.(2008). In this section, we provide another example where this is not true and provide sufficientconditions under which this assertion is true.2.3.1 Example: Non-Monotonicity of x∗1(d1)Suppose the second period demand D2 is such that D2 = 1 or 4 with equal probability. Let theinitial supply s = 1. We then compute the optimal allocation for two cases, in which d1 = 3and d1 = 5, respectively. Using (2.2) and some algebra, we haveR(x1, 3) = ED2(x13 ∧1− x1D2)= 12(x13 ∧ (1− x1))+ 12(x13 ∧1− x14).82.3. Structure of Optimal SolutionNoting that the two expressions in the above big parentheses are piecewise linear, we can writeR(x1, 3) asR(x1, 3) =x13 0 ≤ x1 <37x124 +1837 ≤ x1 <3458(1− x1)34 ≤ x1 < 1 .Therefore, maximizing R(x1, 3) over the interval [0, 1] yieldsx∗1(3) =34 = 0.75.See Figure 2.1 for an illustration.0 0.2 0.4 0.6 0.8 100.020.040.060.080.10.120.140.16 x1R(x 1,3)x1∗=0.75(a) Objective Function with d1 = 3: R(x1, 3)0 0.2 0.4 0.6 0.8 100.020.040.060.080.10.12 x1R(x 1,5)x1∗ =0.56(b) Objective Function with d1 = 5: R(x1, 5)Figure 2.1: Illustration of optimal allocations with different d1Likewise we can write R(x1, 5) asR(x1, 5) =x15 0 ≤ x1 <59−x140 +1859 ≤ x1 <5638(1− x1)56 ≤ x1 < 1and obtainx∗1(5) =59 ≈ 0.56.Hence, x∗1(5) < x∗1(3). This shows that x∗1(d1) may not be increasing in d1. Interestingly, similarexamples can be constructed to show the non-monotonicity using the general form of objectivefunction (2.1) with ρ < 0. Some of these examples are as follows.92.3. Structure of Optimal SolutionThe general form of the objective function is given byR(x1, d1) = ED2((x1d1∧ 1)ρ+(s− x1D2∧ 1)ρ)1/ρConsider the function W (U) in (2.1) and the case n = 2. By verifying the second ordercondition, we see W (U) is concave. Besides, it is also increasing in each component. R(x1, d1)is the expectation of a composition of W (U) and two concave functions. Hence it is concavein x1 on [0, s]. Therefore, we can define x∗1(d1) in the same way as we did in Section 2.2. Nowwe construct examples which show that x∗1(d1) is not necessarily increasing in d1. Suppose D2is uniform on {1, 4}, and s = 1. We then plot the x∗1(d1) over 1 ≤ d1 ≤ 5 for three differentρ values (ρ = −6,−8,−10). See Figure 2.2. A non-monotonic trend can be clearly seen in1 2 3 4 50.450.50.550.60.650.70.75d1x∗  ρ=−6ρ=−8ρ=−10Figure 2.2: Illustration for non-monotonicity of x∗1(d1) in d1 with three different ρ values.Second customer demand D2 is discrete uniform on {1, 4}, and s = 1.all three curves, indicating that x∗1(d1) is not necessarily increasing in d1. In fact, as the ρvalue decreases the non-monotonicity remains, and the curve becomes more alike the one whereρ → −∞.The above examples indicate that the relation between x∗1 and d1 may be counter-intuitive.This result depends on the distribution of D2 and the amount of the initial supply. If theresource is limited in amount, then the supplier needs to make a choice between allocating tothe first customer and saving for the later demand. As a result, the supplier may increase x∗1as d1 gets larger but may also want to reserve more for the second customer as d1 increases tosome level, leading to a decrease of x∗1. This trade-off is affected by the distribution of seconddemand. Sometimes it is better to increase x∗1 whereas other times saving more for the seconddemand is optimal even when d1 is increasing. Generally speaking, for a distribution whosedensity function has several “bumps”, i.e. points with similarly large densities, it is likely thatx∗1 is not overall monotonic in d1. In the above example, D2 follows a discrete distribution,which is an extreme case where densities become point masses. However, we want to stress that102.3. Structure of Optimal Solutiondemand being discrete is not the inherent reason for non-monotonicity. Examples showing thenon-monotonicity of x∗1(d1) can also be constructed using a continuous distribution for D2 byfollowing a similar intuition. Under discrete distributions the analysis is cleaner and we keepthis assumption for the remainder of this section. We will investigate conditions under whichmonotonicity holds.2.3.2 Bounded Discrete DistributionThis subsection studies the case where D2 has a bounded discrete distribution. Throughoutthis subsection, we make the following assumption, which is satisfied by many commonly useddistributions such as discrete uniform and binomial.Assumption 2.3.1. D2 has a discrete distribution with finitely many realizations.Let the probability mass function of D2 be given byP(D2 = ak) = pk, k = 1, 2, · · · , n.We assume that0 < a1 < a2 < · · · < an. (2.6)Once the distribution is given, we want to write the objective function in an explicit way.First, if x1 has been allocated to the first customer, then the minimum fill rate conditioned onthe realized value D2 = ak (k = 1, 2, · · · , n) is given byfk(x1, d1) =(x1d1∧ s− x1D2)∣∣D2=ak =x1d1∧ s− x1ak.As a minimum of two linear functions with different slopes, each fk is a piecewise linear concavefunction of x1. In addition, the break point that connects the two pieces is exactly the x1 thatmakes the two expressions for the minimum operator equal, i.e, x1/d1 = (s− x1)/ak. It can beshown that the break point is given byzk = zk(d1) =sd1d1 + ak. (2.7)Note that while each break point zk is a function of d1, it is bounded above by s. Thus, zk canbe interpreted as the allocation amount that equalizes the fill rates of both customers in caseof D2 = ak. Now, having defined {zk}, we can write fk explicitly asfk(x1, d1) =x1d1if 0 ≤ x1 ≤ zks− x1akif zk ≤ x1 ≤ s .(2.8)Thus, we obtain that fk is increasing on [0, zk] and decreasing on [zk, s], and x1 = zk =sd1d1 + ak112.3. Structure of Optimal Solutionmaximizes fk(x1, d1) for each k.We now proceed to the objective function in problem (2.4), by considering D2 as a randomvariable. Taking the expectation with respect to D2, we obtainR(x1, d1) =n∑k=1pkfk(x1, d1).Recall that the value of d1 is realized before x1 is decided. Since every fk is a piecewise linearconcave function of x1, their convex combination R(x1, d1) is also a piecewise linear concavefunction in x1. Moreover, the set of all the break points of R(x1, d1) is exactly {zk : k =1, 2, · · · , n}. Since the sequence of ak’s is increasing in k, it follows from (2.7) that the breakpoints are strictly monotonic with0 < zn < · · · < z1 < s . (2.9)It is convenient to define z0 = s and zn+1 = 0. Then, we can derive the analytic form of eachlinear piece by expanding (2.8) for every k = 1, 2, · · · , n+ 1:R(x1, d1) =k−1∑j=1pj1d1−n∑j=kpjajx1 +n∑j=ksaj, (2.10)for zk ≤ x1 < zk−1.We are interested in how the optimal solution depends on the value of d1. To examine theimpact of d1 on the maximizer of R(x1, d1), we first find the optimal solution φ(d1) of problem(2.4). There may exist multiple optimal solutions, in which case we predefine only one of themin order that φ(d1) is uniquely defined as a function d1; letφ(d1) = inf arg max0≤x1≤sR(x1, d1).Due to the concavity and piecewise linearity of R(x1, d1), we know that the point whose leftderivative is positive and right derivative is non-positive achieves the maximum, and is φ(d1).To find such a point, we examine the slope of each linear piece in (2.10) in the order of k =n + 1, n, · · · , 1, and look for the first one that is less or equal to zero. Suppose the piececorresponding to [zk, zk−1) is the first one, then φ(d1) = zk by our predefined specification.(Note that k 6= n+1 because the leftmost piece has strictly positive slope.) Hence, the optimalsolution φ(d1) must be one of the n break points {zk}, i.e.,φ(d1) = zk(d1), for some k = 1, 2, · · · , n.Hence, knowing how d1 affects zk directly helps us know how d1 affects φ(d1). From theabove reasoning, the choice of the optimal zk depends on the signs of the slopes of the linear122.3. Structure of Optimal Solutionpieces. From (2.10), we see that the slope is closely related to d1. To reveal how the value ofd1 determines the slopes, we introduce a sequence of thresholds for d1, each of which sets thecorresponding slope in (2.10) to zero. Defineθk =∑k−1j=1 pj∑nj=k pj/aj, for k = 2, 3, · · · , n. (2.11)It is straightforward to verify that if d1 < θk, then R(x1, d1) is increasing in x1 on [zk, zk−1); ifd1 > θk, then R(x1, d1) is decreasing in x1 on [zk, zk−1). If d1 = θk, then R(x1, d1) is constantfor x1 in [zk, zk−1).Note that these threshold points depend only on the distribution of D2, and therefore arepredetermined. From the definition of θk’s in (2.11), it can be seen that as we increase d1, theslope of R(x1, d1) in the interval [zk, zk−1) changes its sign as d1 crosses θk. This is significantin the following two ways: (i) a small change in d1, not crossing any of the θk thresholds,keeps the sign of R(x1, d1)’s slope unchanged (either negative or positive) within [zk, zk−1) eventhough the exact value of zk and zk−1 changes; (ii) when the increasing d1 crosses θk, thesign of R(x1, d1)’s slope in the interval [zk, zk−1) changes (from positive to negative), and themaximizer of R(x1, d1) shifts from zk−1 to zk. We formalize these observations below.Define θ1 = 0 and θn+1 = ∞. It follows directly from the definition in (2.11) that0 = θ1 < θ2 < · · · < θn < θn+1 = ∞. (2.12)The following lemma characterizes φ(d1), the optimal solution to (2.4) as a function of therealized demand of the first customer. The signs “+” and “−” in the function expressionmeans the right and left limits, respectively.Lemma 2.3.2. Given Assumption 2.3.1, the function φ(d1) is concave and increases in d1 ford1 ∈ [θk, θk+1). In addition, for k = 2, 3, · · · , n, φ(d1) is discontinuous at each d1 = θk, and wehave φ(θk−) > φ(θk+).To visually illustrate Lemma 2.3.2, we give Figure 2.3 as below. Suppose that P(D2 =i) = 1/3 for i = 1, 2, 3, and s = 1. As above lemma shows, that the relaxed solution φ(d1)is well-behaved except at some predetermined threshold points. As d1 increases, φ(d1) is bothincreasing and concave in each of the interval; however, at each threshold, φ(d1) makes adownward jump.As discussed in Section 2.2, the optimal allocation is related to the relaxed solution φ(d1)through (2.5), i.e.x∗1(d1) = φ(d1) ∧ d1.Then, from Lemma 2.3.2, we immediately have the following corollary.Corollary 2.3.3. Given Assumption 2.3.1, the optimal allocation x∗1(d1) is a piecewise contin-uous function of d1; moreover, it is increasing and concave in d1 on each piece. However, at132.3. Structure of Optimal Solution0 2 4 6 8 1000.20.40.60.81d1φRelaxed Solution with s=1θ2 θ3Figure 2.3: Illustration for discontinuities in φ(d1) as a function of d1. Second customer demandD2 is discrete uniform on {1, 2, 3}, and s = 1.every discontinuity, if there is any, x∗1(d1+) < x∗1(d1−).From the last statement in Corollary 2.3.3, it is shown that the monotonicity of x∗1(d1) in d1requires no discontinuity in x∗1(d1). The question now is when exactly there is no discontinuity,i.e., when x∗1(d1) is overall increasing and concave in d1. From (2.5), x∗1 is the smaller of (i)φ(d1) and (ii) the function x∗1 = d1, whose image is the 45◦ line in a demand-allocation graph(e.g., the dot line in Figure 2.4). This 45◦ line represents the level of allocation that fullysatisfies the first customer; therefore this line will be referred to as fulfilment line henceforth.Obviously, the fulfilment line is continuous and increasing. Hence, roughly speaking, we wantall the n − 1 discontinuous points of φ(d1) to lie on or above the fulfilment line, so that theywill not be part of x∗1.Figure 2.4 shows an example picture that illustrates our point. Again, we use the distributionP(D2 = i) = 1/3 for i = 1, 2, 3. For the left graph (Case A), we use s = 10 while for the rightgraph (Case B), s = 5. As noted, the optimal allocation is the lower part of the relaxed solutionand fulfilment line. Hence, x∗1 is continuous in Case A but not in Case B.The following theorem identifies conditions for the monotonicity and concavity of x∗1(d1) ind1.Theorem 2.3.4. Under Assumption 2.3.1, a necessary and sufficient condition for x∗1(d1) tobe overall increasing and concave in d1 is that the initial supply s satisfiess ≥ θn + an. (2.13)This theorem shows that when the initial supply is sufficiently large, the optimal allocationis strictly increasing with the first customer’s demand. Consider what would happen to theamount, x1, allocated to customer 1 as the demand d1 increases. The supplier balances theimpact of the following two actions: (i) increasing x1 to allocate more to the first customer,142.3. Structure of Optimal Solution0 2 4 6 8 100246810d1  Relaxed Solution φFulfilment LineOptimal Allocation x∗1(a) Case A: s = 100 2 4 6 8 100246810d1  Relaxed Solution φFulfilment LineOptimal Allocation x∗1(b) Case B: s = 5Figure 2.4: Illustration for the monotonicity and lack of monotonicity. Second customer demandD2 is discrete uniform on {1, 2, 3}, and s = 10 or s = 5.and (ii) reserving more for the second customer by decreasing x1. (See our discussion follow-ing the definitions of θk’s in (2.11)). Theorem 2.3.4 simply states that as long as the initialsupply is sufficient enough to meet the first demand up to θn (the highest level of d1 for thesupplier to consider the effect of (ii)) and the second demand up to an (the largest realizationof D2), respectively, the supplier can always allocate more to the first customer as d1 increases.Conversely, the reason why the allocation x1 could decrease even as d1 is increasing is thatthe initial supply is limited – since the supplier’s action makes a more significant impact oncustomer 2’s fill rate.Alternately, the condition in Theorem 2.3.4, equation (2.13), can be written as followingusing equation (2.11):s ≥(∑n−1j=1 pjpn+ 1)an.Let β =∑n−1j=1 pjpn + 1. Then, β is a constant that is completely determined by the distributionof D2. Hence, the inequality s ≥ βan reveals the interrelationship between the supply and thesecond distribution in affecting the structure of optimal allocation as a function of the firstdemand. Furthermore, under many commonly seen distributions, the factor β is likely to bemore than 2 because pn is generally smaller than 1 − pn. Therefore, if we let D1 and D2 beidentically distributed and β > 2, then the above condition means that the initial supply issufficient enough to meet both customers’ largest demands, which is why the supplier will nothave to worry about facing a large demand in the future while he increases x1.In summary, Theorem 2.3.4 tells us sufficient initial supply leads to an increasing optimalallocation function. Besides, the distribution of D2 also plays a key role in that it determinesboth θn and β. Note that condition (2.13) is possible to hold for some s because the realized152.3. Structure of Optimal Solutiondemands are bounded; cf. Section 2.3.3.Recall from the definition of x∗1 in (2.5) that x∗1 is the minimum of two functions, φ and theidentity mapping. The condition in Theorem 2.3.4 ensures that the points of discontinuity inφ(d1) are not the points of discontinuity in x∗1(d1), and thus x∗1(d1) is overall continuous. Mean-while, we are interested to see when the function x∗1(d1) would be determined by φ(d1) instead,i.e., x∗1(d1) = φ(d1). In this case, x∗1(d1) becomes discontinuous at every θk (k = 2, 3, · · · , n).Besides, the optimal allocation stays below the fulfilment line; i.e., the first customer is neverfully satisfied. Intuitively, this would happen when the second period demand is much largerthan the initial supply. Because the second customer’s fill rate will never reach 1, there is noneed for the supplier to allocate to the first customer the full demanded amount, regardlesshow small it is. The above intuition is verified in the following proposition.Proposition 2.3.5. Suppose that Assumption 2.3.1 holds. If s ≤ a1, thenx∗1(d1) = φ(d1) < d1 for d1 > 0.If the initial supply is neither too large nor too small compared to the second demand (thusTheorem 2.3.4 and Proposition 2.3.5 are inapplicable), we have to combine equation (2.5) andLemma 2.3.2 to see where x∗1 is increasing in d1 and where the discontinuous downward jumpoccurs.2.3.3 Unbounded Discrete DistributionIn the earlier discussion, an (the maximum possible value of D2), has played an important rolein characterizing the monotonicity condition for the optimal allocation. In fact, an being finiteis the main reason why inequality (2.13) can hold for some s. This subsection focuses on thecase where the second period demand is discrete but unbounded (e.g. Poisson distribution).Again, we use this assumption throughout this subsection.Assumption 2.3.6. D2 is discretely distributed, and P(D2 > M) > 0 for any M ≥ 0.We will still use the same notations as defined in the previous subsection, with slight mod-ifications to adapt to the unbounded case in this subsection. To be specific, instead of beingfinitely many, all sequences {ak}, {zk} and {θk} have infinitely many points. For instance, theprobability mass function of D2 becomesP(D2 = ak) = pk > 0, k = 1, 2, · · ·with {ak} strictly increasing to +∞. Besides, θk now takes the form thatθk =∑k−1j=1 pj∑∞j=k pj/aj.162.4. Sensitivity in Initial SupplyNote that θk is well-defined because the series in the denominator converges. Moreover, it canbe shown that each θk is finite, but {θk} is an increasing and unbounded sequence of positivenumbers.Because of the infinitely many break points {zk} of the objective function, the functionφ(d1) now has infinitely many continuous pieces. Each of the piece is strictly increasing andconcave in d1, and each discontinuous point sees a decrease in function value. In other words,Lemma 2.3.2 basically remains the same under Assumption 2.3.6, except that there are nowinfinitely many θk’s. In contrast, for the optimal allocation x∗1, there is an interesting differencefrom Theorem 2.3.4. The condition (2.13) in the previous case holds for some s, whereas itcan never hold for any s in the unbounded case, simply because s can never be larger thanthe “largest” demand realization. Therefore, the overall continuity can never happen underAssumption 2.3.6. We present it as the next theorem.Theorem 2.3.7. Under Assumption 2.3.6, given any initial supply s, there exists d¯1 > 0 suchthat x∗1(d1) is discontinuous at d1 = d¯1. Moreover, x∗1(d¯1−) > x∗1(d¯1).The above theorem shows that the unboundedness of D2 (Assumption 2.3.6) plays animportant role. Suppose that the increment from ak−1 to ak remains constant for each k.Then, it can be seen from the proof of Theorem 2.3.7 that zk(θk) → s as d1 → +∞ for everyk, we know that the discontinuity gaps of φ(d1) become smaller as d1 gets larger. However,because the distribution is discrete, there are always positive gaps. This leads to the inevitablediscontinuity of the optimal allocation. The discussion under Theorem 2.3.4 shows that if theoptimal allocation is continuous in all d1 > 0, then the initial supply must be large enoughcompared to the second demand. Hence, under unbounded assumption, it is expected thatcondition (2.13) will never hold because the probability of D2 being very large is positive ands cannot exceed it.Meanwhile, Proposition 2.3.5 continues to hold. This is because the result depends on therelationship between the initial supply and the smallest realization of the second demand, a1.Since a1 is a fixed finite number, unless a1 = 0, there exists some s > 0 such that s ≤ a1.2.4 Sensitivity in Initial SupplyIn the following, we briefly discuss how the change of the initial supply affects the optimalallocation. To that end, assume s is not fixed any more. As a result, all the functions definedin previous sections become functions of two variables, namely, the first demand d1 and theinitial supply s. Therefore, the optimal allocation x∗1 depends on both s and d1 now. In theSRA setting, s is decided before any realization of demands, so the results are mainly for thesake of ex ante sensitivity analysis.Let x∗1(d1) and φ(s, d1) be the optimal allocation and the optimal solution to problem (2.4),respectively. Assume that the second period demand is still discrete. We claim that under thisassumption, the initial supply s can be factored out so that φ(s, d1) is linear in s. To see this,172.4. Sensitivity in Initial Supplywe consider problem (2.4). With s as another variable, the same deduction in the proof ofLemma 2.3.2 applies and result in (A.1) becomesφ(s, d1) = zk =sd1d1 + akfor some k.Due to its analytical form, we can write φ(s, d1) = φ(1, d1)s. Then, by equation (2.5) we havex∗1(d1) = φ(1, d1)s ∧ d1. (2.14)Hence, if the second demand follows a discrete distribution, then the optimal solution toproblem (2.4) is separable in d1 and s, and it is linear in s. The intuition behind the result is:since the resource is divisible, we can scale demand and allocation by the total initial supply s,and the problem becomes sequential allocation of a unit resource. To be more precise regardingx∗1(d1) with fixed fix d1, by (2.14), the optimal allocation is linear in s while being truncated atsome level d1. The truncation represents the case where the supplier has sufficient amount ofsupply with which the first demand can be fulfilled. But below that level, the allocated amountis linearly increasing in s with the slope decided by the fixed d1; i.e. φ(1, d1). In either case,increasing s will not decrease the optimal allocation to the first customer.18Chapter 3Fairness Among Servers WhenCapacity Decisions Are Endogenous3.1 IntroductionMany service systems are characterized by arriving requests (jobs) processed by heterogeneousservers with different service capacities. In such systems, the decision on how the incomingjobs are routed to the servers is important. These decision rules, referred to as routing policies,are often designed by an administrator. The administrator cares about the performance of thesystem, which is measured through a combination of operational metrics such as flow times,utilization, quality, etc. This drives the design of the routing policy. For instance, if theadministrator’s goal is to obtain a fast speed of service, then customers are likely to be sent tothe fastest server available. This policy is named Fastest Server First (FSF) in the literature.In a many-server heavy-traffic system, the FSF policy minimizes the flow times (Armony,2005). However, FSF causes a significant distortion in the distribution of idle time amongthe servers. In fact, Armony (2005) shows that the FSF policy completely labors the fasterservers in large-scale settings. If the servers are employees, then the notion of the more efficientemployees being tasked with a higher workload can lead to perceptions of unfairness. This isa well-understood phenomenon in the human resources literature (Huseman et al., 1987), andit is often cited in operation management literature such as Armony and Ward (2010) and Cuiet al. (2007).The human resources literature has documented that such perceptions of unfairness havestrong negative consequences like absenteeism and disloyalty, which can be damaging to theorganization that houses these service systems. This issue is of particular significance in health-care and call center settings. The research in organizational behavior (Colquitt et al. (2001)and Cohen-Charash and Spector (2001), for example) provides strong evidence that inequitabletreatment often leads to significant employee dissatisfaction. Employee dissatisfaction furtherimpedes the system’s proper functionality. In particular, Colquitt et al. (2001) compare andtest several models from different studies to show the close relationship between organizationaljustice (how employees judge the behavior of the organization and their resulting attitude andbehavior) and job satisfaction and commitment. Moreover, Fehr and Schmidt (1999) claim thatpeople “are willing to give up some material pay-off to move to the direction of more equitableoutcomes.” In addition, Kahneman et al. (1986) point out that the administrator, despite being193.1. Introductionprofit-maximizing, will have incentive to act in a manner that is perceived as fair if she is awarethat the employees care about fairness.The importance of fairness and its eventual consequence to the performance of the employ-ees, and in turn to the organization, has led some operations managers to explicitly considerfairness when designing their service systems. In certain instances, this may mean that systemefficiency is sacrificed to maintain fairness. See Bertsimas et al. (2012) for a study on thisefficiency-fairness trade-off and its application to allocation problems in several areas includingcall center design and healthcare scheduling.To precisely describe the notion of fairness in our setting, we apply the traditional equitytheory model proposed by researchers in the organizational justice area. Adams (1965) andHuseman et al. (1987) find that, as a measure of fairness, an employee compares the ratio of“outcome” to “input” with others, where the former term usually refers to the reward andthe latter term refers to the effort. Huseman et al. (1987) further suggest that, if the ratio issmaller (bigger) than others, the employee will consider being under-rewarded (over-rewarded).Employees sensitive to fairness require this ratio to be close to equal across all employees. Theyfeel distress when under-rewarded and they experience guilt when over-rewarded. Husemanet al. (1987) also show that, in cases of unfairness, employees take actions to restore equity. Ina call center with the FSF policy for instance, this translates to reducing the speed at whichcalls are answered (Mandelbaum et al., 2010).Following the equity theory discussed above, we model server’s processing rate or capacityas the “input”, which is quite natural and straightforward. However, the reward (“outcome”)has several plausible candidates in our setting. Although monetary rewards accruing throughwages and bonuses seem a reasonable choice, this is not the case in many contexts. Two reasonsfor this are institutional policies and the legacy of the organizations where these service systemsreside in. For example, healthcare is unionized in many areas of the world and thus does noteasily allow for differentiated rewards. Moskowitz (1983, p.827) discusses how federal legislationimposes barriers on differentiated rewards in service systems in the non-profit and healthcareareas. Another reason for the absence of monetary awards is that setting up a differentiated anddynamic reward system would impose a significant administrative and informational burden onthe organization. For these reasons, we do not consider monetary pay-off in this paper. Instead,we use intrinsic process-related measures that employees care about, such as idle time. Moreidle time means less active work, which is an outcome of faster service in some cases. Underthis reward scheme, equitable treatment translates to idle times being distributed in relationto the capacities of individual servers.Some recent papers such as Armony and Ward (2010) have addressed the fairness issue bymodeling it as an exogenous constraint. However, to the best of our knowledge, endogenizingfairness has not been attempted in the literature. To address this issue, we study a servicesystem where the fairness issue arises internally. The servers choose their capacities in responseto the routing policy in order to optimize their utility that includes a fairness component. We203.1. Introductionbelieve that we are the first to explicitly model fairness among servers who strategically deter-mine their capacities. Consequently, our work broadens the research area and introduces newapplications. Due to the endogeneity of servers’ capacities, characterizing the optimal routingpolicy for the administrator becomes a formidable task, which we do not intend to accomplishin this paper. Instead, we take an important first step to analyze a class of policies and severalof the most commonly used ones. In particular, we are interested in how the servers react tothe policies and how the policies affect the system efficiency in a decentralized environment inwhich the servers make decisions independently and simultaneously. Furthermore, our aim isto understand the role that fairness plays in the decision making process.3.1.1 Literature ReviewThe notion of fairness arises in various organizations (Greenberg, 1987), and it is often contextdependent. In a service system, two kinds of views exist on fairness: (1) fairness amongdifferentiated customer classes and (2) equitable treatments toward servers (employees). Alarge amount of literature on fair routing policies focuses on the first kind. Avi-Itzhak et al.(2008) and Wierman (2007) provide good reviews on this type of work. The second kind ofview (equitable treatment to employees), although important, has received less attention in theoperations management literature. Our work is from this perspective.Armony andWard (2010) study a large-scale (large arrival rate and many servers) heterogeneous-server system and aim to minimize the steady-state expected waiting time subject to a fairnessconstraint on workload division. They propose a dynamic threshold routing policy that deter-mines the assignment priorities of servers based on the total number of customers in the system.This policy is shown to be optimal asymptotically as the arrival rate and the number of serversgrow to infinity. Given that the idleness proportion of each server is fixed in the Whitt-Halfinregime, the average waiting time for customers is minimized.Atar et al. (2011) focus on the same type of service system and bring in the notion ofservers’ fairness. They analyze the performance of a policy that routes customers to the serverwith the longest cumulative idleness. This policy is “blind” as it requires no information onservice or arrival rates. Not surprisingly, the policy attains equalization of cumulative idlenessasymptotically. Recently, Reed and Shaki (2014) extend the framework of Atar et al. (2011)to general service time distribution, and also study a blind policy which aims to spread theincoming work amongst servers pools in an equitable way.Tseytlin (2009) and Mandelbaum et al. (2010) study emergency departments in hospi-tals. They seek to allocate patients to wards in an equitable manner. They introduce theRandomized-Most-Idle (RMI) policy, which routes customers to a server pool (group of servers)with a probability that equals the ratio of the number of idle servers in that pool to the totalnumber of idle servers in the system. This policy depends on neither cumulative idleness timesnor capacities of the pools.213.1. IntroductionTezcan (2008) studies the optimal control in a distributed parallel system. Since customersare routed upon arrival in this system, it differs from the setting in our model and in the otherstudies discussed thus far. One of Tezcan’s proposed policies, named Minimum-Expected-Delay-Load-Balancing (MED-LB), is proved to asymptotically achieve the goal of having the averageutilization of each server balanced.All of the above papers employ asymptotic analyses and the theoretical results hold forlarge-scale systems. In contrast to asymptotic results, some papers look at server’s fairnesswith exact analysis. As an extension of his investigation on the slow server problem (Cabral,2005), Cabral (2007) studies the question of “who works most”. He shows that, in a systemwith two different servers and a routing policy that sends customers to each server with equalprobability when both are idle, the faster server serves more customers but works less hours inthe long run. Wu et al. (2007) place emphasis on servers’ fairness in the context of a bandwidthallocation problem in telecommunication networks. The fairness measurement used in theirpaper is not directly applicable to our model.The asymptotic and the exact studies mentioned above assume that the administrator isthe only decision maker and that the servers provide exogenous capacities. This paper differsfrom the above papers in that we study a decentralized system in which the servers choose theircapacities, which is seen in many contexts where employees are not supervised strictly all thetime.Several papers also assume that servers choose their speed endogenously. Gopalakrishnanet al. (2013) study a dispatching and staffing problem in a strategic server context that resemblesours. Like our research, their research is motivated by fairness issues. However, server’s trade-off does not include fairness in their model. On the contrary, we model fairness explicitly aspart of server’s utility. In addition, we look at heterogeneous servers and thus study asymmetricequilibria, which Gopalakrishnan et al. (2013) do not consider. Some other papers that studystrategic servers are Kalai et al. (1992), Gilbert and Weng (1998), Cachon and Zhang (2007),Ching et al. (2010) and Choi et al. (2011). We note that the model, objective, and analysis ofthese papers are different from ours. One significant difference is that fairness is not an issuein these papers.Our contributions in this paper are as follows.1. We treat the issue of servers fairness as an endogenous factor. In our model, fairness is acomponent in players’ utilities and affects their actions. Thus, their choice of capacity asa response to the announced policy considers fairness. To our knowledge, we are the firstto take this view.2. Our analysis does not appeal to a heavy traffic analysis. Thus, we do not need large scalesystems for our results to hold. In fact, in some cases (e.g. off-peak hours in hospitalswhen the number of servers is quite small) the many-server heavy-traffic assumption maynot apply. As a result, our result is exact and perhaps more appropriate in certain settings.223.2. Model3. We extend the research on game-theoretic queueing by adding a component of fairnessmeasurement into the server’s objective function, which is not seen in this stream ofliterature. From a technical perspective, this extension makes our research significantlydifferent from that in the literature and more challenging to cope with.3.2 Model3.2.1 Basic AssumptionsWe study a two-server queueing system with Poisson arrivals and exponential service times.A homogeneous class of customers arrive at rate λ and the capacities of server 1 and server 2are µ1 and µ2 (chosen endogenously, as will be clear later). We treat λ as exogenous in thispaper, and thus normalize it to 1. Later, it will become apparent that our model and resultsapply to arbitrary λ. We require that the servers’ minimum capacity is 1/2. This assumptionmakes sense in that employees are expected to work no less than a minimum level of efficiency(Gopalakrishnan et al., 2013). To control the system, the administrator announces a routingpolicy that satisfies certain requirements. We adopt the three assumptions in Armony andWard (2010) regarding the feasible policies: (1) we do not allow pre-emption; (2) when there isa waiting customer, no server is allowed to be idle (this non-idling assumption is widely usedin the literature); and (3) we only consider policies that are independent of future information(i.e. non-anticipatory). Furthermore, the system applies a single-queue formation, meaningthat the arrived customers are routed only when at least one server is available. The use of asingle queue instead of parallel queues is not only operationally sensible, but it also enhancescustomer satisfaction based on perceptions of the system (Larson, 1987). Finally, we assumethat there is no abandonment.We consider randomized routing policies. Let φ be the probability that the customer whoarrives at an empty system is sent to server 1. Under our assumptions, the routing policy affectsthe system only when both servers are idle. It can be fully expressed by the routing probabilityφ. Therefore, the routing probability is henceforth referred to as the policy. We further assumethat the policy does not depend on time (stationary policy). In fact, all our analysis assumes along run stable system. After a policy is announced, a non-cooperative game unfolds betweenthe two servers who simultaneously choose µ1 and µ2. We assume that changes in capacitiesonly affect process flow measures and have no other effects (such as on the quality of service).3.2.2 Individual Server’s ObjectiveIn this subsection, we introduce the server’s objective function and the formulation of the de-centralized problems, in which servers separately and simultaneously decide their capacities.We model the server’s objective using two aspects. They are referred to as self-focused andcomparison-based disutility. The first aspect pertains to a server’s own performance measures233.2. Modelencompassing idleness and effort. The second aspect is borrowed from the organizational be-havior literature (Festinger, 1954), and it reflects the dissatisfaction towards unfairness due tocomparison. We will use the sum of the inverse-idleness function and the capacity cost func-tion to capture self-focused disutility. Also, we will use an “unfairness” function to describecomparison-based disutility.Self-focused Disutility.First, consider the long run average fraction of idle time for each server, denoted by τi(i = 1, 2). We define the inverse-idleness function bygi(µ1, µ2) =1τi, i = 1, 2. (3.1)Recall that the minimum capacity is 1/2, then the only case which results in an unstable systemis µ1 = µ2 = 1/2. In such a case, τ1 = τ2 = 0 and gi is defined as infinity. Hence, we see that,although choosing such a low rate is allowed, overloading the system is never preferred by theservers. This resonates with practice where systems are rarely overloaded in the long run. Sinceneither server prefers the outcome of both choosing the minimum capacity, we ignore this case.Therefore, from here onwards, we only consider a stable system. In general, gi is decided bythe capacities and the routing policy; however, we simply write it as a function of capacities.Later it will be clear that the policies we are interested in can be expressed through µ1 and µ2.Second, as mentioned, the two servers are possibly heterogeneous in their capability inproviding service. In other words, it requires different effort levels for them to provide the samecapacity. We capture this by having different unit costs of capacity. Without loss of generality,let server 2 be the costlier one. Assume that server 1’s unit cost is t and his capacity cost istµ1. In addition, assume that server 2’s unit cost is t+∆t and his capacity cost is (t+∆t)µ2.Suppose t > 0 and ∆t ≥ 0. Note that, when ∆t = 0, we have the case of homogeneous servers.Our linear cost assumption is a simplification of the convex cost function used, for example, byKalai et al. (1992), who model servers’ cost as a strictly convex function. However, we will seelater that our main results remain valid even if we assume strict convexity.Together, the inverse-idleness and the capacity cost contribute to server’s self-focused disu-tility: g1 + tµ1 for server 1 and g2 + (t+∆t)µ2 for server 2.Comparison-based Disutility.Fairness is indeed amorphous and depends on the context. Although people’s judgementon fairness may have some connection with their general expectations, research has shown thatit is based more strongly on social comparison (Austin et al., 1980). Therefore, we modelthe dissatisfaction caused by unfairness between servers as their comparison-based disutility.Following the discussion in Section 3.1, we apply the equity model studied by Adams (1965) andHuseman et al. (1987). Specifically, servers perceive fairness by comparing the outcome/inputratio with one another. Inequity exists if and only if the ratios are unequal, incurring thecomparison-based disutility. As discussed earlier, we use the chosen capacity as input and the243.2. Modelaverage fraction of idle time τi as outcome. A similar treatment can be seen in literature. Forexample, Mandelbaum et al. (2010) use “utilization”, which is 1− τi in our setting, as a factorfor fairness measurement.Since the input and the outcome are identified, we apply the equity model directly. Hence,servers consider it fair if and only ifτ1µ1= τ2µ2. (3.2)If the above equality becomes “<” (for example, µ1 > µ2 and τ1 < τ2), then the faster server(server 1) is exposed to a higher workload instead of being rewarded with more rest time.We say that server 1 is under-rewarded in this case. Similarly, he is over-rewarded if theequality becomes “>” in (3.2). Both cases are perceived as unfair. According to the study inHuseman et al. (1987), servers have an incentive to restore fairness whether over-rewarded orunder-rewarded. However, inequity that is to their disadvantage generally produces a highersuch incentive, as opposed to inequity that is to their advantage (see Fehr and Schmidt (1999)and Cui et al. (2007), for example). As a result, to simplify our model, we assume that theunder-rewarded server incurs disutility, whereas the over-rewarded server is unaffected.From the above discussion, server 1’s magnitude of inequity can be described as(τ2µ2 −τ1µ1)+.We now define the unfairness function based on this quantity. First, consider the following twoscenarios: (1) Server 1 inputs capacity µ(1)1 and experiences outcome/input difference d > 0.(2) Server 1 inputs capacity µ(2)1 and experiences outcome/input difference of the same amountd. Apparently, if µ(1)1 > µ(2)1 , then server 1 must experience more dissatisfaction in scenario (1)than he does in scenario (2). Studies in Brockner et al. (1992) provides supporting evidence.Therefore, we multiply the server’s capacity with the magnitude of inequity to model thisfeature. Second, as part of server’s disutility, it is reasonable to expect the function to haveincreasing margins. As the difference becomes larger, the server’s dissatisfaction increases ata greater rate. To model this, we take the quadratic form of the above expression. Therefore,the unfairness function is defined byf1 =(µ1( τ2µ2− τ1µ1)+)2(3.3)for server 1, andf2 =(µ2( τ1µ1− τ2µ2)+)2(3.4)for server 2.After a routing policy is announced, the servers compete in capacities to minimize theirindividual disutility functions with the policy being common knowledge. Throughout thispaper, we focus only on the pure strategies. Server’s total disutility is a weighed combinationof the self-focused disutility (weight 1) and comparison-based disutility. Let α(1)f and α(2)f be thepositive weights that server 1 and 2 associate to the comparison-based disutility, respectively.253.2. ModelIn general, we assume that the two weights are equal when ∆t = 0, but otherwise arbitrary.The servers’ problems are as follows. Server 1, given server 2’s chosen capacity µ2 ≥ 1/2, solves(S1) minµ1≥1/2F1 = α(1)f f1 + g1 + tµ1.Given µ1 ≥ 1/2, server 2 solves(S2) minµ2≥1/2F2 = α(2)f f2 + g2 + (t+∆t)µ2.In this two-player static game, besides the usual trade-off of idle time and capacity cost, serversalso need to consider fairness between themselves. Note that problems (S1) and (S2) both havethe announced policy embedded in the objective functions. As a result, the game structurelargely relies on the routing policy that is applied.3.2.3 Routing PoliciesWe have made several assumptions in Section 3.2.1 concerning the policy φ. Without furtherspecification, however, it is intractable to devise a feasible policy for the administrator toguarantee the optimal system efficiency. The problem remains difficult even if we restrain ourattention to a reasonably small class of policies. As mentioned earlier, our goal in this paperis not to solve for optimal policies, but to analyze a number of practical policies. We aim tounderstand how these policies affect servers’ choices and the fairness among them. This is animportant stepping stone to the search for the best-performing policies within that class. Inthis section, we characterize the policy class we are interested in and list the policies that wewill analyze in detail.Let R be the set of real numbers. For every r ∈ R, define a policyφr =µr1µr1 + µr2.In addition, define φ∞ = limr→∞ φr (∞ can be either positive or negative infinity). We shallfocus on the policy class defined byP = {φr | r ∈ R ∪ {±∞}}.Note that every policy in P is determined only through µ1 and µ2. Moreover, the policies arerelated to the comparison between the two capacities. Specifically, if r > 0, then the fasterserver gets more customers. If r < 0, then the slower server gets more customers. When r = 0,the customers are equally routed to the two servers regardless of their capacities. For thisreason, policies with small r are considered to be more fairness-oriented (the faster server isrewarded with less work). Furthermore, all of the policies in P are continuous with respect toµ1 and µ2 except when r ∈ {±∞}. The two special cases with discontinuity will be carefully263.2. Modeltreated later in this paper. In fact, the class P is also studied by Gopalakrishnan et al. (2013)and is named “rate-based” policies. We follow them and call P the capacity-based policy class.In this paper, we will mainly study four specific policies. All of them are commonly used inpractice because they are easy to implement. First, we discuss the two discontinuous policiesin P. As will be observed, the discontinuities of both policies are at µ1 = µ2. When r = +∞,we see by definition thatφ+∞ =1 µ1 > µ212 µ1 = µ20 µ1 < µ2 .This is the Faster Server First (FSF) policy, which we mentioned in Section 3.1. Several papershave discussed the FSF policy, including Armony and Ward (2010). This policy is popular dueto certain obvious operational benefits. Intuitively, it is the best policy if there are no issuesof fairness. However, it has negative consequences if servers care about fairness. On the otherend of spectrum is the case where r = −∞. Again, by definition we haveφ−∞ =0 µ1 > µ212 µ1 = µ21 µ1 < µ2 .This policy is named the Slower Server First (SSF) policy and is a natural remedy to theunfairness caused by FSF. Despite its effective treatment to unfairness among servers, previousworks on servers fairness in a queueing system seem to have little interest in SSF. The mainreason for this is that most of the previous models assume exogenous capacities (Armonyand Ward, 2010; Mandelbaum et al., 2010). Unsurprisingly, SSF makes least use of the totalcapacity, and thus it leads to low system efficiency. However, in a model where capacities areendogenously determined by servers, SSF induces a strong incentive for them to provide highcapacities. Therefore, for models that assume strategic servers such as Gopalakrishnan et al.(2013), it makes sense to study SSF closely.Second, we list two continuous policies from P that we will pay close attention to. Thedefinition of equity, (3.2), indicates that to maintain fairness, the idle time of the server withlower capacity must be small. One can achieve this by sending more customers to the slowerserver than the FSF policy. As noted, the SSF policy does this but fails to admit continuousdisutility functions. Hence, we propose a policy that is in the same spirit as SSF but muchsmoother. Let r = −1 and thenφ−1 =1/µ11/µ2 + 1/µ1= µ2µ1 + µ2.This policy also sends more customers to the slower server to incentivize higher capacity. Sincethis policy routes the customers to each server with the probability proportionate to the inverse273.3. Two-Server Game: Analysis and Resultscapacities, we shall refer to it henceforth as the proportional policy (Prop). Finally, we includethe simplest policy in Pφ0 =12 .We refer to this policy as the Half-Half (HH) policy. Being a constant, HH is the easiest to im-plement and analyze. Many previous works with either strategic or non-strategic servers applythis policy, e.g. Cabral (2007); Kalai et al. (1992). Moreover, sharing the customers equally be-tween servers bears a natural sense of equity, especially when the heterogeneity between serversis unclear.In the rest of the paper, we write φFSF, φSSF, φProp and φHH instead of φ+∞, φ−∞, φ−1 andφ0, respectively, and let P˜ = {φFSF, φSSF, φProp, φHH}.3.3 Two-Server Game: Analysis and ResultsIn this section, we study the optimization problems posed to the two servers and provide someresults regarding the structural properties of their optimal decisions. We do not consider mixedstrategies but only look at pure strategies. Denote the announced policy by φ¯. We requirethat φ¯ ∈ P. Taking φ¯ as common knowledge, both servers simultaneously choose capacities tosolve problems (S1) and (S2), respectively. We focus on server 1’s objective functions in detailbecause parallel results for server 2 follow without difficulty by exchanging the roles of µ1 andµ2. To clarify notations, recall that gi is the inverse-idleness function for server i (i = 1, 2)defined in (3.1). In the following discussion, we write it as gi(µi|µj , φ¯). The first argument µi isserver i’s action, which is the variable of the function, and µj and φ¯ are his opponent’s actionand the announced policy, which are fixed to him. A similar notation is used for the unfairnessfunction fi. In addition, the ′+′ and ′−′ signs beside the variable mean right and left limit,respectively. All proofs are in the Appendix A.2.To begin with, we look at a benchmark case where ∆t = 0 (hence α(1)f = α(2)f ). This meansthat the two servers are homogeneous. We study this case because it is a good approximation incircumstances where the heterogeneity is very small or even negligible. In this case, a symmetricNash equilibrium where the two servers choose the same capacity is expected. This is indeedtrue as long as the implemented policy is not FSF or SSF. The following theorem characterizesthe symmetric equilibrium for the continuous policies.Theorem 3.3.1. Suppose ∆t = 0 and t is fixed. Let Pc = P \ {φFSF, φSSF}. For every φ¯ ∈ Pc,there exists a unique symmetric Nash equilibrium (µ∗, µ∗). Moreover,(i) for any small ǫ > 0, there exists r¯ > 0 such that for any φr with r > r¯, we haveµ∗ < 1/2 + ǫ; and(ii) for any big M > 0, there exists r < 0 such that for any φr with r < r, we have µ∗ > M .The above theorem only deals with symmetric equilibrium. Other asymmetric equilibriamay exist, but we do not consider them. One important implication of Theorem 3.3.1 is as283.3. Two-Server Game: Analysis and Resultsfollows. Although a symmetric equilibrium for every continuous policy always exists, not all ofthem are favorable. Examples of unfavorable equilibrium include small µ∗ (close to 1/2), whichmakes gi large and big µ∗ (approaching infinity), which results in large capacity cost.Theorem 3.3.1 shows that we can find a sequence of policies {φr} which approaches φFSF,such that the corresponding equilibrium sequence converges to 1/2. Similarly, for policiesapproaching SSF, the equilibrium sequence increases to +∞. For policies that have large |r|,they are continuous, but are “almost” FSF and SSF. Theorems 10 and 11 in Gopalakrishnanet al. (2013) also characterize the properties of these policies. Because the capacity cannotexceed a fixed large number by their assumption, they claim that policies that are “almost”SSF do not induce symmetric equilibrium. Although we cannot deduce that FSF and SSF donot admit symmetric equilibrium directly from Theorem 3.3.1, we do have such result as acorollary of Propositions 3.3.2 and 3.3.3, which will be introduced shortly. We emphasize againthat the above discussion only concerns symmetric equilibrium. As will be shown in Section 3.4,when ∆t = 0, the FSF policy may induce Nash equilibria that are not symmetric.Now, we move to the general case where servers are not necessarily homogeneous. In thefollowing discussion, we restrict our attention to the four policies φ¯ ∈ P˜. We will study thesepolicies from two aspects. First, we examine how servers behave in the two-server game underthose policies. This game may or may not have an equilibrium. Second, supposing that wehave equilibria under the policies, we will compare them along the measure of system efficiency,which will be discussed in Section 3.4. Naturally, the policy that leads to higher efficiency ispreferred by the administrator.As an important preparation for the equilibrium analysis, we give some basic results thatdepict the shape of the objective functions. Two propositions characterize server 1’s inverse-idleness function and unfairness function, respectively, under the four policies.Proposition 3.3.2. Suppose µ2 > 1/2 is fixed.(i) If φ¯ ∈ {φProp, φHH}, then g1(µ1|µ2, φ¯) is continuous, strictly decreasing and convex forµ1 > 1/2.(ii) If φ¯ ∈ {φFSF, φSSF}, then g1(µ1|µ2, φ¯) has two continuous pieces on 1/2 < µ1 < µ2and µ1 > µ2 respectively. On both pieces, g1(µ1|µ2, φ¯) is strictly decreasing and convex.Furthermore,g1(µ2 − |µ2, φFSF) < g1(µ2|µ2, φFSF) < g1(µ2 + |µ2, φFSF) (3.5)g1(µ2 − |µ2, φSSF) > g1(µ2|µ2, φSSF) > g1(µ2 + |µ2, φSSF). (3.6)Proposition 3.3.3. Let µ2 > 1/2 be fixed.(i) If φ¯ ∈ {φFSF, φProp, φHH}, then f1(µ1|µ2, φ¯) = 0 for 1/2 < µ1 ≤ µ2, and f1(µ1|µ2, φ¯) isstrictly convex and increases to infinity on µ1 > µ2.293.3. Two-Server Game: Analysis and Results(ii) If φ¯ = φSSF, then there exists 1/2 ≤ a < µ2 and b > µ2 such that f1(µ1|µ2, φSSF) iscontinuous, strictly increasing and convex on a ≤ µ1 < µ2 and µ1 ≥ b, respectively.Moreover, f1(µ1|µ2, φSSF) = 0 for both 1/2 ≤ µ1 ≤ a and µ2 ≤ µ1 ≤ b.Note that we exclude the case µ2 = 1/2. In fact, the only part in the propositions thatneeds to change to accommodate this case is Proposition 3.3.2 (ii). Just one decreasing convexpiece will exist for g1, i.e. µ1 > µ2. All other results remain valid.Proposition 3.3.2 implies that the inverse-idleness function g1 is continuous only if thepolicy is continuous. Under FSF or SSF, gi has a discontinuity at µ1 = µ2 because the policyis discontinuous there. As a result, when φ¯ ∈ {φFSF, φSSF} and the two servers have the samecapacity, server 1 can reduce a strictly positive amount of disutility by deviating a little fromµ2. Proposition 3.3.3 shows the distinguishing feature of the SSF policy. For the other threepolicies, the unfairness function f1 equals zero if 1/2 < µ1 ≤ µ2, and it becomes positiveimmediately after µ1 surpasses µ2. However, under the SSF policy, there is a positive piece off1 when µ1 < µ2, and f1 remains zero after µ1 exceeds µ2 until the difference is sufficientlylarge. This characteristic shows that SSF strongly incentivizes the slow server.Recall that the overall objective function Fi is a linear combination of gi, fi, and a linear costfunction. An immediate and useful implication is that Fi also has the corresponding convexityproperties. A further implication concerning FSF and SSF is thatF1(µ2 − |µ2, φFSF) < F1(µ2|µ2, φFSF) < F1(µ2 + |µ2, φFSF)F1(µ2 − |µ2, φSSF) > F1(µ2|µ2, φSSF) > F1(µ2 + |µ2, φSSF).Since the above inequalities are strict, µ2 can never be the value of µ1 minimizing F1. Thus,a unilateral deviation from any symmetric strategy profile will always exist. Therefore, as acorollary of the above propositions, we conclude that FSF and SSF do not induce symmetricequilibrium. The jump in F1 for the two discontinuous policies also poses difficulty in findingan asymmetric equilibrium. We can derive sufficient conditions for the existence of equilibrium,but they are implicit and far from illustrative. Instead, we will mainly treat it numericallyin Section 3.4. We will see that the sufficient conditions are liberal for FSF but somewhatstringent for SSF. That is, a large number of instances display an equilibrium under FSF whileno instance with ∆t < t displays equilibrium under SSF.Fortunately, Prop and HH result in continuous objective functions with desirable properties.Under Prop or HH, the two-server game is resolved by solving two convex optimization problemssimultaneously. The theorem below summarizes our main findings.Theorem 3.3.4. Suppose ∆t > 0 and φ¯ ∈ {φProp, φHH}. Then there exists a unique Nashequilibrium (µ1, µ2), and µ1 > µ2.We will apply the result in Nikaidoˆ and Isoda (1955) to show the existence of the equilibrium,and we will turn to Theorem 7 in Cachon and Netessine (2006) for the proof of uniqueness. We303.4. Simulations and Discussionsprove µ1 > µ2 by contradiction. This result clearly shows the benefit of using Prop or HH asthe routing policy. These policies both induce a unique equilibrium in which the cheaper serverprovides higher capacity. It is also noteworthy that Theorem 3.3.4 is valid for all heterogeneousservers cases (∆t > 0), regardless of the unit cost and the weights of fairness.Three points summarize our main results in this section. First, we showed that all con-tinuous capacity-based policies admit a unique symmetric equilibrium when the servers arehomogeneous. However, this common capacity is either too small or too large if the policy isclose to FSF or SSF. Second, we outlined the shape of server’s objective function for differ-ent policies, and thus laid a solid foundation for further analyses. Third, we established theexistence and uniqueness of the Nash equilibrium under the Prop and HH policies.3.4 Simulations and DiscussionsIn this section, we further study the four policies in P˜ by simulations. Our goals are to un-derstand the servers’ behaviors under each policy, to compare the policies’ performances withrespect to system efficiency, and to obtain further insights. Our approach consists of threeparts. (1) In Section 3.4.1, we examine the existence and uniqueness of equilibrium by plottingthe best response functions under each policy. A unique equilibrium exists for Prop and HH(as predicted in Theorem 3.3.4). For FSF and SSF, the non-existence of Nash equilibrium isillustrated. In this case, we characterize the servers’ off-equilibrium behaviors by an intervalof capacities. (2) Section 3.4.2 explicitly compares the outcome of the game under differentpolicies. We also obtain some empirical patterns regarding the equilibrium properties for FSFand SSF. (3) In Section 3.4.3, we focus on equilibrium outcomes and compare the four policiesbased on system efficiency. Particularly, we study how servers’ attitudes towards fairness andservers’ heterogeneity affect a policy’s performance.To simplify the simulation, we reduce the freedom of parameters by setting α(2)f = (t +∆t)α(1)f /t. Here we assume that the costlier server cares about fairness more and the weightsare proportional to capacity costs. This is not a crucial assumption as our main results andobservations under the opposite assumption (α(2)f = (t + ∆t)α(1)f /t) are the same. Arbitrary(α(1)f , α(2)f ) cases can also be treated in a similar manner. Hence, we simulate with three freevariables: α(1)f ∈ [0, 10], t ∈ (0, 10], and ∆t ∈ [0, 10]. The discretization step is 0.5. Algorithmsare implemented using Matlab and are run on a standard PC.3.4.1 Best Response Functions and Off-Equilibrium BehaviorsThe convexity properties shown in Propositions 3.3.2 and 3.3.3 grant the use of binary searchalgorithm to get the best response functions for each server. Figure 3.1 (Prop and HH) andFigure 3.2 (FSF and SSF) illustrate their typical shapes.An immediate observation from Figure 3.1 is that the best response functions for Propand HH are continuous and intersect exactly once. Besides, the intersection lies above the313.4. Simulations and Discussions0.5 1 1.5 2 2.50.511.522.5Best Responses (Prop)µ2µ 1  server 1’sserver 2’s(a) α(1)f = 4, t = 2, ∆t = 10.5 1 1.5 20.511.52Best Responses (HH)µ2µ 1  server 1’sserver 2’s(b) α(1)f = 4, t = 2, ∆t = 1Figure 3.1: Best response functions (Prop and HH).0.5 1 1.50.511.5Best Responses (FSF): No NEµ2µ 1  server 1’sserver 2’s(a) α(1)f = 10, t = 2, ∆t = 0.50.5 1 1.50.511.5Best Responses (SSF): No NEµ2µ 1  server 1’sserver 2’s(b) α(1)f = 4, t = 5, ∆t = 3Figure 3.2: Best response functions (FSF and SSF). Linear segments on 45◦ line are not partof the functions.µ1 = µ2 line, which means that server 1 provides higher capacity at equilibrium. Furthermore,Figure 3.1 also confirms our theoretical result that the equilibrium is unique. According toCachon and Netessine (2006), in the two-player case, an equivalent condition to Theorem 7 intheir paper is that the multiplication of slopes of best response functions should not exceedone at equilibrium. Figure 3.1 clearly shows that the two best response functions both havederivatives with absolute values of less than 1 at the intersection. Therefore the condition holdsand we have the uniqueness of equilibrium.Because of the discontinuity of FSF and SSF, the best response curves under these policieshave jumps and equilibrium properties (whether it exists and, if yes, how many) are unclear.Although FSF and SSF induce equilibrium in many instances, the instance shown in Figure 3.2does not have any equilibrium and we try to understand servers’ off-equilibrium behavior.Although it seems that, by Figure 3.2, there is a continuum of symmetric equilibria for bothFSF and SSF, it is not true. We draw the linear segments as part of best response curves in323.4. Simulations and Discussionsthe graphs to represent that the functions are not defined there. Take server 1 for example, byinequalities (3.5) and (3.6), we know that it is actually the left limit of µ2 (µ2−) that achievethe infimum, not minimum, of server 1’s objective function under FSF, and the right limit of µ2(µ2+) under SSF. In the simulation, we plot them as µ1 = µ2− ǫ and µ1 = µ2 + ǫ, respectively,with very small ǫ > 0. The same logic and technique applies to server 2. Therefore, servers’best response function does not actually exist along the 45 degree line.However, this linear segment is the key to understand servers’ off-equilibrium behaviors.Take Figure 3.2 (a) (FSF) for example. The best response iteration leads the strategy profile(µ1, µ2) to eventually land on the µ1 = µ2 − ǫ segment. This means that server 1 undercutsserver 2 by a small quantity. Then the same strategy is taken by server 2 (µ2 = µ1 − ǫ). As aresult, the servers decrease the capacities in turn until the inverse-idleness becomes sufficientlylarge. Next, one of the servers increases his capacity, and another round of undercutting begins.The thick solid line shown in Figure 3.2 (a) indicates the undercutting range. Since the linesegment lies in the 45 degree line, we can express the endpoints of the line segment as (µ, µ)and (µ¯, µ¯), and we simply write [µ, µ¯] to denote the servers’ off-equilibrium behavior. Similarly,for SSF, we also have such an interval. However, instead of undercutting, the servers increasecapacities in turn within the range of the interval, and they decrease capacities when the costis too high to bear.3.4.2 Comparison of EquilibriaTable 3.1 shows what we obtained for different sets of parameters and policies. These are some ofthe representative instances from our extensive simulations. The first kind of entry is presentedwith parentheses and represents the equilibrium capacity decisions (µ1, µ2). The second kind ofentry is marked with square brackets and reports the interval [µ, µ¯] of the off-equilibrium range.A few noteworthy observations emerge from our simulation. First, the servers’ possible off-equilibrium capacities under FSF are very small compared to the equilibrium capacities underProp or HH. Indeed, we observe from Table 3.1 that µ¯ under FSF is smaller than µ1 under Propand HH. This is a major disadvantage of FSF when accounting for endogenous capacity. Onthe contrary, the off-equilibrium capacities under SSF are high enough to compare with Propand HH. In fact, for the same parameters, every µ¯ under SSF is higher than µ1 under Prop andHH; and in some case µ is higher than µ2. Hence, by effectively incentivizing the slow server,SSF induces, even being off-equilibrium, possibly large capacities for both servers.Second, although the equilibrium (µ1, µ2) induced by SSF is relatively high compared tothat induced by Prop and HH (especially for server 2), SSF cannot induce equilibrium in quitea few instances. This means that the first order condition under SSF is stringent. During oursimulation, we find that ∆t must be at least as large as t for an equilibrium to exist under SSF(i.e. server 2’s capacity cost has to be at least twice the capacity cost of server 1). Anotherobservation is that, given fixed t and ∆t, if an equilibrium exists for α(1)f , then one also existsfor all larger weights of fairness. In other words, when more weight is given to fairness, it is333.4. Simulations and Discussions∆t t = 1 t = 5α(1)f = 1 α(1)f = 5 α(1)f = 10 α(1)f = 1 α(1)f = 5 α(1)f = 100FSF [0.70, 0.98] [0.66, 0.98] [0.64, 0.98] (0.90,0.57),(0.57,0.90) [0.60, 0.71] [0.60, 0.71]SSF [0.98, 1.94] [0.98, 1.94] [0.98, 1.94] [0.71, 1.01] [0.71, 1.02] [0.71, 1.02]Prop (1.13, 1.13) (1.13, 1.13) (1.13, 1.13) (0.75, 0.75) (0.75, 0.75) (0.75, 0.75)HH (1.08, 1.08) (1.08, 1.08) (1.08, 1.08) (0.74, 0.74) (0.74, 0.74) (0.74, 0.74)0.5FSF [0.70, 0.89] [0.66, 0.89] [0.64, 0.89] (0.92,0.54),(0.59,0.87) (0.84, 0.59) [0.60, 0.70]SSF [0.98, 1.61] [0.98, 1.61] [0.98, 1.61] [0.71, 0.98] [0.71, 0.98] [0.71, 0.99]Prop (1.16, 0.96) (1.12, 0.97) (1.10, 0.97) (0.77, 0.72) (0.77, 0.72) (0.77, 0.72)HH (1.14, 0.89) (1.08, 0.92) (1.04, 0.93) (0.77, 0.71) (0.77, 0.71) (0.76, 0.71)3FSF (1.17, 0.50) (0.97, 0.57) (0.90, 0.62) (0.94, 0.50) (0.89, 0.50) (0.84, 0.53)SSF (1.21, 0.68) (1.20, 0.68) (1.19, 0.68) [0.71, 0.88] [0.71, 0.88] [0.71, 0.89]Prop (1.26, 0.63) (1.14, 0.65) (1.07, 0.67) (0.84, 0.61) (0.84, 0.61) (0.83, 0.62)HH (1.25, 0.56) (1.08, 0.61) (1.01, 0.65) (0.87, 0.57) (0.85, 0.58) (0.84, 0.59)6FSF (1.17, 0.50) (0.98, 0.50) (0.91, 0.50) (0.94, 0.50) (0.89, 0.50) (0.85, 0.50)SSF (1.33, 0.50) (1.23, 0.53) (1.18, 0.54) [0.71, 0.82] (0.82, 0.59) (0.82, 0.59)Prop (1.32, 0.51) (1.17, 0.52) (1.09, 0.54) (0.91, 0.52) (0.90, 0.53) (0.88, 0.53)HH (1.26, 0.51) (1.09, 0.51) (1.02, 0.52) (0.92, 0.51) (0.90, 0.51) (0.88, 0.51)Table 3.1: Possible game outcomes. Entries with square brackets represent the interval whilethose with parentheses represent the equilibrium.more likely that an equilibrium will exist. Table 3.1 illustrates these empirical patterns.Third, while the possibility of an arbitrary number of equilibria has not been ruled out,we have observed only the two equilibria case under the FSF policy. Besides, it only happensin a small number of instances. The key condition for FSF to have two equilibria is ∆t beingsmall (i.e. the heterogeneity between two servers is negligible). For example, see the cases when∆t = 0 and 0.5 in Table 3.1. Except for these cases with two equilibria under FSF, all otherinstances have at most one equilibrium for FSF or other policies. Interestingly, when there isonly one equilibrium (µ1, µ2), we always observe µ1 ≥ µ2, regardless of the policy, which impliesan intuitive property that the cheaper server provides a higher capacity. For Prop and HH, weproved this theoretically; for FSF and SSF, however, this is observed empirically.3.4.3 Comparison in Policy PerformanceIn the following, we will only focus on equilibrium outcomes and compare the policies. Theperformance measure is system efficiency, which we assume to be the average number of sojourncustomers in the system: L = L(µ1, µ2, φ¯). The administrator prefers this quantity to be small.Note that if there are two equilibria, we compute L for both and use the smaller one forcomparison. We do not plot L when no equilibrium exists.343.4. Simulations and DiscussionsIn the experiment, we vary two parameters in our model: (1) how much servers care aboutfairness and (2) the heterogeneity between servers. The first is characterized by the weight α(1)fwhile the second by ∆t. In the simulations, we plot L against these two parameters. Hence,we gain insights into how servers’ attitude towards fairness and servers’ heterogeneity affect apolicy’s performance. For illustration purposes, we only show the representative instances fromthe extensive simulations we conducted.Figure 3.3 contains two L versus α(1)f plots with different cost parameters (specified in thecaption). The plots clearly show that L(φFSF) has the biggest increase along α(1)f . Curves0 2 4 6 8 101.41.61.822.22.42.62.8αf1L  FSFSSFPropHH(a) Low cost: t = 1, ∆t = 30 2 4 6 8 1022.533.5αf1L  FSFSSFPropHH(b) High cost: t = 3, ∆t = 5Figure 3.3: Performance of policies against fairness weight α(1)f with different costs.representing Prop and HH also have observable increases, but are pretty stable. For SSF,L(φSSF) is almost flat in the plots. This indicates that, if a policy sends less customers to theslower server, then it is more sensitive to α(1)f . Indeed, such a policy is intuitively unfair and isaffected greatly as servers care about fairness more. Besides, higher costs make the sensitivityof L(φFSF) more obvious, as it is steeper in (b) than in (a). Furthermore, when α(1)f is small,FSF induces the least congestion among all policies. This is obvious when α(1)f = 0 (i.e. thereis no fairness issue because servers do not care about it). In fact, even when α(1)f is positive,L(φFSF) may still be the smallest. In addition, a higher costs case admits more such positiveα(1)f values. In general, when α(1)f is small and the cost is high, FSF can perform better in termsof system efficiency than other policies. This finding appears to be in contrast to Armony andWard (2010), who have shown that FSF is completely unsuitable if servers care about fairness(i.e. α(1)f > 0 in our model). This difference is due to the key assumption about capacityendogeneity. The capacities, and therefore the cost functions, are exogenous in their model.Next, we study how heterogeneity affects a policy’s performance. Figure 3.4 gives two Lversus ∆t plots with the same t = 3 but different weights of fairness. Notice that curves aredrawn only when an equilibrium exists. Since all curves are continuous, the plots indicate that,if an equilibrium exists for some ∆t, then one also exists for all larger ∆t. As discussed earlier,it is empirically true that the SSF policy induces equilibrium only when ∆t is bigger than t. In353.5. Summary and Extensions0 2 4 6 8 101.81.922.12.22.32.42.5∆tL  FSFSSFPropHH(a) Small weight: α(1)f = 1, t = 30 2 4 6 8 101.81.922.12.22.32.42.52.62.72.8∆tL  FSFSSFPropHH(b) Large weight: α(1)f = 5, t = 3Figure 3.4: Performance of policies against extra cost ∆t.this sense, SSF’s performance is sensitive to ∆t. Indeed, curves under SSF begin at ∆t = 4.5 inthe plots. For FSF, although its curves also begin at ∆t > 0, we see that the starting point ∆tis much smaller. Furthermore, for each policy, the L curve sees an increase at first, and thenbecomes quite stable over ∆t. Interestingly, in both plots (a) and (b), as ∆t increases, L(φFSF)is always the first to become flat. This shows how insensitive FSF is to the heterogeneity ofservers.We give a brief summary to conclude this section. When FSF is adopted, the total expectednumber of customers in waiting is quite sensitive to the weight of fairness, but somewhatinsensitive to the cost parameter. While FSF sometimes induces less congestion than otherpolicies, in many cases it does not outperform others policies, and the performance gaps toother policies are substantial. For this reason, we do not recommend FSF unless the managerhas a clear understanding of how much each server values fairness. On the other hand, underSSF, the number of customers waiting is insensitive to α(1)f but sensitive to ∆t. In fact, it is sosusceptible to the non-existence of equilibrium that the system may be unstable in many cases.Therefore, we do not recommend SSF as long as the two servers are not highly differentiated. Werecommend Prop since it is considerably stable with respect to system parameters consideredhere, and always admits a unique equilibrium, making the system predictable and stable. Wenote that Prop outperforms HH in almost all cases.3.5 Summary and ExtensionsThis paper studies a service system with a single arrival class and two servers. Our model hastwo distinguishing features. First, the routing policy not only decides the workload for bothservers, but also affects servers’ perception of the fairness between them. Second, capacities areendogenous as the two servers independently and simultaneously choose them after the policy isannounced. Some recent papers such as Armony and Ward (2010) have also noted the fairness363.5. Summary and Extensionsissue, but most of them treat the problem with fixed capacity assumption. Only a few paperssuch as Gopalakrishnan et al. (2013) take the game-theoretic view as we do, but our workdistinguishes itself by the explicit modeling of the unfairness term. Besides, Gopalakrishnanet al. (2013) focus on the homogeneous servers case while we model servers’ heterogeneity byan extra cost term ∆t.We analyze the two-server game under a class of routing policies. More specifically, weexamine four commonly seen policies. Theoretically, we prove some properties of server’s ob-jective function, and establish the existence and uniqueness of the Nash equilibrium for theProp and HH policies. Using simulation, we further study the policies from two perspectives:(1) equilibrium/off-equilibrium game outcomes and (2) the system efficiency performance. Asan empirical guidance to managerial application, we recommend the use of the Prop policy forits stability and reliability.Our work is a first step towards a greater understanding of endogenizing fairness amongservers. We list two direct extensions here. First, the N -server (N > 2) case awaits exploration.Although the disutility functions can be extended to the general case, doing so greatly curtailsthe tractability of the problem. Second, recall that the set of policies that we have consideredare four specific policies. It is not clear what an optimal policy would be in general. To answerthat, a study on the Stackelberg game between the administrator and the servers is in order.37Chapter 4Uniform Pricing in Service SystemsWith Experience Based QualityImprovement4.1 IntroductionHow should a revenue-maximizing firm price its delay-sensitive service that is provided bymultiple servers differing in their quality? Customers seeking such service usually must endurewaits in addition to paying the nominal price. Consequently, when deciding whether to use theservice, customers weigh the service value (typically correlated to the service quality) againstthe total cost incurred, which includes the paid price and the waiting cost due to congestion.A natural and commonly seen solution to the firm’s problem is to price based on the serviceprovider’s quality so that the customers’ surplus is fully exploited. To be more specific, in thecase where the firm owns quality-differentiated servers, a price is posted for each server andcustomers make rational decisions on whether to procure the service and which server to queueup to if they do. Given such customers’ behavior, the firm decide the set of prices for the serversto maximize the revenue. We call this pricing scheme differentiated pricing. Indeed, there hasbeen a large body of literature studying this type of pricing scheme in queueing systems sinceNaor (1969); see Hassin and Haviv (2003) for an excellent review.Although such scheme is used by many quality-differentiated service firms, we argue thatthere is a potential pitfall associated with it. Under differentiated pricing, it is plausible thatthe low quality server can only serve a small customer volume. For example, a majority ofcustomers prefer senior doctors to residents in the teaching hospital, experienced hair styliststo their apprentices, famous top-rated chiropractors to the unknown ones, etc. Even if the priceis set to be very low, the induced demand may still be limited. However, in many contextssuch as the above examples, servers can learn by doing and improve the service quality byaccumulating more experience (Gaynor et al., 2005). The plausibility of this experience-basedimprovement hypothesis rests on the idea of “practice makes perfect”. As a server satisfies alarge volume of customers’ demand, he has to apply a correspondingly large amounts of care,effort and scrutiny to the service processes. Hence, he learns and makes corrective changes thatresult in a higher quality service in the future. However, due to differentiated pricing, the lowquality server will improve very slowly, seriously impairing the firm’s long-run revenue. In fact,384.1. Introductioncontinuous improvement in service quality by training and servers’ learning is considered asa prerequisite to firm competitiveness in service management. Letting the low quality serversserve more customers is without doubt an effective way of training and helping them improve.Hence, when a firm can and should take advantage of the experience-based quality improvement,it is an interesting question to examine whether applying differentiated pricing is a good optionand whether it induces sufficient learning for the low-quality server. Moreover, to identify abetter pricing scheme that benefits the firm more is of great interest.Motivated by a nascent academic research on probabilistic (opaque) selling of products inthe marketing literature, we propose another pricing scheme, uniform pricing, to manage therevenue of a quality-differentiated service firm. In contrast to differentiated pricing, the firmnow charges a uniform price to all customers who decide to procure the service. However, thecustomers who enter the system are subject to a random routing to the servers with differentquality levels. Once the randomness is unravelled, the customers are sent to different serversand queue separately. In this case, the firm sets a proper price and decides a routing policy,which are both publicly known to the customers. The customers, on the other hand, makeex ante decisions based on the expected service quality and waiting cost. In other words, thefirm offers a synthetic service product that essentially amounts to a lottery among the serviceof all quality levels. This pricing scheme resembles the probabilistic (opaque) selling strategyintroduced and studied by Fay and Xie (2008) and Jiang (2007) in retailing and travel industries.The main characteristic of such pricing strategy is for the seller to hide some attribute of a setof products and only reveal it to buyers after the payment transaction is complete. In oursetting, the hidden attribute is the service quality or, equivalently, which server to queue upto. This attribute is revealed to a customer immediately after payment as the firm maintainsparalleled queues.The primary goal of this paper is to investigate the following question. In presence ofexperience-based quality improvement, which pricing scheme, differentiated or uniform pricing,is more beneficial to the firm’s revenue management? By analytical modelling, we demonstratethat uniform pricing is indeed superior to differentiated pricing because it generates larger long-term total revenue for the firm. The underlying reason is that low quality servers improve fasterunder uniform pricing, and thus contribute higher revenue sooner. Our result shows that thepricing lever alone is not enough for effective service management. In fact, uniform pricing usesother types of levers such as operations lever (routing) and information lever (offering a lotteryon service quality) to more effectively manage the service system. Both differentiated anduniform pricing schemes have exactly the same number of controlled variables. The former hasthe prices for the servers and the latter has a uniform price along with the routing probabilities.However, in term of the types of levers, uniform pricing utilizes more, resulting in a betterperformance. Moreover, our analysis requires very mild conditions. Relaxation of several modelassumptions does not hurt the validity of our main result. Further to the main question, wealso study the impact to the relative revenue advantage of the uniform pricing from two factors:394.2. Related Literature and Positioningservers’ learning speed and their initial heterogeneity. On the one hand, in the long run, thebenefit of uniform pricing is higher when servers learn slowly compared to when they learnfast. On the other hand, depending on the servers’ quality, the relative revenue differencebetween uniform and differentiated pricing could be either increasing or decreasing in servers’heterogeneity.The next section reviews the background literature and positions our contributions. Sec-tion 2.2 details our base model and assumptions. Section 4.4 and 4.5 compare the two pricingschemes in the static and dynamic models, respectively. Section 4.6 explores how certain pa-rameters affect the revenue difference, with a focus on the impact of servers’ learning speed andtheir initial heterogeneity. Section 4.7 summarizes and concludes.4.2 Related Literature and PositioningOur study is primarily related to three streams of literature: economics of queues, learningcurve theory, and probabilistic (opaque) selling.Economics of Queues. We adopt the natural framework provided by queueing theory formodeling delay-sensitive service management. In our analysis, we closely follow the classicmodels where a monopolist charges rational customers prices for using its service where con-gestion is unavoidable; e.g. Naor (1969), Edelson and Hilderbrand (1975), Knudsen (1972),Mendelson (1985) and Chen and Frank (2004). In particular, models assuming that queuelength is unobservable to customers are more closely related to ours. See Chapter 3 in Has-sin and Haviv (2003) for a comprehensive review. Among various models along this line, notmany papers have examined the issue of service quality in the context of pricing the queueingsystem. Anand et al. (2011) study the dependence of service quality on service duration andthe resulting customers’ equilibrium behavior as well as the firm’s pricing decision. Assumingthe similar relationship between quality and speed, Tong and Rajagopalan (2014) investigatedifferent pricing schemes for a service provider to maximize revenue. In different contexts, othernotable works that explore the issue of service quality in delay-sensitive service systems includeKostami and Rajagopalan (2013), Allon and Federgruen (2007) and so forth. Most of thesepapers focus on the quality that is correlated with the service capacity. Our model, however,does not require a interrelationship between service quality and capacity. More importantly,none of the previous literature along this line considers experience-based quality improvement,whereas we manage to fill this gap. These differences distinguish our work in important waysfrom the research of others.Learning Curve Theory. By including learning model in our study, we want to analyticallyunderstand the process in a service operations environment for the purpose of comparing firm’spricing schemes based on their revenue performance. We do not aim to contribute to thetheory of learning per se. However, we do want to be consistent with the established theory inthe literature. Learning-by-doing (learning curve) has been studied mainly in manufacturing404.2. Related Literature and Positioningfor competitive settings (Cabral and Riordan, 1994; Dasgupta and Stiglitz, 1988; Fudenbergand Tirole, 1983) and non-competitive settings (Adler and Clark, 1991; Lapre´ et al., 2000).There are also some papers studying the learning effect in service contexts, e.g. healthcare(Edmondson et al., 2003) and call center setting (Gans and Zhou, 2002; Gans et al., 2010;Ryder et al., 2008).The most common model in the literature that characterizes the rates at which learningoccurs is the log-linear “learning curve” (Yelle, 1979). This type of particular functional formshas been widely used in manufacturing, which states that production cost for a product unitdecreases as cumulative volume increases (Spence, 1981). In fact, there is empirical evidencethat it also applies to service environment (Gustafson, 1982). Hence, we extend this model toservice operations and employ a learning curve where service quality is increasing in servers’cumulative experience and asymptotically approaches to some upper limit. In this sense, Misraet al. (2004) is very close to our work. They also study experience-based learning, but in asalesforce design context. In particular, they include the decisions of both pricing and staffing,whereas the latter decision is absent in our model. Nevertheless, the customers’ choice (arrivingdemand) is exogenous in Misra et al. (2004), but in our model, it is affected by the chargedprice. Endogenizing the demand rates undoubtedly incorporates an important practical factorto the model, and therefore deserves a careful study. Furthermore, unlike Misra et al. (2004)who consider differentiated pricing only, our main focus is how to avoid the potential pitfallof differentiated pricing. Finally, while some of the previous literature has also studied thecounterpart effect of learning, i.e. forgetting (McCreery and Krajewski, 1999; Shafer et al.,2001), we do not model such effect. As mentioned, our focus is on the comparison of the twopricing schemes. Hence, we try to limit the sources of possible impact. Besides, includingforgetting effect in our model does not provide more interesting results.Probabilistic (Opaque) Selling. Our work also belongs to a growing body of literature thatstudies probabilistic (opaque) selling, whereby a seller hides some attribute of a product untilafter the buyers purchase it. The practice of Priceline and Hotwire exemplify such sellingstrategy. The earliest works in this stream include Fay and Xie (2008), Jiang (2007) and Jerathet al. (2010), which lead many followers to pursue answers to the following question: When andwhy is probabilistic (opaque) selling attractive to firms? Researchers from both marketing andoperations management have provided several plausible explanations why firms should adoptthis novel selling strategy under certain conditions. According to their findings, probabilistic(opaque) selling helps price discriminate heterogeneous customers and yields higher revenue(Fay and Xie, 2008; Jiang, 2007); it reduces mismatches between demand and supply (Gallegoand Phillips, 2004; Jerath et al., 2010); it softens price competition for the more lucrativemarket segment (Shapiro and Shi, 2008); it exploits consumer’s bounded rationality (Huangand Yu, 2014); it facilitates efficient inventory management (Elmachtoub, 2014; Fay and Xie,2015); it profitably disposes excess capacity in a vertically differentiated market (Zhang et al.,2014). Our work contributes to this stream of literature by providing another reason to advocate414.3. Basic Model and Assumptionsprobabilistic (opaque) selling - when quality improvement is experience-based, it induces qualityimprovement of the low quality servers such that the long run revenue can be improved.While the proposed uniform pricing is a form of probabilistic (opaque) selling, we recognizetwo important features that have been largely neglected in the previous research. First, proba-bilistic (opaque) selling has never been applied to a delay-sensitive service setting. This paper isthe first attempt to introduce such a new pricing scheme to congestion-susceptible environment.It is both interesting and practically useful to identify new realm where probabilistic (opaque)selling is viable and even preferable. Second, with an exception of Zhang et al. (2014), onlyhorizontally differentiated market has been investigated. In our setting, however, the differen-tiation is vertical. Moreover, the differentiating attribute, service quality, is not exogenous asoften assumed in horizontal differentiation models. Rather, it is endogenously determined bythe pricing strategy via servers’ learning and improvement process.4.2.1 Our ContributionsThere are two main contributions from this paper. (1) Our study provides insights on howservice systems should be managed in the presence of experience-based service quality improve-ment. For example, we show that the firm should adopt the proposed uniform pricing schemerather than the regular commonly seen pricing scheme. The uniform pricing takes advantage ofpricing, operations and information levers to effectively manage the system so that the servicequality can be improved faster. (2) We add an important new dimension to the studies onprobabilistic (opaque) selling. For the first time, this new pricing strategy is investigated in thecontext of service system with congestions. Besides, we are among the first few research thatfocus on the vertical differentiation of the product.4.3 Basic Model and AssumptionsIn this section, we describe the basic model and make some assumptions that follow through themain analysis. The basic model is the classical queueing model in a single server case (Edelsonand Hilderbrand, 1975; Naor, 1969). The analysis of our main model can be reduced to thatof this one. To be specific, a market of potential customers arrive at a monopolist to procureservice, which is provided by a single server. Customers are homogeneous in the valuationtowards the service. This service valuation, a, is a deterministic function of the server’s qualitys in providing the service; i.e. a = a(s). Before proceeding to the formal model, we make twoimportant assumptions here concerning the service quality.(1) Generally speaking, the function a(s) is increasing and concave (Misra et al., 2004).However, to simplify our analysis without losing insights, we assume a(s) = s. Considering astrictly concave valuation-quality function does not harm the validity of our results. In fact,if a(s) is strictly concave in s, then uniform pricing could perform better than differentiatedpricing even with fewer degree of freedom (to be explained later). To get a concise exposition,424.3. Basic Model and Assumptionswe henceforth employ a to represent both valuation and quality, and interchangeably use thetwo terms.(2) We do not require the quality to depend on service capacity. In fact, in the main analysis,we assume that service quality is independent on capacity. Besides, the service duration isnot affected by quality either. We are aware that in certain contexts these two measures arecorrelated; e.g. Gans (2002) (congestion is a serious and costly problem) and Anand et al. (2011)(service is customer-intensive). Our analysis and results can be easily modified according totheir specific relationship. However, there are many situations where the service time is not amajor concern and service quality is perceived from other angles such as the server’s ability,special skills and established reputation (hairstylists, chiropractors, etc). This kind of qualityalso plays an important role in many service systems. Moreover, the improvement on such kindof quality is closely based on server’s accumulated experience. Therefore, while we acknowledgethe existence of various other kinds of quality, we focus on capacity-independent service quality.Now, we detail the the basic model by describing the customers’ behavior and the firm’sdecision.4.3.1 Customers’ BehaviorThe firm decides a price p and charges it for admission, operates at an exponential servicetime with mean µ, and adopts the first-come-first-serve (FCFS) priority rule. The arrival ofthe potential rational customers is according to a Poisson process with rate Λ. They do notknow the exact queue length, but they know all the other parameters from which they canpostulate the expected queue length. Hence, the customers weigh over the valuation and thetotal price (sum of the nominal price and the waiting cost) of the service. We focus on mixedstrategy equilibrium concerning customers’ queue-joining behavior. Since the customers arehomogeneous, the equilibrium is symmetric where they all form a common probability withwhich to join the queue (Hassin and Haviv, 2003). Customers who do not join never come backand the demands are lost. As a result, the proportion of customers who join the system alsoforms a Poisson arrival. Let the arrival rate be λ ∈ [0,Λ], then the average total time spent inthe system is given by W (λ) = 1/(µ − λ). We assume that customers incur a congestion costthat is linear in the total waiting time with a margin c. Therefore, the proportion of joinedcustomers is found by solvinga = p+ cW (λ). (4.1)Typically, three market outcomes are possible - full (λ = Λ), partial (0 < λ < Λ), or zero(λ = 0) market coverage. We will closely look at the partial coverage case. In other words, thesystem will get too crowded that not all the customers will choose to join, i.e. µ < Λ, and thevaluation is high enough that at least one customer will join, i.e. a > c/µ. The term c/µ isused because customer’s waiting time only consists of the service duration, which has expectedvalue 1/µ.434.3. Basic Model and Assumptions4.3.2 Firm’s DecisionKnowing the customers’ behavior, the firm chooses a price to maximize its revenue, which issimply pλ. Since in our model the congestion cost is paid by customers, the firm does not incurany cost associated to delay. That is, the firm solves the optimization problem max pλ. Theprice and the served demand are related in equilibrium by (4.1), andλ = µ− ca− p.Hence, the firm’s problem is(B’) maxp≥0p(µ− ca− p).Instead of using price as a decision variable, we can alternatively formulate an equivalent opti-mization problem using the served demand λ as decision variable:(B) maxλ(a− cµ− λ)s.t. 0 ≤ λ ≤ µ− ca.The constraint in (B) is due to the fact that the corresponding price cannot be negative. Thesecond formulation is valid because of our partial market coverage assumption. Under suchassumption, the constraint λ ≤ Λ becomes redundant. This formulation, however, is lessintuitive as the firm actually decides λ implicitly via pricing. We will work on formulation(B) as it turns out to be convenient for our analysis later. Both problems (B’) and (B) areconvex optimizations and are easy to solve. In addition, the partial market coverage assumptionensures an interior optimal solution. We find that the optimal price isp∗ = a−√caµ .Under this price, the corresponding served demand (market share) isλ∗ = µ−√cµaand the maximized revenue isr∗ = p∗λ∗ = (√µa−√c)2.This basic model has been intensively studied in literature. For more detailed steps of the abovecomputation, refer to Hassin and Haviv (2003).444.3. Basic Model and Assumptions4.3.3 Assumptions in Multi-Server CaseWe now consider the monopolist firm with multiple servers who are heterogeneous in servicequality. There are some previous works on pricing in multi-server environment (Bradford, 1996).We adapt those models to our setting, particularly for the ease of analysing and comparingdifferentiated and uniform pricing schemes. Let N = {1, 2, · · · , n} be the index set of all theservers, and without loss of generosity suppose 0 < a1 ≤ a2 ≤ · · · ≤ an < amax, where amaxis the maximum service quality possible. Although servers differ in quality, their capacity isthe same µ. This is to apply our assumption that service quality is capacity-independent.All customers have the same valuations toward using the service provided by these servers.Moreover, the waiting cost function has exactly the same margin c for all customers using anyserver. Depending on the pricing schemes, the resulting models are a bit different in term ofrouting. Under differentiated pricing, a price is posted for each server. The customers needto decide whether to procure the service, and if yes, which server to queue in front of. Hence,the joining customers form N separate demand streams. Again, we assume that customersapply mixed strategy. Therefore, the firm actually maintains N paralleled M/M/1 queues andoperates in the same way as it does in the single server case for each server.Under uniform pricing, the firm announces a single price and decides the routing policy.Like the price, the routing policy is also known to all customers. However, we focus on static(not dependent on the queue length) random routings. As in the probabilistic (opaque) sellingof physical products, customers only know the distribution but not the exact server routed to.In other words, the firm is essentially offering a lottery. We assume that the customers arerisk-neutral and they consider the expected service value and expected waiting cost to makea decision. An important assumption regarding the implementation of uniform pricing is thatfirm maintains paralleled queues. That is, the firm randomly routes the customer immediatelyafter the price is paid, and the customer queues in front of the assigned server. In contrast tothis assumption, the firm could use a non-idling routing policy and have the customers wait inone line. To the customers, which server will eventually provide the service is still random inthis case, but the randomness is not necessarily unravelled right after they enter the system.These two alternatives (paralleled queues and single queue) are in the same spirit as the “earlycommitment” and “late commitment” discussed in Fay and Xie (2015).In our model, we adopt paralleled queues assumption (“early commitment”) for two reasons.First, in order to implement a non-idling routing policy, the firm needs to monitor the systemcontinuously in time, which is a large administrative investment. There will also be an informa-tional burden to the customers because the policy will be more complex (e.g. it may depends onwhich servers are idle). Hence, routing the joining customers immediately is easier for both thefirm and the customers. Second, “late commitment” gives the firm a huge operational advan-tage as it results in a risk pooling system. This is in itself an attractive feature. However, sincedifferentiated pricing cannot utilize risk pooling, we assume “early-commitment” to maintaina fair comparison between these two pricing schemes.454.4. Static Model Without Learning EffectFinally, we keep our focus on the partial market coverage outcome:cµ < a1, Λ > nµ. (4.2)The first inequality ensures that at least one customer will use the server with lowest qualityunder differentiated pricing. If, for example, c/µ > ak for some k > 1, then no customerwill choose to queue in front of servers 1, 2, · · · , k. As a result, there are only N − k effectiveservers. This is potentially another disadvantage associated with differentiated pricing that canbe mitigated by uniform pricing’s dictated routing. However, we do not consider this simplercase. The second inequality in (4.2) means that the firm does not have enough capacity toserve the whole market. We make this assumption to ease our analysis by eliminating theboundary solution where the whole market is captured (see next section). Doing this simplifiesthe analysis without restricting the validity of our result.4.4 Static Model Without Learning EffectIn this section, we analyse the differentiated and uniform pricing schemes in a static model,where servers’ quality does not change over time. We will compare the two pricing schemeswith respect to the generated revenue as well as the served customer volumes. To capture theessence of relevant insights, it is enough to look at a firm with just two servers. Generalizationto the N -server case is easy but does not add more useful results. Therefore, let us focuson a monopolist with two servers whose services are valued as a1 and a2, respectively, where0 < a1 ≤ a2 < amax.4.4.1 Differentiated PricingUnder differentiated pricing, the firm sets prices p1 and p2 for the two servers. The customerschoose whether to join a queue, and which one to join if they are joining. Resultantly, thecustomers form a common mixed strategy that assigns three probabilities to the options of notjoining, joining server 1 and joining server 2. As mentioned, the mixed strategy equilibriumgenerates two streams of customers, each of which can be seen as a single server case. Formally,we establish the following lemma.Lemma 4.4.1. Under the partial market coverage conditions (4.2), the firm’s problem can beformulated as(S-Diff) maxx∈R2rD(x) =∑i=1,2xi(ai −cµ− xi)s.t. 0 ≤ xi ≤ µ−cai, ∀i = 1, 2. (4.3)For i = 1, 2, the optimal price isp∗i = ai −√caiµ ,464.4. Static Model Without Learning Effectthe market share isλ∗i = x∗i = µ−√cµai,and the generated revenue isr∗i = (√µai −√c)2;thus the total revenue is r∗D(x) =∑i r∗i .To intuitively explain the reason why the system can be seen as two separate M/M/1queues, note that with a common probability distribution over server 1, server 2 and leaving,no customer will take a unilateral deviation. Indeed, joining one queue with larger probabil-ity increases the congestion level and thus results in negative customer surplus, whereas thecustomer surplus remains zero if the not joining option has a higher probability.4.4.2 Uniform PricingThe firm could alternatively charge a uniform price to all customers that decide to use theservice. In addition, the firm also decides a static random routing policy, which is characterizedby parameters βi, i.e. the probability that the customer is routed to server i, for i = 1, 2. Sinceβ1 + β2 = 1, β1 alone can represent the policy. The random routing is realized immediatelyafter the customers pay the price and enter the system. As a customer is routed to one server,jockeying between queues is not allowed. As mentioned, we assume that customers are risk-neutral and hence the valuation on the service is the expectation of the service valuations fromboth servers. Similarly, the waiting cost is also the expected cost. As a result, given the priceand the routing policy, the customers have to make ex ante decisions whether to procure theservice. In this sense, the uniform pricing is in nature a probabilistic (opaque) selling strategy,where the firm offers an opaque service.Let the uniform price be po, and the valuation to the opaque service be a¯ = β1a1 + β2a2.Suppose at equilibrium the customers who join the system cover a market of size 0 < λo < Λ(again, we apply assumption (4.2)), then we formulate the firm’s problem in the followinglemma.Lemma 4.4.2. Define y = (y1, y2) ∈ R2 as our decision variable. The firm’s problem can beformulated as(S-Unif ’) max0≤y≤µrU (y) =∑i=1,2yi(ai −cµ− yi)s.t.∑i=1,2yiai ≥∑i=1,2cyiµ− yi. (4.4)Given a solution y, we can recover the routing policy, the uniform price and the market share474.4. Static Model Without Learning Effectby the following transformation.βi =yiy1 + y2i = 1, 2;po =∑i=1,2(βiai −cβiµ− yi);λo = y1 + y2.In this lemma, we follow the spirit of formulation (B) and do not use price as the decisionvariable. Rather, we optimize over the two induced demand streams. This is because that theprice and the total served demand are entangled in one equation and it is hard to represent onein term of the other. This is why we prefer formulation (B) to (B’).4.4.3 ComparisonThis subsection compares the revenue generated by the differentiated and uniform pricing inthe static model and comments on the comparison. First of all, we take a closer look at theproblem (S-Unif’) and solve for its optimal solution. One important observation is that theconstraint (4.4) is redundant.Lemma 4.4.3. Problem (S-Unif ’) is equivalent to(S-Unif) max0≤y≤µrU (y) =∑i=1,2yi(ai −cµ− yi).Due to the above lemma, we just need to compare problems (S-Diff) and (S-Unif). Theyhave exactly the same objective function, but the feasible set of (S-Unif) is clearly larger thanthat of (S-Diff). Consequently, the optimal revenue under uniform pricing is no worse thanthat under differentiated pricing. That is,r∗U ≥ r∗D. (4.5)In fact, because both problems are convex programs, and the optimal solution to (S-Diff), x∗,is an interior point, we deduce that x∗ also maximizes rU (y). Another more direct way to seethis is simply by solving (S-Unif). To be specific, we observe that rU (y) is strictly concave iny and is separable with respect to its components. By solving the first-order conditions, wehave y∗ = x∗ and the equality in (4.5) holds. Here we stress the importance of the assumption(4.2), especially that the low quality server attracts at least one customer (a1 > c/µ). Had thisassumption been removed, x∗ would not be an interior point any more and r∗U would be strictlylarger. With assumption (4.2), the two pricing schemes yield to the same revenue in a staticmaximization problem. We write this formally as our first result.Proposition 4.4.4. If the firm only considers a static pricing problem, then differentiated anduniform pricing are equivalent at optimality. They induce the same market coverage, assign the484.5. Dynamic Model With Learning Effectsame amount of customer volume to the servers, and generate the same revenue for the firm.We make three remarks with respect to the comparison. (1) both pricing schemes leave thefirm the same number of decision variables: two prices for differentiated pricing and a price anda routing probability for uniform pricing. Hence, in term of the degrees of freedom, the twoschemes are truly alternative and the comparison is fair. However, uniform pricing utilizes twotypes of management levers, which are pricing lever (the uniform price) and operations lever(routing policy). In contrast, differentiated pricing only applies pricing lever. Although the firmcan use price to affect customer’s choice, which in turn determines the distribution of customervolumes over the two servers, the impact is indirect compared to directly routing the customers.(2) The intuition behind Proposition 4.4.4 is the mutual mimicking of the two pricing schemes.For any customer volumes differentiated pricing induces for the two servers, uniform pricingcan induce exactly the same size and distribution of the market share. The way is to use thepricing and routing levers mentioned above. The converse is also true for differentiated pricing.(3) Although in the one-period model the equivalence of the two pricing schemes seems quiteintuitive based on the last remark, this intuition does not work once we consider multiple-periodproblem. Specifically, the inequality (4.5) could be strict once we consider the learning effect,which is discussed in the next section.4.5 Dynamic Model With Learning EffectIn the presence of experience-based service quality improvement, how does the long term totalrevenue generated by uniform pricing compare to that of differentiated pricing? We answerthis question in this section by considering a multiple-period model where the firm dynamicallyprices the service using either differentiated or uniform pricing. The dynamic in this systemis the quality improvement due to servers’ learning as they serve more customer volume. Thelearning curve is assumed to be increasing and concave with an asymptotic upper bound. Hence,more customers served by a server in the current period means a larger quality improvementin the next period. We assume that the time for the server to learn and improve quality issmall compared to a single period. Therefore, the quality improvement is accomplished beforethe new pricing season starts. The firm’s goal is to maximize the total revenue. The trade-offis between a higher current revenue (with smaller customer volume) and improving the servicequality sooner to generate higher revenue in the future.Our results show that uniform pricing is advantageous in that it generates more total revenuethan differentiated pricing does. To give a foretaste of why uniform pricing is better, let usconsider the following example. Consider a single-period model again, and let β1 = β2 = 1/2.This means that the routing policy is to send customers to servers with equal probability (purerandomly). We believe that this policy is one of the simplest to implement, and it avoids muchadministrative and informational burden to both the firm and the customers. As mentioned inthe previous section, uniform pricing utilizes both pricing lever and operations lever to manage494.5. Dynamic Model With Learning Effectthe system. As such, dictating a half-half routing is to directly affect the operational measuresin the system. Denote the customer volume at optimality by λ¯i for server 1 and 2, respectively.The expected quality a¯ = (a1 + a2)/2. Then,λ¯i = µ−√cµa¯ i = 1, 2.Compare to the customer volumes under differentiated pricing, we find that λ¯1 + λ¯2 > λ∗1 + λ∗2and λ¯1 > λ∗1 (by monotonicity and concavity of the above function). Therefore, althoughuniform pricing with half-half routing dilutes the revenue, the low quality server (server 1)gets more customer volume to serve. This is advantageous in the far-sighted sense because thelow quality server will become much better in the future, helping the firm gain more revenue.Moreover, the customers that high quality server gets is less (λ¯2 < λ∗2); but this will not offsetthe benefit of training the low quality server because the learning curve is assumed to be strictlyconcave. In other words, the higher quality servers have no more room for large improvement,so why not send some of their customers to train lower quality servers? This shows the powerof operations lever that uniform pricing can utilize. In the following, we formally build theargument that uniform pricing is preferred when learning effect exists.4.5.1 Model FormulationFirst of all, let us describe the function that characterizes the learning effect. Write this qualityimprovement function L = L(a, z), where a is the server’s starting quality and z representsthe accumulative experience. Much of the literature on learning curves in the manufacturingcontexts uses units of output as a measure of experience (Fudenberg and Tirole, 1983; Spence,1981). In the service settings such as ours, a plausible candidate to measure experience is thecustomer volume. Hence, suppose that z is given by the total number of customers served fromthe beginning. As mentioned, the function L(a, z) is assumed to be increasing and concave in z.Furthermore, it approaches to an upper bound as z becomes larger. Denote this upper boundby amax, which is the maximum service quality a server could possibly achieve. Hence, basedon these assumptions, a proper improvement function has the formL(a, z) = amax − (amax − a)e−δz, (4.6)where δ > 0 is the learning speed. The larger δ is, the faster the server can learn and thusimprove his quality sooner. In general, it is possible that the learning structure differs fromserver to server (Gans et al., 2010). However, we assume that the servers have a commonlearning curve with the same amax and δ, because our results will not change without thisassumption (to be explained later).Consider a finite horizon dynamic model with time period t = 1, 2, · · · , T . We add anothersubscript t to all the relevant notations to represent time. Then, based on the above discussion,504.5. Dynamic Model With Learning Effectwe haveai,t+1 = L(ai1,t∑k=1λik), i = 1, 2; t = 1, · · · , T.In the above, λik is the customer volume served by server i in period k. Due to the log-linear functional form of the learning curve, we have a memoryless property for the qualityimprovement. The service quality in period t+1 is equivalently determined by the quality andthe experience gained in period t, i.e.ai,t+1 = L(ait, λit), i = 1, 2; t = 1, · · · , T.Given the dynamics of learning and quality improvement, the firm sets prices at each periodto maximize the total revenue along the planning horizon. Note that we could consider thediscounted total revenue, but there is no difference in nature as it is a finite horizon problem.The firm uses either differentiated or uniform pricing. We assume that there is no switchingbetween these two schemes during the entire planning horizon. To formulate the problems, wetake the similar approach as in the single period model. That is, the decision variables are thecustomer volumes served by the servers.Differentiated Pricing. Let the 2 × T matrix X = (xit) be the decision variable, where xitrepresent the customer volume of server i at time period t. Then, the firm’s problem is(M-Diff) maxRD(X) =T∑t=1∑i=1,2xit(ait −cµ− xit)s.t. 0 ≤ xit ≤ µ−cait, ∀i, t; (4.7)ai,t+1 = L(ait, xit), i = 1, 2; t = 1, 2, · · · , T − 1.Uniform Pricing. In each time period t, let pot be the uniform price and βit be the routingprobabilities. Our decision variable is the 2 × T matrix Y = (yit), where yit is the customervolume of server i at time period t. Hence, the total customer volume is given byλot =∑i=1,2yitβit.With a straightforward generalization from the single period model, the firm’ problem is(M-Unif) maxRU (Y) =T∑t=1∑i=1,2yit(ait −cµ− yit)s.t.∑i=1,2aityit ≥∑i=1,2cyitµ− yit, ∀t; 0 ≤ yit ≤ µ, ∀i, t; (4.8)ai,t+1 = L(ait, yit), i = 1, 2; t = 1, 2, · · · , T − 1.514.5. Dynamic Model With Learning EffectGiven a solution Y, the price at period t is recovered byβit =yity1t + y2ti = 1, 2;pot =∑i=1,2(aitβit −cβitµ− yit).Note that problem (M-Unif) is essentiallymaxRU (Y) =T∑t=1potλot.Once we take into account the learning effect, the firm will have incentive to induce largedemand in the early periods. Based on the customers’ behavior, lower price always leads tolarger demand. Hence, the constraint (4.8) is to make sure that pot is non-negative for every timeperiod t. As a result, unlike in the single period model, the constraint (4.8) is not redundantand cannot be dropped for free.4.5.2 ComparisonSimilar to the observation in the single period model, here we find that the objective functionsin (M-Diff) and (M-Unif) are exactly the same. In addition, condition (4.7) implies condition(4.8). To see this, suppose X satisfies (4.7), then automatically0 ≤ xit ≤ µ, ∀i, t.In addition, rewrite (4.7) asait ≥cµ− xit, (4.9)and note xit ≥ 0. Finally, multiplying both sides of (4.9) by xit and summing over i shows thatX also satisfies condition (4.8). Therefore, the feasible set of problem (M-Unif) is larger thanthat of (M-Diff), resulting in our main result.Theorem 4.5.1. If the firm considers the learning and quality improvement effect over multipleperiods, then the total revenue generated by differentiated pricing is no higher than that generatedby uniform pricing. More precisely,RU (X∗) ≥ RD(Y∗). (4.10)The intuition behind Theorem 4.5.1 is that no matter what size of customer volumes dif-ferentiated pricing gets, uniform pricing can mimic by inducing the same total demand anddistributes it to the servers using proper routing probabilities. However, different from Propo-sition 4.4.4, the converse of the previous statement is not true. In particular, for the low qualityserver, uniform pricing can generate a large customer volume that differentiated pricing is not524.5. Dynamic Model With Learning Effectable to. Indeed, if a1t < a2t, then a1t < a¯t for any routing policy where β1t > 0. Hence, alow quality a1t places much limitation on the largest demand differentiated pricing can possiblyinduce for server 1; uniform pricing mitigates this situation by only showing customers theexpected quality. Therefore, the inequality in (4.10) could be strict. Take the following three-period model for an example. The initial service values are a11 = 1, a21 = 8. The learning curvehas parameters amax = 24 and δ = 1. Then, solving (M-Diff), we have the total maximizedrevenue 37.33; solving (M-Unif) gives total revenue 44.68, which is about 20% larger. Notethat in the first period, the optimal uniform pricing scheme induces 0.76 customer volume forserver 1, while the optimal differentiated pricing only induces 0.2 customer volume for server1, which is exactly the upper bound for x11 in the problem (M-Diff). Consequently, some ofthe inequalities in (4.7) will be violated by the optimal Y∗, resulting a strictly larger objectivefunction.As mentioned previously, the strict superiority of uniform pricing in the dynamic modelproves that using pricing lever alone could be an inefficient service management. Both pricingschemes optimize over the same number of variables (2T ). However, uniform pricing givesup some degree of freedom from the pricing lever but makes up by yielding to routing, animportant operations lever. Moreover, by random routing, uniform pricing also has some controlover customers expectation towards the service quality. By making the observed servers’ quality“opaque”, uniform pricing actually also plays with the information lever to manage the queueingsystem. In contrast, all the variables in differentiated pricing are prices. In term of the typeof lever, differentiated pricing resorts to only one type. Therefore, an important insight of ouranalysis is that the combination of various types of management levers can be more powerfulthan just applying one type.4.5.3 DiscussionsIn this section, we comment on our model from two viewpoints: formulation and robustness.Dynamic Programming Formulation. In the above, the problems (M-Diff) and (M-Unif) areformulated as non-linear optimizations. The concavity of the objective function is not clear.Alternatively, we can also formulate the optimization problems using deterministic dynamicprogramming. Let us write variables in column vector (whose components correspond to thetwo servers), and the single subscript represents time. The state space is service quality 0 ≤at ≤ amax. The action space is the induced customer volume 0 ≤ zt ≤ µ. The dynamic is thequality improvement, which remains the same as described:at+1 = L(at, zt).With a little abuse of notation, here L(·, ·) is computed component-wise. Letr(at, zt) =∑i=1,2zit(ait −cµ− zit)534.5. Dynamic Model With Learning Effectbe the immediate reward of taking action zt at period t when the service quality is at. Inaddition, let Rt(at) be the total optimal revenue from period t onward when the current servicequality is at; set RT+1 = 0. Then, the optimality equation is given by(DP) Rt(at) = maxz∈At{r(at, zt) +Rt+1(at+1)}. (4.11)The feasible action set At is different in the two pricing schemes. Specifically, under differenti-ated pricing, At is given by a product setADt = Πni=1{0 ≤ zit ≤ µ−cait},whereas under uniform pricing,AUt =∑i=1,2aitzit ≥∑i=1,2czit(µ− zit), 0 ≤ zit ≤ µ.As shown previously, it is not hard to establish that ADt ⊂ AUt . Resultantly, Theorem 4.5.1holds true through this formulation too.In contrast to the first formulation, we are able to derive some second-order properties forthe objective functions in (DP).Proposition 4.5.2. Let Jt(at, zt) = r(at, zt) +Rt+1(at+1), then(a) Jt(at, zt) is concave in zt for all t.(b) For each t, Rt(at) is concave in at and increasing with respect to ait (i = 1, 2).Robustness to Model Assumptions. Our model is indeed established on many simplifying as-sumptions. However, most of these assumptions are made because not only they ensure succinctanalysis but also relaxing them yields little additional insights. In other words, our main resultsremain valid if we relax those assumptions.First, the servers can be heterogeneous in many dimensions besides quality. They can bedifferent in the service capacity µ, the unit congestion cost c, the maximum achievable qualityamax and the learning speed δ. Clearly, applying these changes results in the same conclusionconcerning the comparison of the two pricing schemes as they will still have the same objectivefunction.Second, functional structure changes have little impact on our results. For example, thecongestion cost can be increasing and strictly convex. Then Theorem 4.5.1 still holds; andthe proof of Proposition 4.5.2 follows through by applying the composition rules of increasingconvex functions. We can also relax the assumption that equalizes service quality to customers’valuation on the service. That is, instead of a(s) = s, we assume that a(s) is increasing andstrictly concave (Misra et al., 2004). Then, this change, again, only mildly affects the proof of544.6. How Do Parameters Affect the Revenue Difference?Proposition 4.5.2. The optimal revenue at period t, Rt, is still increasing and jointly concave inservice quality. To note another interesting impact of this assumption change, the function a(s)being strictly concave actually makes uniform pricing more preferable. As mentioned, uniformpricing offers the customers an service with “opaque” quality, and the customers make decisionsbased on the expected quality. Hence, the valuation to an opaque service, a(s¯), will be higherthan the expectation of observed valuations, a(s), due to concavity. In fact, with the simplehalf-half routing policy (described in the beginning of this section), uniform pricing can performbetter than differentiated pricing if a(s) is strictly concave1.Third, the assumption that service quality and service capacity are independent with eachother could be unsettling to some managers. Indeed, in some situations higher quality meanslarger capacity (Gans, 2002), whereas in some other situations longer service time leads to aperception of higher quality (Anand et al., 2011). In both cases, capacity can be written asµ = µ(a). No matter how the function µ(a) looks like, once the problems are formulated, theobjective functions under the two pricing schemes always coincide. Therefore Theorem 4.5.1holds. As for Proposition 4.5.2, result (b) holds if µ(a) is increasing and concave in a; otherwiseit may fail to be true. To see this, we only need the functionv(a) := a− cµ(a)− xto be increasing and concave in a. Monotonicity follows immediately as µ(a) is increasing. Notethatv′′(a) = 2(µ′(a))2 − µ′′(a)(µ(a)− x)(µ(a)− x)3 ≥ 0,as desired. The condition that service capacity is increasing and concave in server’s quality ismet in many situations, and therefore our results are still valid. Even when µ(a) is decreasingin a, the fact that uniform pricing is still advantageous to differentiated pricing is unchanged.To sum up, the model are robust to most of the assumptions, changing of which keeps theobjective functions under both pricing schemes identical. However, there are assumptions thatdo affect our analysis significantly. For example, if the customers are risk averse rather thanrisk neutral, then uniform pricing will suffer from a loss due to its “opacity”. As a result, it isnot clear which pricing scheme is better.4.6 How Do Parameters Affect the Revenue Difference?In the previous section, we established that, compared to differentiated pricing, uniform pricinggenerates equal or higher total revenue. This section further investigates how the revenuedifference changes as some of the parameters change. First of all, we specify the way we1The construction of a(s) is available upon request.554.6. How Do Parameters Affect the Revenue Difference?measure the difference. Define∆ = R∗U −R∗DR∗D× 100%,i.e. the relative revenue advantage of uniform pricing compared to differentiated pricing. Itis the percentage increase in revenue if the firm uses uniform pricing instead of differentiatedpricing. We will use ∆ as the measure of the comparison between the two pricing schemes.Apparently, ∆ ≥ 0 and larger ∆ means that uniform pricing possesses more advantage.Basically, we are interested in the impact to the revenue advantage ∆ from three factors. Tobe specific, we look at the change in ∆ with respect to the change of the planning horizon (T ),the servers’ learning speed (δ) and the initial heterogeneity of the two servers (a21−a11). Theseparameters are closely related to the servers’ learning process (length and speed) as well as the“opacity” rendered by the uniform pricing, which are the main characteristics that account forthe revenue advantage. Hence, a study on how they affect the comparison is both interestingand useful. Rather, other parameters such as congestion cost c, capacity µ and maximumquality level amax are fixed. Since we only look at the servers’ heterogeneity at the beginning,we drop the time period subscript of quality levels for the sake of a simpler exposition. Thatis, we write a1 and a2 instead of a11 and a21 in this section. Therefore, we are interested in therevenue advantage as a function of several parameters in the problem, i.e.∆ = ∆(T, δ, a1, a2).Depending on the context, which will be made clear as we develop our analysis, we omit allthe fixed parameters in the bracket and just write the varying ones. For most of the followinganalysis, we compute ∆ numerically. Algorithms are implemented in Matlab and are run on astandard PC. In some cases, however, we also develop analytical results based on simplifyingassumptions.Our results consists of three parts. First, we study the asymptotic behaviors of ∆ withrespect to T and δ. We show that the revenue advantage vanishes as the planning horizonor the learning speed is growing large. Second, we find that whether larger learning speedleads to more revenue advantage depends on the length of the planning horizon. Third, weanswer the question how heterogeneity (a2 − a1) affect ∆. Although changing either a2 or a1can equivalently change their difference, we show an interesting finding where the two ways ofchanging drives the revenue advantage in the opposite directions.4.6.1 Asymptotic BehaviorIn this subsection, we analytically characterize the asymptotic behavior of the revenue advan-tage ∆ as the learning process becomes either very long or very fast.Proposition 4.6.1. Fix a1 and a2.(a). For every δ > 0, ∆(T ) → 0 as T → ∞.564.6. How Do Parameters Affect the Revenue Difference?(b). For every T = 1, 2, · · · , ∆(δ) → 0 as δ → ∞.Proposition 4.6.1 simply states that the revenue advantage enjoyed by uniform pricing isvanishing as the planning horizon or the servers’ learning speed approaches to infinity. There-fore, the situation where the firm should use uniform pricing and take the advantage is whenthe total time period is not too large and when servers improve the quality not too fast.We make a couple of remarks regrading this result. (1). It is obvious that ∆ = 0 if δ = 0,i.e. there is no learning effect; and by Proposition 4.4.4, ∆ = 0 when T = 1. Hence, thereis no monotone relationship overall for the two parameters T and δ. (2). Although ∆ → 0when either T or δ approaches to infinity, the underlying reasons for this same asymptoticbehavior are different. When T becomes large, the absolute difference R∗U −R∗D approaches toa constant and R∗D grows unbounded. In contrast, when δ gets large, the gap between R∗U andR∗D is closing, so R∗U −R∗D approaches to zero. Consequently, had we considered the discountedtotal revenue as the objective, ∆ would approach to a positive constant as T → ∞, becauseR∗D would be bounded by a finite number. However, result (b) remains the same.4.6.2 Impact of Learning SpeedAccording to Proposition 4.6.1 (b), the revenue advantage is eventually dropping to zero as δapproaches infinity. Nevertheless, let us suppose that the servers’ learning speed is not verylarge in this subsection. Does increasing δ increase ∆? In other words, does it benefit the firmmore when using uniform pricing instead of differentiated pricing if the servers learn fast? Sinceuniform pricing takes the advantage of the learning effect and the quality improvement process,the intuitive answer to the above questions is yes. Surprisingly, we find that this only holdstrue when the planning horizon is short. If T is large (not necessarily very large), however, then∆ could be negatively correlated with the learning speed even though δ is far from being verylarge. We will first analytically show that, when T is small, ∆(δ) is non-decreasing based onan approximation of the learning curve and some simplifying assumptions. Then, we presentsome numerical results that demonstrate the dependence of the shape of ∆(δ) on T .Monotonicity in a Simplified Case. Although the log-linear learning curve (4.6) is mostly seenin the literature, there are works that employ a linear approximation (Dasgupta and Stiglitz,1988; Jin et al., 2004). To develop tractable analytical result, we also approximate servers’learning by the following piecewise linear curve. Let zt be the custom volume for the server attime period t, thenat+1 = min{amax,at + δzt}. (4.12)Moreover, for this simplified case, we make several additional assumptions. Defineδ˜ := amax − a1µ .We assume that (1) δ ≤ δ˜, i.e. the learning in the first period is not enough for the low quality574.6. How Do Parameters Affect the Revenue Difference?server to achieve maximum quality in the second period, (2) a2 = amax so only server 1 needsto learn, and (3) T = 2.Proposition 4.6.2. Suppose the above assumptions are satisfied and (4.12) holds, then ∆(δ)is non-decreasing in δ.In Proposition 4.6.2, we are looking at a short planning horizon. Note that δ˜ is relativelyvery large (see the numerical study below), yet having a faster learner always gives uniformpricing more revenue advantage as long as δ ≤ δ˜. Indeed, short planning horizon and server’slearning fast help the uniform pricing exploit the advantage of stimulating quick and largequality improvement by routing. However, it turns out that the validity of this insight dependsvery much on T . As the planning horizon gets just a few periods longer, ∆′(δ) becomes negativeeven for relatively small δ. We show this numerically.Numerical Study. For all the numerical studies in this paper, we fix servers’ capacity, the unitwaiting cost, and the maximum quality to beµ = 1, c = 0.8, and amax = 24.For this subsection only, we suppose that servers’ initial quality levels are exogenous; a1 = 1 anda2 = 7. We have tested that varying a1 and a2 does not affect our main result. We plot ∆(δ)over the interval 0.5 ≤ δ ≤ 1.5 for several different values of T . See Figure 4.1 below. From the0.5 1 1.55101520253035Learning Speed (δ)Revenue Advantage (%)  T=2T=3T=4T=5Figure 4.1: The impact of servers’ learning speed on the revenue advantage: Dependence on T .Fix a1 = 1 and a2 = 7.plot, we observe that for any δ0, ∆′(δ0) is decreasing in T . For example, for δ0 = 0.8, ∆′(δ0)is positive when T = 2, almost zero when T = 3, and negative when T = 4 or 5. This showsthat, even if servers are not learning in a very high speed, the sign of ∆′(δ) is quite sensitive tohow long the planning horizon is. Hence, counter-intuitively, when the servers learn slowly andT is not small, the firm could incur more potential revenue loss if it uses differentiated pricingrather than uniform pricing. This is an interesting result because it illustrates the advantageof uniform pricing in a situation where one would not expect it to possess. For example, when584.6. How Do Parameters Affect the Revenue Difference?T = 5, the best revenue advantage is achieved when the learning speed is minimum (δ = 0.5).Moreover, our numerical study also confirms the analytical result in Proposition 4.6.2. ForT = 2, the revenue advantage is increasing in δ; and for T = 3, there is a threshold δ¯ ≈ 0.75that ∆ is increasing if δ ≤ δ¯.4.6.3 Impact of HeterogeneityBy numerical studies, this subsection investigates how servers’ initial heterogeneity affects therevenue advantage of uniform pricing. We fix the planning horizon T = 3 and learning speedδ = 1. Note that the cases presented below are the representative instances from our extensivecomputations. The results are valid with other different values of T and δ.Define the initial heterogeneity of the two servers ash = a2 − a1.Since the uniform pricing poses a certain degree of “opacity” to the customers, who are assumedto be risk neutral, it seems plausible that larger heterogeneity leads to more revenue advantage.However, note that the heterogeneity h can be changed by changing either a2 or a1, we showthat the two ways of varying heterogeneity lead to significantly different impacts on revenueadvantage ∆.For the two plots in Figure 4.2, we vary one quality with three fixed other quality respec-tively. In Figure 4.2 (a), ∆′(a1) < 0 for all three curves, which means that ∆ is increasing1 1.2 1.4 1.6 1.8 20510152025Server 1’s Quality (a1)Revenue Advantage (%)  a2=3a2=7a2=11(a) Varying a1 with fixed a23 4 5 6 7 8810121416182022Server 2’s quality (a2)Revenue Advantage (%)  a1=1a1=1.1a1=1.2(b) Varying a2 with fixed a1Figure 4.2: The impact of servers’ heterogeneity on the revenue advantage. Fix T = 3 andδ = 1.with h. This corresponds to our intuition: by narrowing down the gap between the qualitylevels of the two servers, the uniform pricing enjoys less advantage. However, in Figure 4.2 (b),we observe the non-monotonicity of ∆ in h, which results in the following interesting finding:594.6. How Do Parameters Affect the Revenue Difference?There exists a pair of initial quality (a˜1, a˜2) such that∂∂a1∆(a˜1, a˜2) < 0;∂∂a2∆(a˜1, a˜2) < 0. (4.13)That is, although increasing a˜2 can increase h by the same amount as decreasing a˜1, thecorresponding driving forces on ∆ can be in the opposite directions; the former decreases ∆whereas the latter increases it. From Figure 4.2, it is easy to verify that the quality pair wherea˜1 = 1.2 and a˜2 = 7 satisfies (4.13).Therefore, simply noting the relative difference in quality (h) is not enough to address thefull insight of the impact on revenue advantage from servers’ heterogeneity. It also largelydepends on the absolute value of the servers’ quality. To be more precise, the servers’ potentialof improvement matters. Basically, given a fixed initial quality difference, there is more revenueadvantage when both servers are at the early stage of learning, i.e. a1 and a2 are small and thereare more room for their improvement by learning. Take Figure 4.2 (b) for example. If server 2’squality a2 = 8, then ∆ is larger when a2 decreases to 6, which means that server 2 is at an earlierstage of learning. Of course, this claim cannot be valid once a2 is too small because, after all, therelative measure h also affects ∆ in its own right. Alternatively, we present Figure 4.3 to showhow servers’ being at earlier stage of learning benefits uniform pricing’s revenue advantage. For1.2 1.4 1.6 1.8 2246810121416Server 1’s Quality (a1)Revenue Advantage (%)  h=2h=3h=4Figure 4.3: The importance of servers’ potential of improvement. Fix T = 3 and δ = 1.three fixed values of heterogeneity h, we vary the quality level a1 and plot the corresponding∆. Clearly, all three curves are decreasing, which shows that the same amount of heterogeneityprovides less revenue advantage as servers climb up the learning curve, i.e. as their learningpotential decreases. Moreover, servers’ potential of improvement also affects the sign of ∆′(h).Generally, ∆′(h) > 0 if a1 is small whereas ∆′(h) may be negative when a1 becomes large. InFigure 4.3, for example, the dash curve (h = 3) is below the dot-dash curve (h = 4) whena1 = 1.2; however, when a1 = 1.8, their positions are reversed.To conclude this section, we give a brief summary. Since uniform pricing generates equal orhigher total revenue than differentiated pricing does in the multiple period problem, this section604.7. Conclusiontries to understand how the revenue difference between these two pricing schemes is affectedby certain parameters. Focusing on the percentage increase of the revenue, we investigate itsasymptotic behavior as the planning horizon becomes long or servers learn and improve at veryhigh speed. Under both cases, the revenue advantage vanishes. We also particularly studythe impact of servers’ learning speed and their heterogeneity in the beginning. Depending onhow long the planning horizon is, the revenue advantage and the learning speed could be eitherpositively or negatively correlated. Interestingly, when the planning horizon is long, the uniformpricing is even more advantageous if the servers learn slowly compared to if they learn fast. Theimpact of the servers’ heterogeneity cannot be fully characterized just by the relative differenceof their quality levels. Rather, servers’ absolute quality, i.e. their potential of improvement,also decides which direction a change on heterogeneity drives the revenue advantage. Theseresults provides some guidelines for the firm to estimate the benefit from using uniform pricingin the environment with varying factors such as servers’ learning speed and heterogeneity.4.7 ConclusionFor firms who own several servers to provide quality-differentiated time-sensitive services, thetraditional pricing strategy is to base the price on the customers’ valuation, which is correlatedto the service quality. However, if the quality improvement process depends on servers’ accumu-lated experience, then this differentiated pricing can only induce a limited customer volume forthe low quality servers, which hinders their learning and improvement process. Consequently,the revenue will also be curtailed. This paper proposes another pricing scheme, uniform pricing,as an efficient tool for the revenue management of a quality-differentiated service firm. Thispricing scheme resembles the probabilistic (opaque) selling strategy studied in the marketingliterature (Fay and Xie, 2008; Jiang, 2007) as it hides from the customers the ex post servicequality and presents a lottery to the customers. Hence, it affects their choices via an informa-tion lever. More importantly, the uniform pricing takes the advantage of a powerful operationslever, i.e. routing. As a result, when comparing the revenue under the two pricing schemes,although they have the same number of decision variables, uniform pricing utilizes more typesof levers than differentiated pricing does. This turns out to be the main reason why uniformpricing is better.The two pricing schemes are equivalent in a single period model. However, the advantage ofuniform pricing manifests itself in the multiple-period pricing problem. We show theoreticallythat the total revenue under uniform pricing is equal or higher than that under differentiatedpricing. Furthermore, this result holds true under considerably many alternative assumptions;but some key assumptions are crucial and cannot be changed. By numerical studies, we alsoinvestigate the impact of several parameters to the relative revenue advantage of uniform pricing.Specifically, we look at the impact of the length of the planning horizon, servers’ learningspeed and their heterogeneity. Our studies yield to some interesting results that are against614.7. Conclusionintuition. There are some possible extensions to our work. We list two of them. First, thereare other ways to model customers’ choice besides what we use in the model. Specifically,if the congestion cost is incurred to the firm rather than the customers, then we will needanother choice model to characterize customers’ decisions on service procurement. Second, thispaper considers the monopolist case, which sheds light on the firm’s pricing decisions withoutexternal forces. However, it would be interesting to consider the pricing schemes in a competitiveenvironment where firms interact.62BibliographyJ. S. Adams. Inequity in social exchange. In L. Berkowitz, editor, Advances in ExperimentalSocial Psychology, volume 2, pages 267–299. Academic Press, New York, 1965.P. S. Adler and K. B. Clark. Behind the learning curve: A sketch of the learning process.Management Science, 37(3):267–281, 1991.A. Alkan, G. Demange, and D. Gale. Fair allocation of indivisible goods and criteria of justice.Econometrica: Journal of the Econometric Society, 59(4):1023–1039, 1991.G. Allon and A. Federgruen. Competition in service industries. Operations Research, 55(1):37–55, 2007.K. S. Anand, M. F. Pac, and S. Veeraraghavan. Quality-speed conundrum: trade-offs incustomer-intensive services. Management Science, 57(1):40–56, 2011.M. Armony. Dynamic routing in large-scale service systems with heterogeneous servers. Queue-ing Systems, 51(3):287–329, 2005.M. Armony and A. R. Ward. Fair dynamic routing in large-scale heterogeneous-server systems.Operations Research, 58(3):624–637, 2010.R. Atar, Y. Y. Shaki, and A. Shwartz. A blind policy for equalizing cumulative idleness.Queueing Systems, 67(4):275–293, 2011.A. B. Atkinson. On the measurement of inequality. Journal of economic theory, 2(3):244–263,1970.W. Austin, N. C McGinn, and C. Susmilch. Internal standards revisited: Effects of social com-parisons and expectancies on judgments of fairness and satisfaction. Journal of ExperimentalSocial Psychology, 16(5):426–441, 1980.B. Avi-Itzhak, H. Levy, and D. Raz. Quantifying fairness in queuing systems: Principles,approaches, and applicability. Probability in the Engineering and Informational Sciences, 22(4):495–517, 2008.N. A. Barr. The economics of the welfare state. Stanford university press, 1993.63BibliographyP. P. Belobaba. Air travel demand and airline seat inventory management. Technical report,Cambridge, MA: Flight Transportation Laboratory, Massachusetts Institute of Technology,1987.P. P. Belobaba. OR practice - application of a probabilistic decision model to airline seatinventory control. Operations Research, 37(2):183–197, 1989.D. P. Bertsekas, R. G. Gallager, and P. Humblet. Data networks, volume 2. Prentice-HallInternational, 1992.D. Bertsimas, V. F. Farias, and N. Trichakis. The price of fairness. Operations Research, 59(1):17–31, 2011.D. Bertsimas, V. F. Farias, and N. Trichakis. On the efficiency-fairness trade-off. ManagementScience, 58(12):2234–2250, 2012.T. Bonald and L. Massoulie´. Impact of fairness on internet performance. In SIGMETRICSPerformance Evaluation Review, volume 29(1), pages 82–91. ACM, 2001.R. M. Bradford. Pricing, routing, and incentive compatibility in multiserver queues. EuropeanJournal of Operational Research, 89(2):226–236, 1996.J. Brockner, T. R. Tyler, and R. Cooper-Schneider. The influence of prior commitment to aninstitution on reactions to perceived unfairness: The higher they are, the harder they fall.Administrative Science Quarterly, 37(2):241–261, 1992.S. L. Brumelle and J. I. McGill. Airline seat allocation with multiple nested fare classes.Operations Research, 41(1):127–137, 1993.F. B. Cabral. The slow server problem for uninformed customers. Queueing Systems, 50(4):353–370, 2005.F. B. Cabral. Queues with heterogeneous servers and uninformed customers: who works themost? Working paper, 2007.L. Cabral and M. H. Riordan. The learning curve, market dominance, and predatory pricing.Econometrica, 62(5):1115–1140, 1994.G. P. Cachon and S. Netessine. Game theory in supply chain analysis. Tutorials in OperationsResearch: Models, Methods, and Applications for Innovative Decision Making, 2006.G. P. Cachon and F. Zhang. Obtaining fast service in a queueing system via performance-basedallocation of demand. Management Science, 53(3):408–420, 2007.A. M. Campbell, D. Vandenbussche, and W. Hermann. Routing for relief efforts. TransportationScience, 42(2):127–145, 2008.64BibliographyH. Chen and M. Frank. Monopoly pricing when customers queue. IIE Transactions, 36(6):569–581, 2004.Y. Chevaleyre, P.E. Dunne, U. Endriss, J. Lang, M. Lemaitre, N. Maudet, J. Padget, S. Phelps,J.A. Rodriguez-Aguilar, and P. Sousa. Issues in multiagent resource allocation. Informatica,30(1), 2005.W. K. Ching, S. M. Choi, and M. Huang. Optimal service capacity in a multiple-server queueingsystem: A game theory approach. Journal of Industrial and Management Optimization, 6(1):73–102, 2010.S. M. Choi, X. Huang, W. K. Ching, and M. Huang. Incentive effects of multiple-server queueingnetworks: The principal-agent perspective. East Asian Journal on Applied Mathematics, 1(4):379–402, 2011.Y. Cohen-Charash and P. E. Spector. The role of justice in organizations: A meta-analysis.Organizational Behavior and Human Decision Processes, 86(2):278–321, 2001.J. A. Colquitt, D. E. Conlon, M. J. Wesson, C. O. L. H. Porter, and K. Y. Ng. Justice at themillennium: a meta-analytic review of 25 years of organizational justice research. Journal ofApplied Psychology, 86(3):425–445, 2001.T. H. Cui, J. S. Raju, and Z. J. Zhang. Fairness and channel coordination. ManagementScience, 53(8):1303–1314, 2007.P. Dasgupta and J. Stiglitz. Learning-by-doing, market structure and industrial and tradepolicies. Oxford Economic Papers, 40(2):246–268, 1988.N. M. Edelson and D. K. Hilderbrand. Congestion tolls for poisson queuing processes. Econo-metrica, 43(1):81–92, 1975.A. C. Edmondson, A. B. Winslow, R. M.J. Bohmer, and G. P. Pisano. Learning how andlearning what: Effects of tacit and codified knowledge on performance improvement followingtechnology adoption. Decision Sciences, 34(2):197–224, 2003.A. N. Elmachtoub. New approaches for integrating revenue and supply chain management. PhDthesis, Massachusetts Institute of Technology, 2014.S. Fay and J. Xie. Probabilistic goods: A creative way of selling products and services. MarketingScience, 27(4):674–690, 2008.S. Fay and J. Xie. Timing of product allocation: Using probabilistic selling to enhance inventorymanagement. Management Science, 61(2):474–484, 2015.E. Fehr and K. M. Schmidt. A theory of fairness, competition, and cooperation. The QuarterlyJournal of Economics, 114(3):817–868, 1999.65BibliographyL. Festinger. A theory of social comparison processes. Human relations, 7(2):117–140, 1954.D. Fudenberg and J. Tirole. Learning-by-doing and market performance. The Bell Journal ofEconomics, 14(2):522–530, 1983.G. Gallego and R. Phillips. Revenue management of flexible products. Manufacturing & ServiceOperations Management, 6(4):321–337, 2004.N. Gans. Customer loyalty and supplier quality competition. Management Science, 48(2):207–221, 2002.N. Gans and Y. Zhou. Managing learning and turnover in employee staffing. OperationsResearch, 50(6):991–1006, 2002.N. Gans, N. Liu, A. Mandelbaum, H. Shen, and H. Ye. Service times in call centers: Agentheterogeneity and learning with some operational consequences. In Borrowing Strength:Theory Powering Applications—A Festschrift for Lawrence D. Brown, volume 6, pages 99–123. Institute of Mathematical Statistics, 2010.M. Gaynor, H. Seider, and W. B. Vogt. The volume-outcome effect, scale economies, andlearning-by-doing. American Economic Review, 95(2):243–247, 2005.X. Geng, W. T. Huh, and M. Nagarajan. Sequential resource allocation with constraints:Two-customer case. Operations Research Letters, 42(1):70–75, 2014a.X. Geng, W. T. Huh, and M. Nagarajan. Fairness among servers when capacity decisions areendogenous. Production and Operations Management, 2014b.S. M. Gilbert and Z. K. Weng. Incentive effects favor nonconsolidating queues in a servicesystem: The principal-agent perspective. Management Science, 44(12):1662–1669, 1998.R. Gopalakrishnan, S. Doroudi, A. R. Ward, and A. Wierman. Routing and staffing whenservers are strategic. Working paper, 2013.J. Greenberg. A taxonomy of organizational justice theories. Academy of Management Review,12(1):9–22, 1987.H. W. Gustafson. Force-loss cost analysis. In W. H. Mobley, editor, Employee turnover: causes,consequences, and control. Addison-Wesley, 1982.R. Hassin and M. Haviv. To queue or not to queue: Equilibrium behavior in queueing systems,volume 59. Springer, 2003.D. P. Heyman and M. J. Sobel. Stochastic Models in Operations Research: Stochastic Opti-mization, volume 2. Courier Corporation, 2003.66BibliographyT. Huang and Y. Yu. Sell probabilistic goods? a behavioral explanation for opaque selling.Marketing Science, 33(5):743–759, 2014.R. C. Huseman, J. D. Hatfield, and E. W. Miles. A new perspective on equity theory: Theequity sensitivity construct. Academy of Management Review, 12(2):222–234, 1987.K. Jerath, S. Netessine, and S. K. Veeraraghavan. Revenue management with strategic cus-tomers: Last-minute selling and opaque selling. Management Science, 56(3):430–448, 2010.Y. Jiang. Price discrimination with opaque products. Journal of Revenue & Pricing Manage-ment, pages 118–134, 2007. Forthcoming.J. Y. Jin, J. Perote-Pena, and M. Troege. Learning by doing, spillovers and shakeouts. Journalof Evolutionary Economics, 14(1):85–98, 2004.D. Kahneman, J. L. Knetsch, and R. H. Thaler. Fairness and the assumptions of economics.Journal of Business, 59(4):285–300, 1986.E. Kalai, M. I. Kamien, and M. Rubinovitch. Optimal service speeds in a competitive environ-ment. Management Science, 38(8):1154–1163, 1992.F. P. Kelly, A. K. Maulloo, and D. K. Tan. Rate control for communication networks: shadowprices, proportional fairness and stability. Journal of the Operational Research society, 49(3):237–252, 1998.N. C. Knudsen. Individual and social optimization in a multiserver queue with a general cost-benefit structure. Econometrica, 40(3):515–528, 1972.V. Kostami and S. Rajagopalan. Speed-quality trade-offs in a dynamic model. Manufacturing& Service Operations Management, 16(1):104–118, 2013.T. Lan, D. Kao, M. Chiang, and A. Sabharwal. An axiomatic theory of fairness in networkresource allocation. IEEE, 2010.M. A. Lapre´, A. S. Mukherjee, and L. N. Van Wassenhove. Behind the learning curve: Linkinglearning activities to waste reduction. Management Science, 46(5):597–611, 2000.R. C. Larson. Perspectives on queues: social justice and the psychology of queueing. OperationsResearch, 35(6):895–905, 1987.R. W. Lien. Design and control principles for distribution systems: Studies in commercial &nonprofit operations. PhD thesis, Northwestern University, 2008.R. W. Lien, S. M. R. Iravani, and K. R. Smilowitz. Sequential resource allocation for nonprofitoperations. Working paper, 2008.67BibliographyH. Luss. On equitable resource allocation problems: A lexicographic minimax approach. Op-erations Research, 47(3):361–378, 1999.A. Mandelbaum, P. Momcˇilovic´, and Y. Tseytlin. On fair routing from emergency departmentsto hospital wards: QED queues with heterogeneous servers. Working paper, 2010.A. Mas-Collel, M. D. Whinston, and J. Green. Microeconomic Theory. Oxford University Press,Oxford, 1995.J. K. McCreery and L. J. Krajewski. Improving performance using workforce flexibility in an as-sembly environment with learning and forgetting effects. International Journal of ProductionResearch, 37(9):2031–2058, 1999.H. Mendelson. Pricing computer services: queueing effects. Communications of the ACM, 28(3):312–321, 1985.S. Misra, E. J. Pinker, and R. A. Shumsky. Salesforce design with experience-based learning.IIE Transactions, 36(10):941–952, 2004.S. Moskowitz. Pay equity and american nurses: A legal analysis. St. Louis University LawJournal, 27:801, 1983.P. Naor. The regulation of queue size by levying tolls. Econometrica, 37(1):15–24, 1969.J. F Nash. The bargaining problem. Econometrica: Journal of the Econometric Society, pages155–162, 1950.H. Nikaidoˆ and K. Isoda. Note on noncooperative convex games. Pacific Journal of Mathemat-ics, 5(1):807–815, 1955.John Rawls. A theory of justice. Harvard University Press, Cambridge, MA, 1971.J. Reed and Y. Shaki. A fair policy for the g/gi/n queue with multiple server pools. Mathematicsof Operations Research, Forthcoming, 2014.L. W. Robinson. Optimal and approximate control policies for airline booking with sequentialnonmonotonic fare classes. Operations Research, 43(2):252–263, 1995.M. Rubinovitch. The slow server problem. Journal of Applied Probability, 22(1):205–213, 1985.G. S. Ryder, K. G. Ross, and J. T. Musacchio. Optimal service policies under learning effects.International Journal of Services and Operations Management, 4(6):631–651, 2008.E. S. Savas. On equity in providing public services. Management Science, 24(8):800–808, 1978.S. M. Shafer, D. A. Nembhard, and M. V. Uzumeri. The effects of worker learning, forgetting,and heterogeneity on assembly line productivity. Management Science, 47(12):1639–1653,2001.68D. Shapiro and X. Shi. Market segmentation: The role of opaque travel agencies. Journal ofEconomics & Management Strategy, 17(4):803–837, 2008.S. Solak, C. Scherrer, and A. Ghoniem. The stop-and-drop problem in nonprofit food distribu-tion networks. Annals of Operations Research, pages 1–20, 2012. ISSN 0254-5330.M. A. Spence. The learning curve and competition. The Bell Journal of Economics, 12(1):49–70, 1981.J. M. Swaminathan. Decision support for allocating scarce drugs. Interfaces, 33(2):1–11, 2003.K. T. Talluri and G. Van Ryzin. The theory and practice of revenue management. SpringerVerlag, 2005.T. Tezcan. Optimal control of distributed parallel server systems under the halfin and whittregime. Mathematics of Operations Research, 33(1):51–90, 2008.C. Tong and S. Rajagopalan. Pricing and operational performance in discretionary services.Production and Operations Management, 23(4):689–703, 2014.Y. Tseytlin. Queueing systems with heterogeneous servers: On fair routing of patients in emer-gency departments. PhD thesis, Technion-Israel Institute of Technology, 2009.A. Wierman. Fairness and classifications. ACM SIGMETRICS Performance Evaluation Review,34(4):4–12, 2007.H. M. Wu, C. C. Wu, and W. Lin. Improving inter-server fairness in active queue management.Communications Letters, IEEE, 11(11):910–912, 2007.L. E. Yelle. The learning curve: Historical review and comprehensive survey. Decision Sciences,10(2):302–328, 1979.H. P. Young. Equity: in theory and practice. Princeton University Press, Princeton, NJ, 1995.Z. Zhang, K. Joseph, and R. Subramaniam. Probabilistic selling in quality-differentiated mar-kets. Management Science, 2014.69Appendix AProofsA.1 Proofs of Results in Chapter 2Proof of Lemma 2.3.2. Since d1 > 0, there exists an integer k such that θk ≤ d1 < θk+1.Then the left derivative of R(x1, d1) at zk isk∑j=1pj1d1−n∑k+1pjaj>k∑j=1pj1θk+1−n∑k+1pjaj= 0,and the right derivative of R(x1, d1) at zk isk−1∑j=1pj1d1−n∑j=kpjaj≤k−1∑j=1pj1θk−n∑j=kpjaj= 0.Therefore, zk has positive left derivative and non-positive right derivative, and thus is themaximizer. This shows thatφ(d1) = zk(d1) =sd1d1 + akfor θk ≤ d1 < θk+1 . (A.1)By straightforward calculus, φ(d1) is concave and increasing in d1 when d1 lies in the interval[θk, θk+1). However, discontinuities occur at θk, where k = 2, 3, · · · , n. To see this, sinceak > ak−1, we haveφ(θk+) = zk(θk) =sθkθk + ak< sθkθk + ak−1= zk−1(θk) = φ(θk−),for k = 2, 3, · · · , n. This concludes the lemma.Proof of Corollary 2.3.3. Every statement except the last one is a direct consequence ofLemma 2.3.2 since the concavity and monotonicity properties are preserved by the minimumoperator in (2.5). If there exists a discontinuous point, then it must be θk for some k =2, 3, · · · , n. We consider the following cases based on where θk lies with respect to φ(θk+) andφ(θk−). Note that φ(θk+) < φ(θk−) by Lemma 2.3.2. If φ(θk+) ≥ θk, then φ(d1) = d1 by (2.5)when d1 is in a small neighbourhood of θk, in which case φ is continuous at θk. If φ(θk−) ≤ θkor φ(θk+) < θk < φ(θk−), then φ(θk+) is strictly lower than both φ(θk−) and θk, implyingx∗1(θk+) < x∗1(θk−).70A.1. Proofs of Results in Chapter 2Proof of Theorem 2.3.4. We first show that the condition is necessary. Suppose x∗1(d1) isoverall increasing and concave in d1. As mentioned above, in this case the fulfilment line muststay below φ(d1) at every threshold point θk; otherwise the monotonicity would be violated bythe downward jump at θk.From Lemma 2.3.2, φ(θk) = φ(θk+) < φ(θk−). Thus, we must have φ(d1) ≥ d1 at everyd1 = θk (k = 2, 3, · · · , n). Therefore we have the necessary conditionφ(θk) ≥ θk, for every k = 2, 3, · · · , n.Using equation (A.1) and (2.7), we have φ(θk) = zk(θk) =sθkθk + ak. Then we can rewrite thenecessary condition assθkθk + ak≥ θk, for every k = 2, 3, · · · , n,which reduces tos ≥ ak + θk, for every k = 2, 3, · · · , n.The above inequalities are equivalent to the desired results ≥ max2≤k≤n{ak + θk} = an + θn,where the last equality is due to the monotonicity of {ak} and {θk} given in (2.6) and (2.12),respectively.Now we show the sufficiency. Suppose the inequality (2.13) holds. Then the deductions inthe above proof are trivially reversible from the last step up to the statement that φ(d1) ≥ d1at every d1 = θk (k = 2, 3, · · · , n). This means that the fulfilment line is below the points(θk, φ(θk)), for each k = 2, 3, · · · , n.We now conclude the sufficiency proof by showing that x∗1(d1) is overall increasing andconcave. Defineθ˜ = supd1{φ(d1) ≥ d1}.First we claim that φ(θ˜) = θ˜. If φ(θ˜) < θ˜, then by its definition, we know that θ˜ is a point ofdiscontinuity, which must be one of θk’s. This contradicts the fact that φ(θk) ≥ θk. If φ(θ˜) > θ˜,then let δ = φ(θ˜)− θ˜ > 0. Since by (A.1) φ(d1) is right continuous, we know that there existsan ǫ > 0, such that |φ(θ˜ + ǫ) − φ(θ˜)| + ǫ ≤ δ. Hence, φ(θ˜ + ǫ) ≥ φ(θ˜) + ǫ − δ = θ˜ + ǫ, whichcontradicts the definition of θ˜. Therefore only the case of equality holds, proving the claim.Now, since θ˜ ≥ θk holds for every k = 2, 3, · · · , n, in particular, we have θ˜ ≥ θn. FromLemma 2.3.2, it follows that φ(θk−) > φ(θk) ≥ θk, for k = 2, 3, · · · , n. Hence, by the concavityof φ(d1) on each of the intervals [θk, θk+1) for k = 1, 2, · · · , n − 1, and [θn, θ˜], we deduce thatφ(d1) ≥ d1 for all 0 ≤ d1 ≤ θ˜. Therefore x∗1(d1) = d1 on [0, θ˜], which is increasing and linear.On the other hand, from the definition of θ˜, φ(d1) < d1 for d1 > θ˜; so x∗1(d1) = φ(d1) when71A.2. Proofs of Results in Chapter 3d1 > θ˜ ≥ θn, which is increasing and concave according to Lemma 2.3.2.Finally, x∗1(d1) is continuous at d1 = θ˜ by noting that φ(θ˜) = θ˜. Besides, since φ(d1) goesbelow the fulfilment line after d1 = θ˜, we have φ′(θ˜+) < 1 = φ′(θ˜−). Therefore, x∗1(d1) is overallincreasing and concave.Proof of Proposition 2.3.5. For any d1 > 0, there is some k such that φ(d1) = zk(d1) by(A.1). Hence, if s ≤ a1, then by differentiating equation (A.1),φ′(d1+) =sak(d1 + ak)2< saka2k< sa1≤ 1,where the last inequality follows from the ordering of {ak} in (2.6). In particular,φ′(0+) = sa1(d1 + a1)2∣∣∣∣d1=0= sa1≤ 1.Besides, φ(0) = 0. Therefore, combining the result in Lemma 2.3.2, we conclude that φ(d1)intersects with the fulfilment line only at d1 = 0; since φ(d1) < d1 holds for d1 > 0. By (2.5),we conclude the result.Proof of Theorem 2.3.7. Since ak and θk both strictly increase to infinity (see the discussionin the second paragraph of this subsection), we know that for any s > 0, there exists an integerk > 0 such thats < ak−1 + θk. (A.2)Then by equation (A.1), we haveφ(θk) = zk(θk) =sθkθk + ak< sθkθk + ak−1= zk−1(θk−) = φ(θk−).Apply inequality (A.2) to deduceφ(θk) < φ(θk−) =sθkθk + ak−1< θk.Hence by equation (2.5), x∗1(θk) = φ(θk) ∧ θk = φ(θk) while x∗1(θk−) = φ(θk−) ∧ θk = φ(θk−).Since φ(θk) < φ(θk−), it follows that x∗1(d1) is discontinuous at d1 = θk. Let d¯1 = θk, then itproves the theorem.A.2 Proofs of Results in Chapter 3Before the proof of all the results in this section, we provide some preliminary results. Consider astable M/M/2 queueing system, then it follows that there exists a unique stationary distribution.Let πi be the long run (stationary) probability that there are i customers in the system, includingthose waiting and being served. In addition, let π10 be the stationary probability of server 1being busy and server 2 idle; and similarly let π01 be that of server 2 being busy and server72A.2. Proofs of Results in Chapter 31 idle. We modify the approach in Rubinovitch (1985) to get the stationary distribution andother related quantities. By balancing the flow-in and flow-out of each state, we have(λ+ µ1)π10 = λπ0φ+ µ2π2(λ+ µ2)π01 = λπ0(1− φ) + µ1π2λπ0 = π10µ1 + π01µ2λπn = (µ1 + µ2)πn+1, n ≥ 1.Following the traditional notation, let ρ = λ/(µ1 + µ2) < 1 be the traffic coefficient. Then wehaveπn = ρn−1π1 = ρn−1(π10 + π01), n ≥ 1.Solving the above system of equations givesπ10 =λπ02µ1γ1 and π01 =λπ02µ2γ2,whereγ1 =ρ+ φρ+ 1/2 and γ2 =ρ+ (1− φ)ρ+ 1/2 .Furthermore, since π0 + π1 + · · · = 1, we haveπ0 =(1− ρ)(1 + 2ρ)(k + 1k )ρ2 + ((1− φ)k + φ/k)ρ+ 2ρ+ 1, (A.3)where k = µ1/µ2 is the ratio of the two service rates. Now we compute the long run averagenumber of customers both waiting and being served:L =∞∑n=1nπk =∞∑n=1nρn−1π1 =π1(1− ρ)2 .Note that π1 = π10 + π01, so we writeL = π10 + π01(1− ρ)2 =λπ02(1− ρ)2(γ1µ1+ γ2µ2).More specifically, substituting equation (A.3) gives L in term of service rates and routing policy.L = 11− ρ −1 + 2ρ(k + 1k )ρ2 + ((1− φ)k + φ/k)ρ+ 1 + 2ρ. (A.4)Finally, the average idle time for server 1, denoted by τ1, consists of the portion that no customeris in the system and that the only customer in system is at server 2. Therefore,τ1 = π0 + π01 = π0(1 + λ2µ2γ2). (A.5)73A.2. Proofs of Results in Chapter 3Similarly for server 2,τ2 = π0 + π10 = π0(1 + λ2µ1γ1). (A.6)To simplify the notations, once the policy φ¯ is made clear in the context, we will writeg1(µ1) instead of g1(µ1|µ2, φ¯). The simplification applies to other functions in all proofs.Proof of Theorem 3.3.1. We examine the first order condition to find the Nash equilibrium.Since we only consider symmetric equilibrium, the policy φr = 1/2 at equilibrium. Hence, theidle time is the same for both servers and the unfairness function will be zero by definition.Suppose the equilibrium capacity is y > 1/2, by symmetry, we just need to analyse the conditiong′1 + t = 0 when µ1 = µ2 = y.Recall the definition of the inverse-idleness function in (3.1). Substituting (A.5) and (A.3),we haveg1(µ1) =(k + 1k )ρ2 + ((1− φ¯)k +φ¯k )ρ+ 1 + 2ρ(1− ρ)(1 + 2ρ)1(1 + 1µ2ρ+1−φ¯1+2ρ) . (A.7)Substitute policy into (A.7), take derivative and replace µ1 and µ2 with y, we can write thefirst order condition as(2r − 4)y2 − (4 + r)y + t(2y + 1)(y + 1)(2y − 1)2 = 0.Define the left hand side by a function H(y). For the remainder of the proof, we show that forany finite r, H(y) has a unique zero point that is larger than 1/2.First, note that H(1/2) = −3 < 0,H ′(y) = 4(r − 2)y − (4 + r) + t(2y − 1)(16y2 + 14y + 1),and H ′(1/2) = r − 8. Moreover, H(+∞) = +∞ and H ′(+∞) = +∞ because the leading(highest order) terms have positive coefficients. Furthermore, the second order derivative isH ′′(y) = 4(r − 2) + 12t(2y + 1)(4y − 1).We now have two cases. If r ≥ 2, then H ′′(y) > 0 for all y > 1/2. Since H(1/2) < 0, regardlessof the monotonicity of H, it can intersect with y = 0 only once. Let that intersection be µ∗,then µ∗ > 1/2 and the uniqueness is proved. In addition, if r > 8, then H(y) is increasing aty = 1/2. The intersection point is closer to 1/2 as r increases because H ′′(y) increases with r.Therefore, for any small ǫ > 0, we can find a large r¯ > 8, such that for all r > r¯, µ∗ < 1/2 + ǫ.If r < 2, then H ′′(y) could be negative. Further analysis on H ′′ indicates that there is atmost one inflection point, say y˜ > 1/2. If such y˜ does not exist, then we are back to the casewhere H is convex. If y˜ exists, then H is concave on [1/2, y˜] and convex on [y˜,+∞). SinceH ′(1/2) = r − 8 < 0, we deduce that H(y˜) < 0. Hence, H(y) must have a unique zero point74A.2. Proofs of Results in Chapter 3larger than y˜. Call this point µ∗ and we finish the proof for uniqueness. To conclude part (ii),note that the inflection point y˜ increases as r decreases. Therefore, for any large M > 0, wecan find a r < 0, such that y˜ > M for all r < r; then µ∗ > y˜ > M .Proof of Proposition 3.3.2. (i). The continuity result is obvious. We only prove monotonicityand convexity. Suppose φ¯ = φProp = µ2µ1+µ2 and µ2 is fixed. Then by substituting in (A.7), wehaveg1(µ1) =(k + 1k )ρ2 + (1 + (k + 1k ))ρ+ 1(1− ρ)(1 + 2ρ)µ2(1 + 2ρ)µ2(1 + 2ρ) + ρ+ ρµ1= µ2µ1(µ1 + µ2) + µ21 + µ22µ1(µ2 + 1)(µ1 + µ2 − 1).We take the derivatives and obtaing′1(µ1) = −µ21 + µ22(2µ1 − 1) + µ32µ21(µ2 + 1)(µ1 + µ2 − 1)2< 0,andg′′1(µ1) =2(µ31 + 3µ22µ1(µ1 + µ2 − 1) + µ22(µ2 − 1)2)µ31(µ2 + 1)(µ1 + µ2 − 1)3> 0.The inequalities are due to the assumption that µ1 ≥ 1/2 and µ2 > 1/2. Hence g1 is strictlydecreasing and convex in µ1.For the case φ¯ = φHH = 1/2, we perform the same computations and getg1(µ1) =2µ2µ1(µ1 + µ2) + µ21 + µ22µ1(2µ2 + 1)(µ1 + µ2 − 1)g′1(µ1) =(µ1 + µ2)(µ2µ1 + µ1 + µ22 − µ2)(2µ2 + 1)µ21(µ1 + µ2 − 1)2g′′1(µ1) =2(µ31 + 3µ22µ1(µ1 + µ2 − 1) + µ22(µ2 − 1)2)µ31(2µ2 + 1)(µ1 + µ2 − 1)3> 0.Note that µ1, µ2 > 1/2, soµ2µ1 + µ1 + µ22 − µ2 > µ22 −12µ2 +12 > 0.Therefore, if the policy is HH, g1 is also strictly decreasing and convex.(ii). By substituting in (A.7) directly,g1(µ1|µ2, φFSF) =(k+ 1k )ρ2+kρ+1+2ρ(1−ρ)(1+2ρ)11+ 1µ21+ρ1+2ρif 1/2 < µ1 < µ211−ρ if µ1 = µ2(k+ 1k )ρ2+ρ/k+1+2ρ(1−ρ)(1+2ρ)11+ 1µ2ρ1+2ρif µ1 > µ2.75A.2. Proofs of Results in Chapter 3So the function is continuous except at µ1 = µ2. Note that SSF operates in an opposite way toFSF, thereforeg1(µ1|µ2, φSSF) =(k+ 1k )ρ2+ρ/k+1+2ρ(1−ρ)(1+2ρ)11+ 1µ2ρ1+2ρif 1/2 < µ1 < µ211−ρ if µ1 = µ2(k+ 1k )ρ2+kρ+1+2ρ(1−ρ)(1+2ρ)11+ 1µ21+ρ1+2ρif µ1 > µ2.Hence, we can just focus on proving results for FSF. Results for SSF can be obtained for freeby swapping the two continuous pieces. For example, sinceg1(µ2 − |µ2, φFSF) =1 + ρ(1− ρ)(1 + ρ+ ρ1+2ρ)< 11− ρ = g1(µ2|µ2, φFSF)g1(µ2 + |µ2, φFSF) =1 + ρ(1− ρ)(1 + ρ− ρ1+2ρ)> 11− ρ = g1(µ2|µ2, φFSF),we prove the inequalities in (3.5). Immediately, we also prove the inequalities in (3.6). There-fore, in the following, we just focus on proving monotonicity and convexity under FSF policy.For µ1 ∈ (1/2, µ2), we take the derivative and getg′1(µ1) = −1(µ2µ1 + µ22 + 3µ2 + µ1 + 1)2(µ1 + µ2 − 1)2µ21(µ21(µ1 + 1)2 + µ32(µ2 + 1)2+µ2µ21(µ1 + 5)(µ1 + 1) + 4µ42µ1 + 3µ32(2µ21 + 2µ1 − 1) + µ22(4µ31 + 9µ21 − 1))< 0.Similarly, for µ1 > µ2 > 1/2, we haveg′1(µ1) = −wg + µ22(2µ2 + 1)(2µ1 − 1)(µ2µ1 + 1 + µ22 + 2µ2)2(µ1 + µ2 − 1)2µ21,wherewg = µ31µ2(µ2µ1 + 4µ22 + 2 + 2µ2)+µ21(6µ22 + 6µ32 + 6µ42 + 3µ2 + 1)+2µ1µ42 (3 + 2µ2)+µ52 (µ2 + 2) .Hence, g′1 < 0. We have finish the proof for monotonicity.To show convexity, a more tedious algebraic manipulation is needed. We delay the detailsto Section B (a).Proof of Proposition 3.3.3. By the definition of the unfairness function, we can write it asa composition of two functions u and v,f1 = u ◦ v = u(v), (A.8)76A.2. Proofs of Results in Chapter 3where u(v) is defined by u(v) = v2 (v ≥ 0), andv(µ1) = π0(µ1µ2− 1 + 2φ¯− 1µ2(1 + 2ρ))+. (A.9)(i). We first look at φ¯ ∈ {φFSF, φProp, φHH}. Suppose that φ¯ = φFSF, then it is easy to checkthatµ1µ2− 1 + 2φFSF − 1µ2(1 + 2ρ)> 0if and only if µ1 > µ2. For 1/2 < µ1 ≤ µ2, this part becomes zero, so will f1 be. We now onlyconsider µ1 > µ2, thenddµ1(µ1µ2− 1 + 2φFSF − 1µ2(1 + 2ρ))= 1µ2+ 2ρ2µ2(1 + 2ρ)2> 0.Besides,dπ0dµ1= ρ3(µ2 + 1)((µ1 + µ2)3 + µ2(µ1 + µ2) + 2(µ1 − µ2))µ21µ2((k + 1k )ρ2 + ρ/k + 2ρ+ 1)2 (A.10)> 0.Therefore, v(µ1) is strictly increasing, and so is f1.Suppose that φ¯ = φProp. Thenv(µ1) =(1− ρ)(1 + 2ρ)(1 + ρ)(1 + (k + 1k )ρ)(µ1µ2− 1 + (µ2 − µ1)ρµ2(1 + 2ρ))+= 1− ρ1 + (k + 1k )ρ(µ1µ2− 1)+.Hence, f1(µ1|µ2, φProp) = 0 for 1/2 < µ1 ≤ µ2. Now we consider µ1 > µ2. Sinceddµ1(1− ρ1 + (k + 1k )ρ)= ρ2(1 + (k + 1k )ρ)2{1k(1 + 1k)(1− ρ) + 1k +1µ2}> 0,we direclty conclude that v(µ1) is increasing; so f1(µ1) must also be.Suppose that φ¯ = φHH. By equation (A.9), we havev(µ1) = π0(µ1µ2− 1)+.Clearly, this function is positive only when µ1 > µ2. If so, we compute thatdπ0dµ1= 2µ2((1 + µ2)µ21 + (2µ1 − 1)µ22 + µ32)(2µ2µ21 + µ21 + 2µ22µ1 + µ22)2> 0.77A.2. Proofs of Results in Chapter 3Hence, we claim that f1(µ1) is increasing on µ1 > µ2.(ii). We then suppose that φ¯ = φSSF and µ2 > 1/2 is fixed. Again, we analyse (A.9). Inparticular, we find the range of µ1 on which q := µ1µ2 −1+2φSSF−1µ2(1+2ρ) is positive. If 1/2 < µ1 < µ2,then there exists a numbera := max{12 ,√9 + 4(µ22 + µ2)− 32}≥ 12such that q > 0 if a < µ1 < µ2. Moreover, it is easy to check that a < µ2. Similarly, if µ1 > µ2,we check that there existsb :=√1 + 4(µ22 + 3µ2)− 12 > µ2such that q > 0 if µ1 > b. Hence, f1 is zero on 1/2 ≤ µ1 ≤ a and µ2 ≤ µ1 ≤ b; and itis continuous at µ1 = a and µ1 = b. Now, we focus on the positive parts and prove themonotonicity. Since q > 0, we examine that its derivativedqdµ1= 1µ2(1− 2ρ2(1 + 2ρ)2)> 0.If a < µ1 < µ2, then π0 has the same expression as in (A.10). Note that since 1/2 < µ1 < µ2now, we observe that(µ1 + µ2)3 + µ2(µ1 + µ2) + 2(µ1 − µ2) > µ2(3µ21 + 3µ1µ2 + µ1 − 2)> 0.Hence, again we have π′0 > 0. If µ1 > b > µ2, thendπ0dµ1= ρ3((2µ2 + 4)µ21 + 3µ22µ1 + µ2µ1 + µ22(1 + µ2) + 2(µ1 − µ2))µ21µ2((k + 1k )ρ2 + ρk + 2ρ+ 1)2> 0.Therefore, we prove the monotonicity for f1 on both positive pieces. The proof of convexityneeds much more computations, so we do it in Section B (b).Proof of Theorem 3.3.4. By Propositions 3.3.2 and 3.3.3, the objective functions of theservers are strictly convex and differentiable. Then according to Theorem 3.1 in Nikaidoˆ andIsoda (1955), it is left to show that the two servers’ effective strategies are constrained in convexand compact sets. Since t > 0, servers’ capacity costs are unbounded. However, the inverse-idleness function is bounded below by 1 (maximum fraction of idleness is 1). Therefore, thereexists an N < +∞, such that choosing any capacity greater than N is a strictly dominatedstrategy for both servers. In other words, the effective strategies for both servers are in compactand convex sets; and the existence of Nash equilibrium follows.78A.2. Proofs of Results in Chapter 3Due to Theorem 7 in Cachon and Netessine (2006) (the condition for two-player case dis-cussed in their paper), the uniqueness is proved if we can show that the Hessian matrix of utilityfunctions (we now treat Fi as a function of both capacities) satisfies:∣∣∣∣∣∣∂2F1∂µ21∂2F1∂µ1∂µ2∂2F2∂µ2∂µ1∂2F2∂µ22∣∣∣∣∣∣> 0, ∀µ1, µ2 s.t.∂F1∂µ1= 0, ∂F2∂µ2= 0. (A.11)Note this condition is required at equilibrium. Hence, this condition is usually hard to ap-ply. Fortunately, once adapted to our problem, we can prove (A.11) by showing the followingsufficient condition:∂2g1∂µ21∂2g2∂µ22> ∂2g1∂µ1∂µ2∂2g2∂µ2∂µ1∂2f1∂µ21> ∂2f1∂µ1∂µ2∂2g2∂µ22> ∂2g2∂µ2∂µ1 .(A.12)Observe that parameters t and ∆t are irrelevant under second order operations. Moreover,condition (A.12) also makes the parameters α(1)f and α(2)f irrelevant in our proof. Hence, ourresult holds regardless of the values of the parameters. Therefore, using the symmetric relationof µ1 and µ2 in the gi and fi functions, we only need to prove (A.12) for µ1 ≥ µ2. The resultsfor the case µ1 ≤ µ2 will follow immediately. We finish the proof by verifying (A.12), which wewill do in Section B (c).Finally, we claim that for both Prop and HH, µ1 > µ2 holds. Suppose it is not true, thatis, µ1 ≤ µ2. Then by the sufficient and necessary condition, we haveg′1(µ1) + t = 0g′2(µ2) + α(2)f f ′2(µ2) + t+∆t = 0.By directly calculations, we derive that if φ¯ = φProp,g′1(µ1)− g′2(µ2) =(µ1 − µ2)Aµ22µ12 (µ1 + 1) (µ2 + 1) (µ1 + µ2 − 1)2,whereA = µ41(µ2 +1)+ µ42(µ1 +1)+ µ22(µ1 − 1/2)(3µ21 +2µ1 +2µ2) + µ21(µ2 − 1/2)(3µ22 +2µ2 +2µ1).Since µ2 ≥ µ1 > 1/2, g′1(µ1) ≤ g′2(µ2). Similarly, if φ¯ = φHH,g′1(µ1)− g′2(µ2) =(µ1 − µ2)(µ1 + µ2)(2µ31(µ2 + 1) +B)µ22µ21(2µ1 + 1)(2µ2 + 1)(µ1 + µ2 − 1)2,whereB = µ21(4µ22 − 1)+ 2µ32µ1 + µ32 − µ22.79A.3. Proofs of Results in Chapter 4Because µ2 ≥ µ1 > 1/2, we see that B > 0, and g′1(µ1) ≤ g′2(µ2).Recall that ∆t > 0 by assumption. Therefore, in both cases we have0 = g′1(µ1) + t ≤ g′2(µ2) + t < g′2(µ2) + α(2)f f ′2(µ2) + t+∆t = 0,which is a contradiction.A.3 Proofs of Results in Chapter 4Proof of of Lemma 4.4.1. To establish formulation (S-Diff), let us first consider costumers’behavior. Given two prices p1 and p2, the demand streams for the two servers must lead to thesame customer surplus at equilibrium. Hence,ai − pi −cµ− λi= constant, for i = 1, 2,where 0 < λi < Λ is the customer rate for server i, or the market share of server i. Then, weconsider the firm’s decision on maximizing the total revenue p1λ1 + p2λ2. We deduce that thefirm will exploit the customer’s surplus at equilibrium; hence the constant in the above equalityis zero. Therefore, firm’s pricing must satisfiesai = pi +cµ− λi, for i = 1, 2. (A.13)Let xi = λi, and so the vector x = (x1, x2) ∈ R2 is the decision variable. Then, by (A.13), theprices are pi = a1 − c/(µ− x1) ≥ 0. Hence, the firm’s problem ismax rD(x) =∑i=1,2xi(ai −cµ− xi)s.t. 0 ≤ xi ≤ µ−cai, x1 + x2 ≤ Λ∀i = 1, 2. (A.14)Since the partial market coverage assumption holds, we see that the last constraint x1+x2 ≤ Λis redundant. In fact, the solution will not be at the boundary where the whole market iscovered; i.e. x1+x2 is strictly smaller than Λ at optimality. Therefore, we have the formulation(S-Diff).One immediate observation is that (S-Diff) is a convex program and the objective functionis separable in x1 and x2. Because condition (4.2) holds, the solution is an internal point.Moreover, solving each xi is to solve the same problem as in the single server case, whichdirectly leads us to the desired results.Proof of of Lemma 4.4.2. Since the firm is offering a lottery to the customers, ex ante thecustomers can see the firm as a virtual single-server system. Hence, just like in the basic model,80A.3. Proofs of Results in Chapter 4we havea¯ = po + cW¯ (λo), (A.15)whereW¯ =∑i=1,2βiµ− λoβiis the expected waiting time. Based on the customers’ equilibrium behavior (A.15), the firmseeks a maximized revenue:maxpo≥0,0≤β1≤1λopo.As can be observed, it is difficult to solve (A.15) and represent the customer volume λo in termof the uniform price po. Therefore, we let y = (y1, y2) ∈ R2 be the decision variable, whereyi = λoβi is the induced customer rate for server i. Hence, at equilibrium, the firm’s revenuecan be written asλopo = λoa¯− c∑i=1,2βiµ− λoβi=∑i=1,2yi(ai −cµ− yi).Moreover, the constraint that po ≥ 0 is translated by (A.15) toa¯− c∑i=1,2βiµ− λoβi≥ 0,which is equivalent to (by multiplying on both sides λo ≥ 0)∑i=1,2(yiai −cyiµ− yi)≥ 0.Finally, note that yi must be smaller than µ to ensure a stable system. Therefore, we haveestablished formulation (S-Unif’).To recover the decision variables, it is direct to note that y1 + y2 = λo and βi = yi/λo.Applying (A.15), we have po = β1a1 + β2a2− c∑i βi(µ− λoβi)−1, which reduces to the desiredresult.Proof of Proposition 4.5.2. We will prove it by induction on the time period t. When t = T ,since RT+1 = 0, we directly check the derivatives and see thatJT (aT , zT ) =∑i=1,2ziT(aiT −cµ− ziT)is separable in term of i, the server index, and concave in each ziT . Hence, result (a) holds for81A.3. Proofs of Results in Chapter 4t = T . Result (b) holds true vacuously for RT+1(aT+1).Suppose that the results hold for t + 1. By induction assumption, Rt+1 is increasing andconcave. By directly differentiating L with respect to the second component (recall its analyticalform in (4.6)), we see that L(a, z) is increasing and concave in z. Moreover, it is clear thatr(at, zt) is concave in zt. Since Jt(at, zt) = r(at, zt) + Rt+1(at+1) and at+1 = L(at, zt), wetherefore deduce that Jt(at, zt) is concave in zt. To see (b), note that Jt is linear in at andincreasing in each of its component. Besides, the feasible sets At (in both differentiated anduniform pricing) becomes larger when ait gets larger, we see that Rt(at) is increasing in ait.Furthermore, L(a, z) is increasing and concave in a, so Rt+1(L(at, zt)) is also concave in at.Since the concavity is preserved under maximization (Proposition B4 in Heyman and Sobel(2003)), claim (b) also holds for case t. The induction concludes that the results hold for alltime period t = 1, 2, · · · , T .Proof of of Lemma 4.4.3. Note that (4.4) in fact requires the objective function to benon-negative. Since y = 0 is feasible and the resulting objective function equals 0, the optimalobjective function should be non-negative automatically.Proof of Proposition 4.6.1. Definef(x, a) = x(a− cµ− x), cµ ≤ a ≤ amax; 0 ≤ x ≤ µ.Then f is strictly concave in x and is maximized byx∗(a) = µ−√cµa , (A.16)where x∗(a) is increasing in a. Letg(a) = maxxf(x, a) = (√µa−√c)2.Clearly, g(a) is increasing andg′(a) = µ−√cµa ≤ µ. (A.17)According to our formulations (M-Diff) and (M-Unif), we have the following bounds. (1)R∗U is dominated by the total revenue of the case where a1 = a2 = amax; i.e. both servers areat the maximum quality level in the beginning. (2) R∗D is no smaller than the total revenueobtained by myopic heuristic, which simply solves (M-Diff) as T “one-shot” sub-problems. Inthe above cases, the dynamic from learning process is simplified and therefore we haveR∗U ≤T∑t=1∑i=1,2g(amax)82A.3. Proofs of Results in Chapter 4andR∗D ≥T∑t=1∑i=1,2g(ait), where amax − ai,t+1 = (amax − ait)e−δx∗(ait).Moreover, by (A.16), x∗(ait) ≥ x∗(a1); let b := x∗(a1) > 0 be a fixed positive number. Then wehaveamax − ai,t+1amax − ait≤ e−δb. (A.18)Further, by intermediate theorem, there exists a series {ξit} such thatg(amax)− g(ait) = g′(ξit)(amax − ait)≤ µ(amax − ait) by (A.17)≤ µe−δbt(amax − a1) by (A.18) and a1 < a2.Therefore,R∗U −R∗D ≤T∑t=1∑i=1,2(g(amax)− g(ait))≤T∑t=1∑i=1,2µe−δbt(amax − a1)= 2µ(amax − a1)e−δb(1− e−δbT )1− e−δb (A.19)< 2µ(amax − a1)e−δb1− e−δb .Finally, note thatR∗D ≥T∑t=1∑i=1,2g(a1) = 2Tg(a1).Hence, as T → ∞, R∗D → ∞ whereas R∗U − R∗D is bounded by a finite constant. This provespart (a) of the proposition.As for part (b), consider the bound in (A.19) with a fixed T . As δ → ∞, we havee−δb(1− e−δbT )1− e−δb → 0,which gives the desired result.Proof of Proposition 4.6.2. By the assumptions and the approximation (4.12), the problemis simplified. In particular, we can just consider server 1. For server 2, the optimal revenueis fixed; let π∗ be server 2’s optimal revenue in one period. Then let z1 and z2 be server 1’s83A.3. Proofs of Results in Chapter 4customer volume in period 1 and 2. We consider the functionπ(z1, z2) = z1(a1 −cµ− z1) + z2(a1 + δz1 −cµ− z2),and the optimization problem (U): max{π(z1, z2)|0 ≤ z1, z2 ≤ µ}. Apply first order condition,we have∂π∂z1= a1 + δz2 −cµ(µ− z1)2= 0and∂π∂z2= a1 + δz1 −cµ(µ− z2)2= 0.Let l(s) := a1 + δs and r(s) := cµ/(µ − s)2. We directly check that for 0 ≤ s ≤ µ, l(s)intersects with r(s) exactly once; let the intersection be s = z. Hence, problem (U) has solutionz1 = z2 = z. Note that since the slope of l(s) is δ, z can be written as a function of δ; and z(δ)is increasing in δ. We claim that, as a function of δ, π(z, z) is also increasing in δ. To see this,note that z is the zero of the first order condition, and thusddδπ(z, z) = 2(δz + a1 −cµ(µ− z)2)z′(δ) + z2 = z2 > 0.Now consider the two pricing schemes. For differentiated pricing, we solve problem (U)under constraintz1 ≤ x¯ := µ−ca1. (A.20)For uniform pricing, however, because of its opacity, we solve (U) under a relatively relaxedconstraint, i.e.z1 ≤ y¯, (A.21)where y¯ is uniquely determined by solving the following equation for y:y(a1 −cµ− y ) + π∗ = 0.Hence, y¯ > x¯. Define δ1 and δ2 such as z(δ1) = x¯ and z(δ2) = y¯. Then δ2 > δ1.Finally, we characterize ∆ as a function of δ. When 0 < δ ≤ δ1, the constraints (A.20) and(A.21) are both unbinding. Hence R∗U = R∗D, and ∆ = 0. When δ1 < δ ≤ δ2, constraint (A.20)starts to be binding but (A.21) is still not. Therefore, R∗D remains fixed while R∗U is increasing(because π(z, z) is increasing in δ, as shown above); so ∆ increases in δ. When δ2 < δ ≤ δ˜, bothconstraints are binding, so both R∗U and R∗D are unchanging. Therefore, ∆ remains a constant.We conclude that ∆(δ) is non-decreasing over 0 < δ ≤ δ˜.84Appendix BDetailed ComputationsThe following appendix gives all the detailed computations that we promised in Chapter 3.These computations are tedious and elementary. Hence for the sake of brevity in the proofpart, we delay all of them to this point. All the computations are attributed to Maple (version14). We basically calculate functions’ derivatives and determine their signs in a brute forceway. Throughout this section, we use x = µ1 and y = µ2 for clearer display.(a). Proposition 3.3.2: The convexity of inverse-idleness function g1(x|y, φFSF).Suppose 1/2 < x < y. The second derivativeg′′1(x) =2(P1 + y2P2)(yx+ y2 + 3y + x+ 1)3(x+ y − 1)3x3 ,whereP1 = y8 + (6x+ 4)y7 + x(15x+ 21)y6 + 2x3(x+ 4)(x+ 1)2y + x3(x+ 1)3 > 0and P2 has the form ofP2 = b3y3 + b2y2 + b1y + b0.To be specific, b3 = 20x3 − 10 + 6x + 45x2 > 40x2 − 10 > 0, b2 = 54x3 + 27x2 − 24x + 15x4 >48x2 − 24x > 0, b1 = −9x2 + 39x4 + 4 + 49x3 + 6x5 − 9x > 36x4 − 9x2 + 36x3 − 9x > 0, andb0 = 23x3 + x6 + 15x5 + 1 + 39x4 − 3x2 > 6x3 − 3x2 > 0. Hence, g′′1(x) > 0.Suppose now x > y > 1/2. Similar computation givesg′′1(x) =2(x3Q1 +Q2)(yx+ y2 + 1 + 2y)3(x+ y − 1)3x3 .We haveQ1 = y3x3+3y2(1+y+2y2)x2+3y(6y2+1+3y+5y4+5y3)x+(20y6+30y5+34y4+25y3+1+5y+13y2) > 0and Q2 takes the formQ2 = ax2 + bx+ c,where a = 6y3+15y4+30y6+27y5+3y2+15y7 > 0, b = −9y3+9y6−12y4−6y5+15y7+6y8−3y285Appendix B. Detailed Computationsand c = −5y6 + y7 − 5y5 + 3y8 + y4 + y9 + y2 + 3y3. Further examination givesb2 − 4ac = −3y4((1− y)2 + 8y3 + 8y4)(y − 1)2(y + 1)6 < 0.Hence, Q2 > 0 and thus g′′1(x) > 0. This completes the proof.(b). Proposition 3.3.3: The convexity of unfairness function f1(x|y, φ¯).First, let us examine the case φ¯ = φSSF. For x < y, we havef ′′1 (x) =2(y7A1 + y3A2 +A3)(x2 + y2 + 3y2x+ y3 + 2yx2 + x3y + 2x2y2 + y3x)3 ,where A1 = y2+(6x+3)y+2+15x2+15x > 0, A3 = (6x4+9x5+9x2+11x3)y2+(x3+2x6)y+x6 >0. Furthermore, A2 = b3y3 + b2y2 + b1y + b0 where b3 = 30x2 − 4 + 20x3 + 15x > 16x2 − 4 > 0,b2 = 30x3 − 7 + 6x + 15x4 + 42x2 > 28x2 − 7 > 0, b1 = 15x4 + 52x3 + 39x2 − 3x − 3 + 6x5 >12x3 − 3x + 12x2 − 3 > 0, and b0 = −3x + 36x3 + 30x4 + 3x5 + 21x2 + x6 > 6x2 − 3x > 0.Hence, we conclude that f ′′1 (x) > 0.For x > y, we use the same technique (with a bit abuse of notations):f ′′1 (x) =2y(y5B1 + y2B2 +B3)(x2 + y2 + 3x2y + x3 + 2y2x+ x3y + 2x2y2 + y3x)3 ,where B1 = y2 + (6x+4)y+21x+15x2 > 0, B3 = (x6 +15x5 +39x4 +25x3 +3x2)y+ x3(x3 +9x2 + 9x + 3) > 0. Moreover, B2 = b2y2 + b1y + b0. In this case, b2 = 20x3 + 45x2 + 6x− 8 >32x2 − 8 > 0, b1 = 27x2 + 15x4 − 1 + 56x3 − 21x > 4x2 − 1 + 23x2 + 56x3 − 21x > 0, andb0 = 51x3 + 6x5 − 9x + 42x4 − 3x2 > 12x4 − 3x2 + 36x3 − 9x > 0. Hence, we conclude thatf ′′1 (x) > 0. We thus finish proof of part (ii).Consider the case φ¯ = φFSF. Note that the expression of f1 function is the same asf1(x|y, φSSF) when x < y. The above proof is valid regardless of the order of x and y. Hence,for x > y, f ′′1 (x|y, φFSF) > 0.We now are left with Prop and HH policies. If φ¯ = φHH, we look at v(x) and it suffices toprove v′′(x) > 0 for x > y. Note thatv′′(x) = 4yw(x)(x2 + y2 + 2xy(x+ y))3 ,wherew(x) = (1 + 4y + 2y2)x3 + (6y3 + 6y2 + 3y)x2 + (−3y2 + 6y4)x− y3 + 2y5 − 2y4.Note that w(y) = 8y4 + 16y5 > 0, w′(y) = 6y2(1 + 2y)2 > 0, andw′′(x) = (12y2 + 6 + 24y)x+ 12y2 + 6y + 12y3 > 0.86Appendix B. Detailed ComputationsHence, w(x) > 0 for all x > y. This shows that v′′(x) > 0.If φ¯ = φProp, v(x) is not convex. As a result, we need to analyse the original function f1.For x > y,f ′′1 (x) =2y2h(x)(x2 + y2 + xy(x+ y))4 .We repeatedly factorize h(x) and geth(x) = (((q(x+ y − 1) + r4)(x− y) + r3)(x− y) + r2)(x+ y − 1) + r1.In the above,q =(1 + y2 + 2 y)x4 +(4 y3 + 4 y + 2 + 6 y2)x3 +(4 y + 13 y2 + 14 y3 + 3 + 8 y4)x2+(4 + 12 y5 + 18 y3 + 18 y2 + 32 y4)x+ 42 y4 + 38 y5 + 21 y2 − 6 y3 − 6 y + 5 + 16 y6> 12y4 − 6y3 + 12y2 − 6y > 0,r1 = (y − 1)2(2y − 1)2(y2 − y + 1)2 > 0,r2 =(2 y4 + y3 + 2 y2 − 2 y + 1) (y3 + 2 y2 + 1)(2 y − 1)2 > 0,r3 = 1− 4y + 8y2 + 84y7 + 44y8 − 10y3 + 8y4 + 25y6 − 20y5= 44(y2 + 2.6y + 1.9)(y2 + 0.5y + 0.38)(y2 − 0.39y + 0.182)(y2 − 0.8y + 0.18) > 0,r4 = 6− 14 y + 32 y2 + 20 y7 − 32 y3 + 38 y4 + 50 y6 + 20 y5= 20(y + 2.54)(y2 + 0.94y + 1.32)(y2 − 0.15y + 0.32)(y2 − 0.84y + 0.28) > 0.Along with x > y, this shows that h(x) > 0 and therefore the f ′′1 > 0, which complete the proof.(c). Theorem 3.3.4: Validation of equation (A.12).Assume x ≥ y. There are three inequalities in (A.12) to verify for two policies. Denote thedifference of left hand side and right hand side in the three inequalities by V1, V2 and V3respective. We need to prove that they are positive.(1). V1 = ∂2g1∂x2∂2g2∂y2 −∂2g1∂x∂y∂2g2∂y∂x > 0.First, assume φ¯ = φProp. Direct computation givesV1 =r(x)x3y3(1 + x)2(1 + y)2(x+ y − 1)5 ,where r(x) is a polynomial of x with coefficients being polynomials of y. Instead of write itexplicitly, we give its derivatives w.r.t. x and the evaluations at the point x = y. Given thederivative and all the initial conditions, one can always trace back the original function by87Appendix B. Detailed Computationsintegration. Note thatr(5)(x) = 240(y + 1)(18y3 − 3y2 + 36y2x+ 24yx+ 3y + 42x2 − 2) > 6y3 − 3y2 + 8x2 − 2 > 0,r(4)(x)|x=y = 24y(257y2 + 614y3 + 396y4 + 8y − 22) > 88y2 − 22 > 0,r(3)(x)|x=y = 18y2(95y2 + 322y3 + 252y4 + 3y − 16) > 64y2 − 16 > 0,r′′(x)|x=y = 2y3(177y2 + 938y3 + 792y4 − 3y − 52) > 2y3(12y3 − 3y + 416y3 − 52) > 0,r′(x)|x=y = 3y4(21y2 + 176y3 + 144y4 − 3y − 10) > 3y4(12y2 − 3y + 80y3 − 10) > 0,r(x)|x=y = 3y5(4y2 + 2y + 1)(8y2 + 7y − 4) > 9y5/2 > 0.By the above equations, we prove that r(x) is always positive for any x ≥ y and y > 1/2. HenceV1 > 0. This is exactly the same technique that we apply throughout this part; we even bear abit abuse of notations to use r(x) again and again. Henceforth, we display the results withoutdetail explanations.Now assume φ¯ = φHH. Then we reach the conclusion V1 > 0 by noting the following:V1 =r(x)x3y3(1 + 2x)2(1 + 2y)2(x+ y − 1)5 ,where r(7)(x) = 40320(2y+1)(y+1) > 0, r(6)(x)|x=y = 42480y+167040y2+138240y3−2280 > 0,andr(5)(x)|x=y = 20280y2 + 111360y3 + 117120y4 − 3720y − 480 > 0,r(4)(x)|x=y = 24y(230y2 + 2000y3 + 2720y4 − 95y − 22) > 0,r(3)(x)|x=y = 12y2(60y2 + 1280y3 + 2240y4 − 72y − 25) > 0,r′′(x)|x=y = 8y3(−16y2 + 512y3 + 1088y4 − 28y − 15) > 0,r′(x)|x=y = 8y4(−14y2 + 128y3 + 288y4 − 6y − 5) > 0,r(x)|x=y = 16y5(4y2 + y − 1)(8y2 + 2y + 1) > 0.(2). V2 = ∂2f1∂x2 −∂2f1∂x∂y > 0.First, assume φ¯ = φProp, thenV2 =2(x+ y − 1)r(x)(x2 + y2 + xy(x+ y))4 ,88Appendix B. Detailed Computationswherer(4)(x) = −120y2x− 264y2 + 360yx2 + 264y3 + 192y4 + 1680x3y+ 3360x4y + 2880x2y2 + 2160y3x+ 2160x2y3 + 240y4x+5040x3y2 + 840x3 + 3360x4 + 360x2 + 480yx> 120xy(x− y) + 264(x2 − y2) > 0.Moreover, r(3)(y) = 12y4(44 + 274y + 231y2) > 0, r′′(y) = 4y4(38y − 24 + 211y2 + 146y3) > 0,r′(y) = 8y5(13y − 5)(y + 1)2 > 0, and r(y) = 8y6(2y − 1)(y + 1)2 > 0. Hence V2 > 0.Second, assume φ¯ = φHH, thenV2 =8(x+ y − 1)r(x)(x2 + y2 + 2xy(x+ y))4 ,wherer(5)(x) = 480y + 720x+ 2160yx− 840y2 + 10080yx2+ 8640y2x+ 3360y3 + 53760x3y + 60480x2y2+17280y3x+ 960y4 + 2520x2 + 26880x3> 840(x2 − y2) > 0.Also note that r(4)(y) = 192y2(3 + 5y + 94y2 + 225y3) > 0, r(3)(y) = 48y5(115 + 231y) > 0,r′′(y) = 16y4(−6 − 7y + 85y2 + 146y3) > 0, r′(y) = 8y5(13y − 5)(2y + 1)2 > 0, and r(y) =8y6(2y − 1)(2y + 1)2 > 0, as desired.(3). V3 = ∂2g2∂y2 −∂2g2∂y∂x > 0.Assume φ¯ = φProp, thenV3 =r(x)y3(1 + x)2(x+ y − 1)2 ,where r′′(x) = 24x2 + 24xy + 8y + 4y2 − 4 > 0, r′(y) = 6y(4y2 + 2y − 1) > 0, and r(y) =y2(8y2 + 7y − 4) > 0. Thus V3 > 0.If φ¯ = φHH, thenV3 =(x+ y)r(x)y3(1 + 2x)2(x+ y − 1)2 .Since r′′(x) = 24x + 8y − 4 > 0, r′(y) = 20y2 + y − 2 > 0, and r(y) = 2y(4y2 + y − 1) > 0, weconclude V3 > 0.89

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.24.1-0132752/manifest

Comment

Related Items