2010 | OriginalPaper | Chapter
Envy-Free Pricing with General Supply Constraints
Authors : Sungjin Im, Pinyan Lu, Yajun Wang
Published in: Internet and Network Economics
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
The envy-free pricing problem can be stated as finding a pricing and allocation scheme in which each consumer is allocated a set of items that maximize her utility under the pricing. The goal is to maximize seller revenue. We study the problem with
general supply
constraints which are given as an independence system defined over the items. The constraints, for example, can be a number of linear constraints or matroids. This captures the situation where items do not pre-exist, but are produced in reflection of consumer valuation of the items under the limit of resources.
This paper focuses on the case of unit-demand consumers. In the setting, there are
n
consumers and
m
items; each item may be produced in multiple copies. Each consumer
i
∈ [
n
] has a valuation
v
ij
on item
j
in the set
S
i
in which she is interested. She must be allocated (if any) an item which gives the maximum (non-negative) utility. Suppose we are given an
α
-approximation
oracle
for finding the maximum weight independent set for the given independence system (or a slightly stronger oracle); for a large number of natural and interesting supply constraints, constant approximations are available. We obtain the following results.
O
(
α
log
n
)-approximation for the general case.
O
(
αk
)-approximation when each consumer is interested in at most
k
distinct types of items.
O
(
αf
)-approximation when each item is interesting to at most
f
consumers.
Note that the final two results were previously unknown even without the independence system constraint.