Social Welfare and Profit Maximization from Revealed Preferences

Consider the seller's problem of finding optimal prices for her (divisible) goods when faced with a set of consumers, given that she can only observe their purchased bundles at the set prices, i.e., access to only revealed preferences (demand oracle). We study both social welfare and profit maximization under this setting, assuming the concave valuation function of consumers and the convex production cost function of the seller, which are standard assumptions in economics.

A recent series of works (Roth et al., 2016, 2017) studied this problem for various special cases of valuation and cost functions while making no assumption on the demand oracle. The main difficulty they observe is that the resulting optimization problem is non-convex in prices. For social-welfare maximization, we obtain a natural interpretation of the revealed preference feedback in the dual optimization problem, and thereby obtain a simple gradient-based algorithm. This simplifies and improves on the series of works of Roth et al. (2016, 2017) at least by a quadratic factor in terms of query complexity.

Second, we study social-welfare maximization in the online setting, where consumers arrive one-by-one in a random order, a.k.a. the secretary model. For the case where consumer valuation can be an arbitrary continuous function, we design a price posting mechanism that achieves average expected social welfare up to an additive factor of 1/sqrt(m) of maximum social welfare, where m is the number of consumers. Third, for profit maximization, we obtain the first FPTAS when valuation and cost functions are separable, with a matching lower bound. For the non-separable case, we show that no PTAS exists, even when only the cost function is non-separable.