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

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

**Conference: **Submitted

**Journal: **–

**Abstract:**

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.