DIMACS Center, CoRE Building, Rutgers University

**Organizers:****James Dana**, Northwestern University, j-dana@kellogg.northwestern.edu**Brenda Dietrich**, IBM Watson Labs, dietric@watson.ibm.com

Title: Competitive Analysis of On-line Booking: Dynamic Policies

In earlier work, we derived revenue management policies that view the problem from the perspective of online algorithms. This approach eliminates the need for demand forecasts and a risk neutrality assumption. Extensions to this approach can produce dynamic policies that adjust their behavior in response to orders previously accepted, thereby producing increased performance guarantees. We derive such policies and test them on revenue management scenarios with volatile demand distributions. This approach is particularly effective when there is no a priori ordering on the arrival of customer types, e.g. high value customers can arrive before low value customers. Applications we target include assemble-to-order products with limitations on certain key components.

Title: Dynamic Pricing For Non-Perishable Products With Demand Learning

A retailer is endowed with a finite inventory of a non-perishable product. Demand for this product is driven by a Poisson process with unknown price-sensitive intensity. The retailer controls dynamically the price in order to maximize the long-term average profits taking into account the opportunity of his operations. This opportunity cost is given by the long-term average discounted profits that the retailer can make if he switches and starts selling a different assortment of products. The retailer's optimal pricing policy trades off immediate revenues and future profits based on active demand learning.

Title: When is Price Discrimination Profitable? and When are Advance Purchase Discounts Profitable?

The canonical model of a firm selling to heterogeneous, but indistinguishable, consumers implies that the firm should offer multiple products and distort its product quality relative to the efficient level, yet in practice many firms adopt a single product strategy. This tension can be resolved by recognizing that in many instances the firm's choice of product quality is constrained. We analyze a model of a quality-constrained monopolist's product line decision that encompasses a variety of important examples of second-degree price discrimination, including intertemporal price discrimination, coupons, advance purchase discounts, versioning of information goods, and damaged goods. We derive necessary and sufficient conditions for price discrimination to be profitable that generalize existing results in the literature. Specifically, we show that when a continuum of product qualities are feasible, price discrimination is profitable if and only if the ratio of the marginal social value from an increase in quality to the total social value of the good is increasing in consumers' willingness to pay. We also find that allowing price discrimination can result in a Pareto improvement, though in general the welfare effects are ambiguous.

Title: How To Influence Noncooperative, Selfish Agents

The societal value of a distribution of finite resources is frequently measured in terms of aggregate utility. Decisions, however, are frequently controlled by noncooperative agents who try to maximize their own private utility. The term "price of anarchy" refers to the ratio of social utility achieved by selfish agents versus the social optimal.

In network routing games, the price of anarchy can be arbitrarily bad. We describe when and how link charges can be used to avoid this bad outcome. Our results carry over to more general congestion games.

Title: Inter-temporal Valuations, Product Design and Revenue Management

We study inter-temporal choice models where customer valuations evolve over time. This requires discounts to induce people to book early and therefore leads to a low-to-high pricing scheme, at least in expectation. We show that for a wide range of capacity levels, selling partially refundable fares (or equivalently, selling call options on capacity) can result in significantly higher expected revenues than those obtained using traditional low-to-high revenue management techniques (e.g., booking and overbooking limits). The use of options allows customers to self-select products (including options) without the need of imposing fences like Saturday night stays. As a byproduct, we have observed that increasing the uncertainty of customer valuations benefits providers using options, but may hurt providers using traditional revenue management.

Title: Designing and Pricing Grades of Service for Subscribers with Private Information

A profit-maximizing service provider may offer several grades of service at different prices. There are several classes of potential subscribers, differing in their price sensitivity and valuation of service quality. The provider does not know the class of a potential subscriber. We characterize the provider's optimal, incentive compatible menu of products and associated prices.

Title: Near-Optimal Online Auctions

We consider the online auction problem proposed by Bar-Yossef, Hildrum, and Wu [4] in which an auction- eer is selling identical items to bidders arriving one at a time. We give an auction that achieves a constant fac- tor of the optimal profit less an O(h) additive loss term, where h is the value of the highest bid. Furthermore, this auction does not require foreknowledge of the range of bidders' valuations. On both counts, this answers open questions from [4, 5]. We further improve on the results from [5] for the online posted-price problem by re- ducing their additive loss term from O(h log h log log h) to O(h log log h). Finally, we define the notion of an (offline) attribute auction for modeling the problem of auctioning items to consumers who are not a-priori in- distinguishable. We apply our online auction solution to achieve good bounds for the attribute auction problem with 1-dimensional attributes.

Title: Adaptive Limited-Supply Online Auctions

We study a limited-supply online auction problem, in which an auc- tioneer has k goods to sell and bidders arrive and depart dynami- cally. We suppose that agent valuations are drawn independently from some unknown distribution and construct an adaptive auction that is nevertheless value- and time-strategyproof. For the k = 1 problem we have a strategyproof variant on the classic secretary problem. We present a 4-competitive (e-competitive) strategyproof online algorithm with respect to offline Vickrey for revenue (effi- ciency). We also show (in a model that slightly generalizes the as- sumption of independent valuations) that no mechanism can be bet- ter than 3/2-competitive (2-competitive) for revenue (efficiency). Our general approach considers a learning phase followed by an accepting phase, and is careful to handle incentive issues for agents that span the two phases. We extend to the k > 1 case, by deriving strategyproof mechanisms which are constant-competitive for rev- enue and efficiency. Finally, we present some strategyproof com- petitive algorithms for the case in which adversary uses a distribu- tion known to the mechanism.

Title: Dynamic pricing and leadtime quotation for a multi-class make-to-order queue

Consider a make-to-order manufacturer that offers multiple products to a market of price and delay sensitive users. This paper studies the problem of maximizing its long-run average expected profits for a model that captures three aspects of particular interest: first, the joint use of dynamic pricing and leadtime quotation controls to manage customer demand; second, the presence of a dual sourcing mode that can be used to expedite orders at a cost; and third, the interaction of the aforementioned demand controls with the operational decisions of sequencing and expediting that the firm must employ to optimize revenues and satisfy the quoted leadtimes. Using an approximating diffusion control problem we derive near-optimal dynamic pricing, leadtime quotation, sequencing, and expediting policies that provide structural insights and lead to practically implementable recommendations. A set of numerical results illustrates the value of joint pricing and leadtime control, as well as the performance of the proposed set of policies.

Title: Optimization of Distribution Channels: a data-based approach

Nowadays, companies serve their customers through different channels. For an apparel retailer, the available channels include company-owned retail stores, third-party stores, mail orders, and internet orders. For an airline, the available channels include travel agencies, internet orders executed on the company's web site, internet orders executed on partners' web sites, and phone orders. Any company, independently of the industry in which it operating, faces complex decisions when faced with multi-channel distribution. These include differential pricing, allocation of resources (e.g., salespeople) to each channel based on its effectiveness, and, whenever applicable, capacity reservations among channels. In this talk, we focus on the example of channel optimization at IBM. The problem in this case is that of identifying the customers that are suitable for a different channel, based on historical transactional data, and of rebalancing the customer portfolio across channels.

Title: Multi-Period Pricing of Perishable Products; Competition, Uncertainty and Learning

In this paper we discuss a model for dynamically pricing multiple perishable products that sellers need to sell over a finite time horizon (i.e. in this setting, each seller has a fixed inventory of several products that he/she needs to sell over a finite time horizon). We are considering an oligopolistic market and assume that sellers compete through pricing. Applications in mind include pricing airline tickets in the face of competitor airlines, as well as selling seasonal products in the retail industry in the presence of competitors. The model we present addresses the competitive aspect of the problem but also the presence of demand uncertainty. In particular, we propose a model that uses ideas from quasi-variational inequalities (in order to address the aspect of competition) and ideas from robust optimization (in order to address uncertainty of demand). The latter allows us to propose a model that is tractable and does not assume any particular type of distribution for the uncertain parameters of demand. Furthermore, we enhance the model to include a setting where sellers learn their demand and try to understand their competitors' demands as they collect more data on prices for them and their competitors as time progresses and the selling horizon unfolds. We use ideas from MPECs to model this enhanced model of joint pricing and demand learning. Finally, we illustrate our results through some numerical examples and discuss some insights.

Title: Revenue Optimization in a Repeated-Game Model

Firms who set prices in competitive environments must account for the price-setting strategies of their competitors. When there are few firms one might seek a Nash equilibrium in the one-shot game played between the firms. The one-shot model often fails to capture the effects of punishment and reward that become important in a repeated game. We present a simple duopoly model with uncertain demand that endeavours to represent these effects. We show that by adopting mixed strategies in this model, firms can capture monopoly profits in expectation without colluding.

Title: An Asymptoticall Optimal Policy for a Quantity-Based Network Revenue Mgmt. Problem

We consider the following canonical revenue management problem, which has been analyzed in the context of airline seat inventory control and has applications to other service industries and supply chain management. There are M resource types (legs) and J customer classes (routes). There is a total of Cm of resource m (seats on leg m), m=1, ?,M. Customers of class j arrive as a renewal process, require Amj units of resource m, and pay pj if accepted. The aim is to make dynamic accept/reject decisions to maximize the total expected revenue obtained over the finite horizon [0,T] subject to the resource constraints C1,?,CM.

We introduce a control policy motivated by fluid and diffusion limits (as the Cm's and arrival rates grow large). Our control policy makes an initial resource allocation decision based on solving a linear program (LP). The solution of the LP yields the fraction of arrivals of each class to accept. We then form a 'trigger function' based on the difference between the actual and expected number of accepted customers of each class. When this trigger function exceeds a pre-set threshold a reoptimization is performed: An LP involving the remaining resource capacities and remaining time is solved. The solution of this LP is then used to control admissions over the remainder of the horizon.

We show that this policy is asymptotically optimal on diffusion scale, a property that is not shared by other approaches such as booking limits and bid price control. (These other approaches yield policies that are asymptotically

Title: Pricing Strategies and Service Differentiation in an M/M/1 queue - A Profit Maximization Perspective

In this paper, we consider the problem pf pricing and scheduling the customers arriving at a service facility, with the objective of maximizing the profits of the facility. We model the service facility as an M/M/1 queue with heterogeneous, time-sensitive customers and with service preemptions allowed. Each customer has a value for service and a related cost of waiting per unit time; all the customers have the same mean service time. We assume that when the customers arrive at the system, they cannot observe the state of the queue. However, they know all the average system statistics and make their decision solely based on these statistics. The service provider does not know the type of a particular customer unless the customer himself reveals this information. Thus any pricing- scheduling policy employed has to be incentive compatible, inducing the customer to reveal their types.

Title: Strategic Capacity Rationing to Induce Early Purchases

Dynamic pricing offers the potential to increase revenues. At the same time, it creates an incentive for consumers to strategize over the timing of their purchases. That is, customers may anticipate the entire price path and try to optimally time their purchases. In such cases, a firm should ideally use its pricing and stocking decisions to try to profitably influence this strategic behavior. One approach is to create a rationing risk by under-stocking products. The resulting threat of shortages creates an incentive for customers to purchase early at higher prices. But when does such a rationing strategy make sense? If it is indeed profitable to create such shortages, what is the optimal amount of rationing risk to create? And how is this decision affected by the risk preferences of customers, the magnitude of discounting and the level of competition a firm faces?

We develop a stylized model to study this problem. In our model, customers have heterogeneous valuations for the firm's product and face declining prices over two periods. Customers are assumed to have identical risk preferences (utility functions) and know the price path and fill rate in period 2. Via its capacity choice, the firm is able to control the fill rate and hence the rationing risk faced by customers. Customers behave strategically and weigh their payoff of immediate purchase against the expected payoff of later purchase. We analyze the capacity choice that maximizes the firm's profits. First, we consider a monopoly market and characterize conditions under which rationing is optimal. We show that rationing is never an optimal strategy for risk neutral customers; rationing is optimal only when customers are strictly risk averse. We also characterize how the optimal amount of rationing (fill rate) is affected by the discounted price and the degree of risk aversion among customers. Numerically, we find that the firm's profit is much more sensitive to errors in the stocking quantity than to errors in price, suggesting that inventory policies in the strategic customer setting can be more important than pricing in determining total profits. We then analyze an oligopoloy version of the model and show that competition reduces the firms' ability to segment customers via rationing. Indeed, there exists a critical number of firms beyond which a rationing equilibrium can never be supported. Lastly, we discuss the case of aggregate demand uncertainty and the case where customers sequentially form expectations about fill rates based on repeat purchase experience.

Previous: Program

Workshop Index

DIMACS Homepage

Contacting the Center

Document last modified on July 28, 2005.