Approximation Algorithms for Profi t-maximizing Pricing Problems
Khaled Elbassioni
Approximation Algorithms for Profi t-maximizing Pricing Problems
One of the most basic methods for dealing with NP-hard optimization problems is to design polynomial-time algorithms that find a solution which is provably not far from the optimum. Formally, an algorithm is said to be an x-approximation algorithm for a maximization (or minimization) problem if it runs in polynomial time in the size of the input instance and produces a solution whose objective value is within a factor of x of the optimum solution. Under this general framework, we have been working on problems from different areas, including graph problems, computational economics, computational geometry and mathematical programming. We will give an example below.
Item pricing
Profit (or revenue) maximization is a classic and fundamental economic goal. The design of computationally-efficient item-pricing schemes for various profit-maximization problems has received much attention recently, due in large part to the emergence of e-commerce applications on the Internet. With the availability of vastly emerging online markets, it is possible now for retailers to display their goods, such as books, flight tickets and hotel rooms, for purchase to interested consumers sitting at home. The added flexibility in such a market allows consumers to submit their budgets for every subset of items they are interested in to the retailer who considers this input from all the customers, and aims at coming up with an item-pricing strategy that maximizes the revenue. A typical example would be how to set the nightly rate for rooms in a hotel so as to maximize the revenue achievable from customers who submit their budget for the entire duration of intended stay. There is an obvious tradeoff on how to price the items: pricing cheaply implies a large volume of sales as many people will be able to afford their preferred subsets of items, but the revenue from each item sold is small; pricing high increases the revenue from each sold item, but reduces the volume. The optimization problem that arises from such tradeoff is quite complex and inherently non-linear. In the case when the supply of each item is limited, an added complication is sometimes mandated by the requirement to have a fair allocation of items to customers, in the sense that it might be necessary to raise the prices of certain items to ensure that there is enough supply, so that customers who can afford to purchase their preferred subsets at the announced prices are granted these subsets.
The complexity of these kinds of problems translates into hardness of approximation; that is, under plausible complexity assumptions, there exist in general no polynomial-time algorithms with good approximation ratios for the optimal profit-maximizing pricing. In joint work with Parinya Chalermsook, Danupon Nanongkai, and He Sun, we made an attempt at overcoming this inherent difficulty, in one basic variant of the problem, by focusing on the more realistic situation in which the consideration sets that the customers are interested in satisfy a certain geometric restriction. In particular, instead of looking at a full generality where each consumer C considers any set of items Sc , it is reasonable to assume that each consumer has some criterion in mind for each attribute of the item, and her consideration set consists of any item that passes all her criteria. This natural assumption has been a model of study in other fields such as marketing research, healthcare economics and urban planning. It is referred to as the attribute-based screening process. Assuming there are d-relevant attributes, consumers and items are represented by points in the d-dimensional Euclidean space, and the consideration set Sc of consumer C is the set of itempoints that dominate the point corresponding to C in every attribute; see the figure below. Examples of attributes for a customer buying, say, a car, are horsepower, engine size, number of doors, etc. Each consumer C declares her budget Bc , and once the prices are declared, among all the items in the consideration set Sc , the cheapest one with price at most Bc is purchased.
Consideration set
We showed that the low dimensionality of the consideration sets arising in this pricing problem does lead to improved approximation ratios, by presenting sublinear-approximation algorithms for the above variant of the problem. Our algorithm is obtained by combining algorithmic pricing and geometric techniques. These results suggest that considering geometric aspects might be a promising research direction in obtaining improved approximation algorithms for such pricing problems.
Khaled Elbassioni
DEPT. 1 Algorithms and ComplexityPhone +49 681 9325-1007Email elbassio@mpi-inf.mpg.deInternet www.mpi-inf.mpg.de/departments/d1/areas/optimization.html