Envy-Free Pricing with General Supply Constraints for Unit Demand Consumers  

作　　者：Sungjin Im 陆品燕 王亚军 

机构地区：[1]Department of Computer Science,University of Illinois [2]Microsoft Research Asia [3]ACM

出　　处：《Journal of Computer Science & Technology》2012年第4期702-709,共8页计算机科学技术学报（英文版）

基　　金：Sungjin Im is partially supported by the National Science Foundation of USA under Grant Nos. CCF-0728782, CNS-0721899

摘　　要：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 his/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 rn items; each item may be produced in multiple copies. Each consumer i ∈[n] has a valuation vij on item j in the set Si in which he/she is interested. He/she must be allocated （if any） an item which gives the maximum （non-negative） utility. Suppose we are given an a-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 approximation algorithms are available. We obtain the following results. 1） O（αlogn）-approximation for the general case. 2） O（ακ）-approximation when each consumer is interested in at most k distinct types of items. 3） O（αf）-approximation when each type of item is interesting to at most f consumers. Note that the final two results were previously unknown even without the independence system constraint.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 his/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 rn items; each item may be produced in multiple copies. Each consumer i ∈[n] has a valuation vij on item j in the set Si in which he/she is interested. He/she must be allocated （if any） an item which gives the maximum （non-negative） utility. Suppose we are given an a-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 approximation algorithms are available. We obtain the following results. 1） O（αlogn）-approximation for the general case. 2） O（ακ）-approximation when each consumer is interested in at most k distinct types of items. 3） O（αf）-approximation when each type of item is interesting to at most f consumers. Note that the final two results were previously unknown even without the independence system constraint.

关 键 词：envy-free pricing APPROXIMATION MATROID 

分 类 号：F274[经济管理—企业管理] F224[经济管理—国民经济]