Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR06-150 | 4th December 2006 00:00

Towards Hardness of Envy-Free Pricing


Authors: Patrick Briest
Publication: 11th December 2006 10:11
Downloads: 1271


We consider the envy-free pricing problem, in which we want to compute revenue maximizing prices for a set of products P assuming that each consumer from a set of consumer samples C will buy the product maximizing her personal utility, i.e., the difference between her respective budget and the product's price. We show that assuming specific hardness of the balanced bipartite independent set problem in constant degree graphs or hardness of refuting random 3CNF formulas, the envy-free pricing problem cannot be approximated in polynomial time within O(log^eps |C|) for some eps > 0. This is the first result giving evidence that envy-free pricing might be hard to approximate within essentially better ratios than the logarithmic ratio obtained so far. Additionally, it gives another example of how average case complexity is connected to the worst case approximation complexity of notorious optimization problems.

ISSN 1433-8092 | Imprint