Internet and Network Economics
Internet and Network Economics
复制标题
互联网和网络经济学
DOI：
10.1007/978-3-642-10841-9_6
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Briest P
中科院分区：
文献类型：
--
作者：
Briest P
在Stackelberg定价中，领导者为物品设定价格，以使追随者购买可行的物品子集所获得的收益最大化。我们考虑计算上有限的追随者，他们不能在所有可行子集的范围内精确地优化，但他们应用公开已知的算法来确定要购买的物品。这与一般的多维定价相对应，当客户无法有效地优化其估值功能，但仍以理性行为为目标，尽其所能。我们考虑这种新型定价问题的两个版本。在MIn - KNAPSACK变体中，物品是加权的对象，跟随者寻求购买一些有界权重的最小成本选择对象。当他使用贪婪的2 -近似算法时，我们提供了一个多项式-时间(2+ε) -近似算法来解决基于所谓的近均匀价格分配的领导者收益最大化问题。我们也证明了这个问题是强NP困难的。在SET‐COVER变量中，项是跟随者试图覆盖的某个基集的子集。当他使用标准的原始-对偶方法时，我们证明了当元素的频率为2 （VERTEX - COVER变体）时，精确的收益最大化是可能的多项式时间。这与频率为3的元素的问题的APX硬度形成鲜明对比。©2011 Wiley期刊公司网络,2012
In Stackelberg pricing a leader sets prices for items to maximize revenue from a follower purchasing a feasible subset of items. We consider computationally bounded followers who cannot optimize exactly over the range of all feasible subsets, but who apply publicly known algorithms to determine the items to purchase. This corresponds to general multidimensional pricing when customers cannot optimize their valuation functions efficiently but still aim to act rationally to the best of their ability. We consider two versions of this novel type of pricing problem. In the MIn‐KNAPSACK variant items are weighted objects and the follower seeks to purchase a min‐cost selection of objects of some bounded weight. When he uses a greedy 2‐approximation algorithm, we provide a polynomial‐time (2+ε) ‐approximation algorithm for the leader's revenue maximization problem based on so‐called near‐uniform price assignments. We also prove the problem to be strongly NP‐hard. In the SET‐COVER variant items are subsets of some ground set which the follower seeks to cover. When he uses a standard primal‐dual approach, we prove that exact revenue maximization is possible in polynomial time when elements have frequency 2 (VERTEX‐COVER variant). This stands in sharp contrast to APX‐hardness for the problem with elements of frequency 3. © 2011 Wiley Periodicals, Inc. NETWORKS, 2012