Stochastic Activity Month

September 2012

"Stochastic Operations Management"

Workshop Pricing & Staffing

September 10-11-12

SUMMARY

Advances in information technology enable online decision making based on incoming data streams. In operations management, this is relevant for assigning workforce to various different tasks (either answer phone calls or do administration in the next half hour) and for optimizing prices. This requires a blend of techniques from adaptive control theory and statistics, game theory, stochastic modeling and optimization. The keynote speakers are experts on staffing and pricing, both in traditional operations management as well as adjacent areas such as internet pricing and road pricing. Staffing is important in call centers, but also in health care - two emerging key applications are ambulance planning and staffing of emergency wards.

Keynote speakers: Frank Kelly, Marty Reiman, Assaf Zeevi

ORGANIZERS

SPEAKERS

REGISTRATION

Please fill in the online registration form by following the link to the TU/e website. There is no registration fee for this workshop. We do however ask a contribution for participating in the conference dinner (date not yet fixed, most probably Monday sep 10)

PROGRAMME

Monday September 10

Tuesday September 11

ABSTRACTS

Arnoud den Boer

Two extensions of the single-product infinite-inventory dynamic pricing problem under uncertainty

(i) The first extension considers a firm that sells multiple products, with sufficient inventory. The demand of a product does not only depend on its own selling price, but also on the selling prices of other products; in this way we can model substitute or complementary products.
We deploy a parametric demand model, with unknown parameters that can be estimated with maximum quasi-likelihood estimation.
Just as in the single-product case, the firm needs to actively experiment with selling prices in order to eventually learn all unknown parameters. If it would instead use "certainty-equivalent pricing" - always selecting prices that are optimal w.r.t. available parameter estimates -, then the parameter estimates may never converge to their true value. Optimal price experimentation can be achieved by deviating from the certainty equivalent price such that a certain amount of price dispersion is guaranteed. In the single-product case, this can be done by requiring a lower bound on the sample variance of chosen prices.
In the multidimensional case, price dispersion is measured by the smallest eigenvalue of a statistical design matrix. We show how the growth rate of this eigenvalue can be controlled by requiring the selling prices to satisfy a simple quadratic constraint, and discuss the performance of the resulting pricing policy.

(ii) The second extension considers a firm that sells a finite number of products during a finite time period. This is one of the most-studied situations in dynamic pricing and revenue management problems. In contrast to the previous setting, a certainty-equivalent pricing policy performs extremely well, and no active price experimentation is necessary. The reason is that this system satisfies an "endogenous learning property": the continuously changing marginal value of inventory implies that the optimal prices are fluctuating over time. The resulting large amount of price dispersion causes the parameter estimates to converge very quickly to their true values, which makes the certainty-equivalent pricing policy structurally better than any pricing policy can achieve in setting (i).

Eugene Feinberg

We study optimal admission to an M/M/k/N queue with several customer types. The reward structure consists of two functions:  prices that customers are willing to pay for services and of  holding costs.  Both functions may depend on a customer type.  This paper studies average rewards per unit time and describes the structures of stationary optimal, canonical, bias optimal, and Blackwell optimal policies.  Similar to the case without holding costs, bias optimal and Blackwell optimal policies are unique, coincide, and have a trunk reservation form with the largest optimal control level for each customer type. Problems with one holding cost function for all  customer types have been studied previously.  The problem with holding costs depending on customer types is more difficult. In particular, there may exist canonical policies that do not have the trunk reservation structure. This is impossible when holding costs do not depend on customer classes.

Richard Gibbens

Staffing banks of supermarket tills/Control policies in energy storage systems

This talk will address two separate topics. The first topic will be a case study of staffing a bank of supermarket tills under dynamic workloads such as to meet a customer-related key performance indicator. We use actual measured data of customer arrivals and service times gathered from multiple tills and present results on daily workloads, staffing levels and discuss open problems.
The second topic is work in progress studying control policies for balancing large scale energy storage networks. We consider a simplified version of the problem which can be formulated as a minimum cost circulation problem with buy and sell market prices for energy and a storage device limited by power constraints on energy flowing in and out as well as a overall storage capacity. We study this simplified problem in some detail using actual data on prices and a spectrum of storage parameters as preparation for a fuller model which we shall sketch. Joint work with Andrei Bejan, Janusz Bialek, James Cruise, Chris Dent, Frank Kelly and Stan Zachary.

Moshe Haviv

Regulating a queue when customers know their demand

