Computer Science – Computer Science and Game Theory
Scientific paper
2012-02-13
Computer Science
Computer Science and Game Theory
This extended abstract focuses on explaining the main technical idea by showing a sub-linear approximation algorithm for the p
Scientific paper
In the unlimited-supply profit-maximizing pricing problem, we are given the consumers' consideration sets and know their purchase strategy. 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). 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.
Chalermsook Parinya
Elbassioni Khaled
Nanongkai Danupon
Sun He
No associations
LandOfFree
Multi-Attribute Profit-Maximizing Pricing (Extended Abstract) does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Multi-Attribute Profit-Maximizing Pricing (Extended Abstract), we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multi-Attribute Profit-Maximizing Pricing (Extended Abstract) will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-87678