## Multi-Attribute Profit-Maximizing Pricing

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

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.

## Interactive Regret Minimization

Author: Danupon Nanongkai, Atish Das Sarma, Ashwin Lall, Kazuhisa Makino
(Author names are NOT in alphabetical order. )

We study the notion of regret ratio proposed by Nanongkai et al. [VLDB’10] to deal with multi-criteria decision making in database systems. The regret minimization query proposed Nanongkai et al. was shown to have features of both skyline and top-$k$: it does not need information from the user but still controls the output size. While this approach is suitable for obtaining a reasonably small regret ratio, it is still open whether one can make the regret ratio arbitrarily small. Moreover, it remains open whether reasonable questions can be asked to the users in order to improve efficiency of the process.