Abstract:
We study the profit-maximizing envy-free pricing problem with metric substitutability among the items --- the value of consumeri for item j is v_i - c_{i,j} and the substitution costs,c_{i,j}, form a metric. Our model is motivated from theobservation that sellers often sell the same product at differentprices in different locations, and rational consumers optimize thetradeoff between the prices and the substitution costs. While thegeneral envy-free pricing problem is hard to approximate, theaddition of metric substitutability constraints allows us to solvethe problem exactly in polynomial time by reducing it to an instanceof weighted independent set on a perfect graph.When the substitution costs do not form a metric, even in cases whena (1+epsilon)-approximate triangle inequality holds, theproblem becomes NP-hard. Our results show that triangle inequalityis the exact sharp threshold for the problem of going from``tractable" to ``hard".We then turn our attention to the multi-unit demand case, whereconsumers request multiple copies of the item. This problem has aninteresting paradoxical non-monotonicity: The optimal revenue theseller can extract can actually decrease when consumers' demandsincrease. We show that in this case the revenue maximization problembecomes APX-hard and give an O(log D) approximation algorithm,where D is the ratio of the largest to smallest demand. We extendthese techniques to the more general case of arbitrarynon-decreasing value functions, and give an O(log^3 D)approximation algorithm.
Download:
Ec194 ghosh.pdf
ACM COPYRIGHT NOTICE. Copyright © 2012 by the Association for Computing Machinery, Inc. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Publications Dept., ACM, Inc., fax +1 (212) 869-0481, or permissions@acm.org.
mobile