Optimal Envy-free Pricing with Metric Substitutability
Source:
ACM Conference on Electronic Commerce (EC'08) (2008)
Abstract:
We study the profit-maximizing envy-free pricing problem with metric substitutability among the items --- the value of consumer
i for item j is v_i - c_{i,j} and the substitution costs,
c_{i,j}, form a metric. Our model is motivated from the
observation that sellers often sell the same product at different
prices in different locations, and rational consumers optimize the
tradeoff between the prices and the substitution costs. While the
general envy-free pricing problem is hard to approximate, the
addition of metric substitutability constraints allows us to solve
the problem exactly in polynomial time by reducing it to an instance
of weighted independent set on a perfect graph.
When the substitution costs do not form a metric, even in cases when
a (1+epsilon)-approximate triangle inequality holds, the
problem becomes NP-hard. Our results show that triangle inequality
is the exact sharp threshold for the problem of going from
``tractable" to ``hard".
We then turn our attention to the multi-unit demand case, where
consumers request multiple copies of the item. This problem has an
interesting paradoxical non-monotonicity: The optimal revenue the
seller can extract can actually decrease when consumers' demands
increase. We show that in this case the revenue maximization problem
becomes APX-hard and give an O(log D) approximation algorithm,
where D is the ratio of the largest to smallest demand. We extend
these techniques to the more general case of arbitrary
non-decreasing value functions, and give an O(log^3 D)
approximation algorithm.
Download:
