ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR06-150 | 4th December 2006 00:00

Towards Hardness of Envy-Free Pricing

RSS-Feed




TR06-150
Authors: Patrick Briest
Publication: 11th December 2006 10:11
Downloads: 734
Keywords: 


Abstract:

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