Multi-Attribute Profit-Maximizing Pricing

Author: Parinya Chalermsook, Khaled Elbassioni, Danupon Nanongkai, He Sun

Download: arXiv (Extended Abstract)pdf (full version)

Conference: Submitted



In the unlimited-supply profit-maximizing pricing problem, we are given the consumers’ consideration sets and know their purchase strategy (e.g. buy the cheapest items). The goal is to price the items to maximize the revenue. Previous studies suggest that this problem is too general to obtain even a sublinear approximation ratio (in terms of the number of items) even when the consumers are restricted to have very simple purchase strategies.
In this paper we initiate the study of the multi-attribute pricing problem as a direction to break this barrier. Specifically, we consider the case where each item has a constant number of attributes, and each consumer would like to buy the items that satisfy her criteria in all attributes. This notion intuitively captures typical real-world settings and has been widely-studied in marketing research, healthcare economics, etc. It also helps categorizing previously studied cases, such as highway pricing problem and graph vertex pricing problem on planar and bipartite graphs, from the general case.

We show that this notion of attributes leads to improved approximation ratios on a large class of problems. This is obtained by utilizing the fact that the consideration sets have low VC-dimension and applying Dilworth’s theorem on a certain partial order defined on the set of items. As a consequence, we present sublinear-approximation algorithms, thus breaking the previous barrier, for two well-known variants of the problem: unit-demand uniform-budget min-buying and single-minded pricing problems. Moreover, we generalize these techniques to the unit-demand utility-maximizing pricing problem and (non-uniform) unit-demand min-buying pricing problem when valuations or budgets depend on attributes, as well as the pricing problem with symmetric valuations and subadditive revenues. These results suggest that considering attributes is a promising research direction in obtaining improved approximation algorithms for such pricing problems.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: