Paper Info
Title
On profit-maximizing envy-free pricing
Abstract
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.
Year
DOI
Venue
2005
10.5555/1070432.1070598
SODA
Keywords
Field
DocType
pricing item,log-competitive truthful mechanism,seller profit,envy-free price,corresponding mechanism design problem,envy-free pricing,single-minded consumer,corresponding allocation,important class,interesting special case,unit demand consumer,mechanism design,profitability
Revenue,Approximation algorithm,Mathematical optimization,Computer science,Mechanism design,If and only if,Logarithm,Envy-free,Bundle
Conference
ISBN
Citations 
PageRank 
0-89871-585-7
149
10.00
References 
Authors
11
6
Search Limit
100149
Name
Order
Citations
PageRank
V. Guruswami13205247.96
Jason D. Hartline21447125.76
Anna R. Karlin34429646.72
David Kempe45891403.41
Claire Kenyon514910.00
Frank McSherry64289288.94