We use cookies to improve your experience with our site.

普适供应限制下的对于单元消费者的非羡慕定价策略

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

  • 摘要: 非羡慕定价策略寻求一个定价策略和分配方案,使得每个消费者都分配到自己利益最大化的货物。此类问题的目标是最大化卖家的利润。在本文中,我们研究了以一个独立集形式给出的普适供应限制下的情况。这种限制可以是一些线性函数或者是拟阵的形式。它们可以很好得刻画货物是在消费者的估值和资源限制下生产出来的情况,而不是事先存在的。
    在本文中,我们着重研究了单元消费者的情况。我们假设有n个消费者和m种货物;每种货物都可以生产多份。对于每个消费者i,存在一个它感兴趣的货物集合 Si。对其中每个货物j, 消费者i有个估值 vij。分配给i的货物,如果有的话,必须是它非负利润最高的。假设我们有个近似黑盒可以在给定的独立集中找到一个α近似最优的加权独立集。我们得到如下的结果:
    普适情况下: O(αlog n) 近似。
    每个消费者最多对k个货物感兴趣:O(αk) 近似。
    每个货物最多有f个消费者感兴趣: O(αk) 近似。

     

    Abstract: 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 emn 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.

     

/

返回文章
返回