TY - GEN
T1 - Social welfare and profit maximization from revealed preferences
AU - Ji, Ziwei
AU - Mehta, Ruta
AU - Telgarsky, Matus
N1 - Publisher Copyright:
© Springer Nature Switzerland AG 2018.
PY - 2018
Y1 - 2018
N2 - Consider the seller’s problem of finding optimal prices for her n (divisible) goods when faced with a set of m consumers, given that she can only observe their purchased bundles at posted prices, i.e., revealed preferences. We study both social welfare and profit maximization with revealed preferences. Although social welfare maximization is a seemingly non-convex optimization problem in prices, we show that (i) it can be reduced to a dual convex optimization problem in prices, and (ii) the revealed preferences can be interpreted as supergradients of the concave conjugate of valuation, with which subgradients of the dual function can be computed. We thereby obtain a simple subgradient-based algorithm for strongly concave valuations and convex cost, with query complexity (formula presented), where ϵ is the additive difference between the social welfare induced by our algorithm and the optimum social welfare. We also study social welfare maximization under the online setting, specifically the random permutation model, where consumers arrive one-by-one in a random order. For the case where consumer valuations can be arbitrary continuous functions, we propose a price posting mechanism that achieves an expected social welfare up to an additive factor of (formula Presented) from the maximum social welfare. Finally, for profit maximization (which may be non-convex in simple cases), we give nearly matching upper and lower bounds on the query complexity for separable valuations and cost (i.e., each good can be treated independently).
AB - Consider the seller’s problem of finding optimal prices for her n (divisible) goods when faced with a set of m consumers, given that she can only observe their purchased bundles at posted prices, i.e., revealed preferences. We study both social welfare and profit maximization with revealed preferences. Although social welfare maximization is a seemingly non-convex optimization problem in prices, we show that (i) it can be reduced to a dual convex optimization problem in prices, and (ii) the revealed preferences can be interpreted as supergradients of the concave conjugate of valuation, with which subgradients of the dual function can be computed. We thereby obtain a simple subgradient-based algorithm for strongly concave valuations and convex cost, with query complexity (formula presented), where ϵ is the additive difference between the social welfare induced by our algorithm and the optimum social welfare. We also study social welfare maximization under the online setting, specifically the random permutation model, where consumers arrive one-by-one in a random order. For the case where consumer valuations can be arbitrary continuous functions, we propose a price posting mechanism that achieves an expected social welfare up to an additive factor of (formula Presented) from the maximum social welfare. Finally, for profit maximization (which may be non-convex in simple cases), we give nearly matching upper and lower bounds on the query complexity for separable valuations and cost (i.e., each good can be treated independently).
UR - http://www.scopus.com/inward/record.url?scp=85059002334&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85059002334&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-04612-5_18
DO - 10.1007/978-3-030-04612-5_18
M3 - Conference contribution
AN - SCOPUS:85059002334
SN - 9783030046118
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 264
EP - 281
BT - Web and Internet Economics - 14th International Conference, WINE 2018, Proceedings
A2 - Harks, Tobias
A2 - Christodoulou, George
PB - Springer Verlag
T2 - 14th International Conference on Web and Internet Economics, WINE 2018
Y2 - 15 December 2018 through 17 December 2018
ER -