Selfish customers do not join the queue at a rate which is socially optimal. Hence, some queueing systems call for regulations. For the unobservable (not necessarily FCFS) M/G/1 queue and homogeneous customers with respect to waiting costs and service rewards, we show how this can be done in the case that customers know their service requirements by the imposition of an entry, holding or service fee. We commenced with a unified approach, imposing minimal assumptions on the waiting functions and state the socially optimal fees.
We show that customers are always worse off under a flat entry free. As for holding vs. service fees, the answer depends on the queueing regime and/or the actual service requirement.
For example, under FCFS, service fees are preferable to all. Finally, a similar question is looked at but from the point of view of a profit maximizer. We show that this scheme leads to an excessive entry fee which implies under utilization of the server.

Frank Karsten

Resource pooling and cost allocation among independent service providers

We study a situation where several independent service providers collaborate by complete pooling of their resources and customer streams into a joint service system. These service providers may represent such diverse organizations as hospitals that pool beds or maintenance firms that pool repairmen. We model the service systems as Erlang delay systems (M/M/s queues) that face a fixed cost rate per server and homogeneous delay costs for waiting customers. We examine rules to fairly allocate the collective costs of the pooled system amongst the participants by applying concepts from cooperative game theory. (A brief introduction to cooperative game theory will be provided during the presentation.) We consider both the case where players' numbers of servers are exogenously given and the scenario where any coalition picks an optimal number of servers. By exploiting new structural properties of the continuous extension of the classic Erlang delay function, we analyze whether the games under consideration possess a core allocation (i.e., an allocation that gives no group of players an incentive to split off and form a separate pool).

Frank Kelly

Open questions on pricing for electricity networks

In future electricity networks there is expected to be substantially more supply from renewable sources (wind, solar, tidal, etc).
There is currently no clear consensus on whether the intermittency of many renewable sources can be handled by means such as demand management and storage. This talk will aim to stimulate discussion on some of the pricing issues that may, or may not, be relevant.

Anton Kleywegt

Derivative-Free Optimization Methods for Price Optimization

Consider the problem of choosing prices for a number of products in a setting in which the demands as a function of prices are not known.
Recently several researchers have studied versions of this problem, mostly with a single product and a parametric family of demand functions, and proposed methods to estimate the demand function parameters while controlling the price in such a way that the regret will be small. Another line of research does not restrict attention to a parametric family of demand functions, and does not attempt to learn the demand functions, but only searches for the optimal price through a sequence of local approximations. This type of approach to optimization has been called derivative-free optimization, and has been studied for some time. However, the pricing problem has introduced new aspects to derivative-free optimization. The talk will provide an overview of derivative-free optimization with random objective function observations, with particular aspects introduced by the multiple product pricing problem.

Vidyadhar Kulkarni

Design and analysis of concierge option for a service offering

Concierge Medicine is the most visible implementation of a new trend of introducing a fee-based premier option in a service offering. This is usually done for the purposes of segmenting customers based on their willingness or ability to wait for the service. Using a realistic yet representative model setup, we perform a detailed analysis to (i) determine the conditions (fees, cost structure, etc.) under which the concierge option is profitable for the service provider, (ii) quantify benefits accrued by the premier customers; and (iii) evaluate the resulting impact on the other customers. We show that, under a wide range of system parameters, introducing a concierge option benefits every one and also compute the magnitude of these benefits. These benefits are larger when the variance in the customer waiting costs is high and the system utilization is high. We complement these results with data on the adoption of MDVIP (the most popular concierge medical service in the US) and show that the areas where it was adopted have higher median incomes and older population and thus are amenable to higher (by about 9\%) revenues for the service provider.

PRESENTATION

Johan van Leeuwaarden

Staffing systems with admission control

In many-server systems it is crucial to staff the right number of servers so that targeted service levels are met. These staffing problems typically lead to constraint satisfaction problems that are hard to solve. During the last decade, a powerful many-server asymptotic theory has been developed to solve such problems and optimal staffing rules are known to obey the square-root staffing principle. We develop many-server asymptotics in the so-called QED regime, and present refinements to many-server asymptotics and square-root staffing for a Markovian queueing model with admission control and retrials.
(joint work with Florin Avram and Guido Janssen)

Martin I. Reiman

Dynamic Pricing for Network Revenue Management
 
