Envy, Multi Envy, and Revenue Maximization
Envy, Multi Envy, and Revenue Maximization
复制标题
DOI：
10.1007/978-3-642-10841-9_48
复制
发表时间：
2009-09
期刊：
影响因子：
--
通讯作者：
A. Fiat;Amiram Wingarten
中科院分区：
文献类型：
--
作者：
A. Fiat;Amiram Wingarten
我们研究了卖家所面临的嫉妒自由定价问题，卖家希望通过设定捆绑商品的价格来最大化收入。如果存在无限的物品供应，并且代理人是单一的，则我们证明了通过将其归结为完美图上的加权独立集的实例，可以在多项式时间内求解收益最大化嫉妒自由分配/定价。如果没有代理人希望用其他代理的分配的和来代替她的分配，并且她的价格用它们的价格之和来代替她的分配，我们将其定义为多嫉妒自由。我们证明了很难确定一个给定的分配/定价是否是无多嫉妒的。我们还证明了收益最大化多嫉妒自由分配/定价是APX困难的。此外，对于高速公路问题的各种变体，我们给出了有效的算法和困难结果。
We study the envy free pricing problem faced by a seller who wishes to maximize revenue by setting prices for bundles of items. If there is an unlimited supply of items and agents are single minded then we show that finding the revenue maximizing envy free allocation/pricing can be solved in polynomial time by reducing it to an instance of weighted independent set on a perfect graph.We define an allocation/pricing asmulti envy freeif no agent wishes to replace her allocation with the union of the allocations of some set of other agents and her price with the sum of their prices. We show that it iscoNP-hard to decide if a given allocation/pricing is multi envy free. We also show that revenue maximization multi envy free allocation/pricing isAPXhard.Furthermore, we give efficient algorithms and hardness results for various variants of the highway problem.