On profit-maximizing envy-free pricing

Venkatesan Guruswami*, Jason D. Hartline, Anna R. Karlin, David Kempe, Claire Kenyon, Frank McSherry

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

253 Scopus citations


We study the problem of pricing items for sale to consumers so as to maximize the seller's revenue. We assume that for each consumer, we know the maximum amount he would be willing to pay for each bundle of items, and want to find pricings of the items with corresponding allocations that maximize seller profit and at the same time are envy-free, which is a natural fairness criterion requiring that consumers are maximally happy with the outcome they receive given the pricing. We study this problem for two important classes of inputs: unit demand consumers, who want to buy at most one item from among a selection they are interested in, and single-minded consumers, who want to buy one particular subset, but only if they can afford it. We show that computing envy-free prices to maximize the seller's revenue is APX-hard in both of these cases, and give a logarithmic approximation algorithm for them. For several interesting special cases, we derive polynomial-time algorithms. Furthermore, we investigate some connections with the corresponding mechanism design problem, in which the consumer's preferences are private values: for this case, we give a log-competitive truthful mechanism.

Original languageEnglish (US)
Title of host publicationProceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms
Number of pages10
StatePublished - Jul 1 2005
EventSixteenth Annual ACM-SIAM Symposium on Discrete Algorithms - Vancouver, BC, United States
Duration: Jan 23 2005Jan 25 2005


OtherSixteenth Annual ACM-SIAM Symposium on Discrete Algorithms
Country/TerritoryUnited States
CityVancouver, BC

ASJC Scopus subject areas

  • Software
  • General Mathematics


Dive into the research topics of 'On profit-maximizing envy-free pricing'. Together they form a unique fingerprint.

Cite this