We consider a dynamic pricing problem that arises in a revenue management context. It involves several resources and several demand classes, each of which uses a particular subset of the  resources. The arrival rates of demand are determined by prices, which can be dynamically controlled. When a demand arrives, it pays the posted price for its class and consumes a quantity of each resource commensurate with its class. The time horizon is finite: at time T the demands cease, and a terminal reward (possibly negative) is received that depends on the unsold capacity of each resource. The problem is to choose a dynamic pricing policy to maximize the expected total reward.
We describe a related, and much simpler, ?diffusion control problem?, the solution to which provides an asymptotically optimal control as the resource capacities and arrival rates grow large. This diffusion control is obtained as a perturbation of an even simpler, deterministic, ?fluid optimization problem?, which we also present. We show how to solve both the fluid optimization problem and diffusion control problem in the context of two ?airline? motivated problems. 
(joint work with Rami Atar (Technion))

Adam Wierman (1)

Congestion and price competition in the cloud

Abstract: The cloud marketplace has evolved into a highly complex economic system made up of a variety of services. As a result of this complicated marketplace, the performance delivered to users by cloud services depends on the the resource allocation design of the service itself and the strategic incentives resulting from the multi-tiered economic interactions among cloud providers. In this talk I will present work developing and analyzing some new models capturing the interaction this multi-tiered interaction in a manner that exposes the interplay of congestion, pricing, capacity provisioning, and performance. This talk will present joint work with Jonatha Anselmi, Urtzi Ayesta, Jayakrishan Nair, and Bert Zwart.

 

Adam Wierman (2)

Energy procurement in the presence of intermittent sources

The increasing penetration of intermittent, unpredictable renewable energy sources, such as wind energy, poses significant challenges for the utility companies trying to incorporate renewable energy into their portfolios. As a result, there is considerable discussion about how electricity markets should be restructured in order to facilitate the integration of renewable energy into the grid. Suggestions include adding additional markets, moving markets, closer to real-time, etc. In this talk, I will discuss how the optimal energy procurement of a utility company changes as a result of an increasing penetration of intermittent renewable resources, and what impact this should have on electricity market structure.
(Joint with Sachin Adlakha and Jayakrishnan Nair)

Bio: Adam Wierman is a Professor in the Department of Computing and Mathematical Sciences at the California Institute of Technology, where he is a member of the Rigorous Systems Research Group (RSRG). His research interests center around resource allocation and scheduling decisions in computer systems and services. He received the ACM SIGMETRICS Rising Star award in 2011, and has been co-recipient of best paper awards at ACM SIGMETRICS, IEEE INFOCOM, IFIP Performance, IEEE Green Computing Conference, and ACM GREENMETRICS. Additionally, he has received multiple teaching awards, including the Associated Students of the California Institute of Technology (ASCIT) Teaching Award.
 

Assaf Zeevi

Model misspecification and dynamic pricing

Sequential pricing problems typically entail some modeling of consumer purchasing behavior, or in more aggregate form, the demand curve. There is a growing literature, most of it recent, that is concerned with the impact of not knowing the demand curve a priori, and learning it on the fly (a problem often referred to as learning and earning).
In such problem instances, the decision maker constructs a class of demand models which is then calibrated to observed sales and in turn provides the basis for subsequent pricing decisions.
In this talk we will be concerned with the following aspect of this dynamic optimization problem under model uncertainty:
what happens if the assumed class of demand models does not encompass the true underlying demand curve, i.e, if the model is misspecified.
(joint work with Omar Besbes, Columbia University)

Assaf Zeevi is the Henry Kravis Professr at the Graduate School of Business, Columbia University, and currently serves as Vice Dean for Research. He graduated from Stanford in 2001, and since then has been a faculty at Columbia. His research is broadly focused on the formulation and analysis of mathematical models of complex systems. He is particularly interested in the areas of stochastic modeling and statistics and their synergistic application to problems arising in service operations, revenue management, information services, and financial engineering.
 

Bert Zwart

On the Benefits of Price Dispersion in Revenue Management

For a stylized model in dynamic pricing, it can be shown that the so-called 'certainty equivalent pricing' policy, where estimating consumer behavior and optimizing profit are completely decoupled, does not lead to optimal profit.
Thus, it is necessary to develop algorithms that ensure that the right amount of price experimentation is undertaken so as to learn and exploit consumer behavior as efficiently as possible.
Our key tool is a new result on L2 convergence rates for maximum likelihood estimators for generalized linear models with adaptive design.
(joint work with Arnoud den Boer)

SPONSORS