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

来源 :Journal of Computer Science & Technology | 被引量 : 0次 | 上传用户:lvshuijing
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
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 m 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 α-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(α log n)-approximation for the general case.2) O(αk)-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 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 the one independence system defined over the items. 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 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 α-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 (α log n) -approximation for the general case.2) O (αk) -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.
其他文献
日前,由浙江省旅游局和中国移动浙江公司共同举办的“商旅通,通天下——浙江省旅游行业信息化研讨会”在杭州召开。浙江省旅游局、中国移动浙江公司领导以及浙江省100多家高垦
在新农村建设中,传统的守留服务模式已不能适应和无法满足广大读者的需求,图书流通站进入社区、学校的服务模式正悄然在图书馆界盛行,然而,远离城市的山区小朋友他们更期待我
2012中日韩(环渤海)中小企业绿色产业峰会5月在天津梅江会展中心会议厅举行。天津市委常委、市委统战部部长刘长喜出席并讲话。刘长喜对峰会在津举行表示祝贺,对与会嘉宾来津
急性心肌梗死(acute myocardial infarction,AMI)有发病率高、病情变化快、病死率高等特点[1-4]。早期再灌注治疗是治疗AMI最有效的方法,而且再灌注时间越早,疗效越好[1-5]。
一、充分预设,提供动态生成的舞台动态的课堂,基于充分预设。这个预设不是单维的、严密的、封闭的、主观的线性教学设计,而应该是多维的、灵活的、开放的、动态的板块式设计,
目的探讨急性心肌梗死(AMI)患者心率变异性(HRV)及其与梗死相关血管(IRA)的相关关系。方法对68例AMI患者和80例正常人行24 h动态心电图(Holter)检查,测量并计算HRV时域指标与
佛山市的公共图书馆事业在全国同级城市中处于领先水平,6家市、区公共图书馆全部达到了国家一级图书馆的标准。但事业发展中仍然存在许多不足,主要表现在:图书馆服务覆盖面较
纵观小学科学课堂教学,教学任务完不成、拖堂现象比比皆是。那么我们究竟应该如何让平时的科学课堂上得简约而有效呢?一、简约内容,有效取舍科学课的许多课文虽是经典的教学
七彩世界 欢乐世界项目地址:成都双流白衣上街灯具及控制系统提供:乐雷光电技术(上海)有限公司设计原则艺术性原则照明设计的艺术性可以为整个灯光景观设计增添意趣。开放创
这些新闻剪报和照片只是从皇家艺术学院收藏的三大本1935年“中国艺术展”新闻资料中撷取的一小部分,但从中可以窥见该展获得的轰动效应。从一开展,美仑美焕的中国陶瓷、青铜