On revenue maximization with sharp multi-unit demands
On revenue maximization with sharp multi-unit demands
复制标题
论收入最大化与尖锐的多单位需求
DOI：
10.1007/s10878-014-9817-y
复制
发表时间：
2012-09
影响因子：
1
通讯作者：
Zhang, Jinshan
中科院分区：
文献类型：
--
作者：
Chen, Ning;Deng, Xiaotie;Goldberg, Paul W.;Zhang, Jinshan
我们认为市场由一组不可分割的物品组成，买家有多单位的需求。这意味着每个购买者都想要特定数量的物品;一捆小于的物品没有价值。我们考虑的目标是制定价格和分配，以最大限度地提高做市商的总收入。多单位需求下的定价问题具有单位需求模型所不具备的一些性质，是算法定价中的一个重要问题。我们考虑的问题计算收入最大化的解决方案的两个解决方案的概念：竞争均衡和无嫉妒定价。对于不受限制的估值，这些问题是NP完全的，我们专注于一个现实的特殊情况下的“相关值”，每个买家有一个项目的估值，其中和是积极的数量分别与买家和项目。我们提出了一个多项式时间算法来解决收入最大化的竞争均衡问题。对于无嫉妒定价，如果每个购买者的需求是有界的常数，一个收入最大化的解决方案，可以有效地找到一般的需求情况下，被证明是NP-难的。
We consider markets consisting of a set of indivisible items, and buyers that havesharpmulti-unit demand. This means that each buyerwants a specific numberof items; a bundle of size less thanhas no value. We consider the objective of setting prices and allocations in order to maximize the total revenue of the market maker. The pricing problem with sharp multi-unit demand buyers has a number of properties that the unit-demand model does not possess, and is an important question in algorithmic pricing. We consider the problem of computing a revenue maximizing solution for two solution concepts: competitive equilibrium and envy-free pricing. For unrestricted valuations, these problems are NP-complete; we focus on a realistic special case of “correlated values” where each buyerhas a valuationfor item, whereandare positive quantities associated with buyerand itemrespectively. We present a polynomial time algorithm to solve the revenue-maximizing competitive equilibrium problem. For envy-free pricing, if the demand of each buyer is bounded by a constant, a revenue maximizing solution can be found efficiently; the general demand case is shown to be NP-hard.
登录
查看更多内容
DOI：
10.1145/1386790.1386802
发表时间：
2008-07
期刊：
--
影响因子：
--
作者：
Maria-Florina Balcan;Avrim Blum;Y. Mansour
通讯作者：
Maria-Florina Balcan;Avrim Blum;Y. Mansour
DOI：
10.1007/978-3-319-39817-4
发表时间：
2016
期刊：
--
影响因子：
--
作者：
Daming Zhu;S. Bereg
通讯作者：
Daming Zhu;S. Bereg
DOI：
10.1007/978-3-642-10841-9_48
发表时间：
2009-09
期刊：
--
影响因子：
--
作者：
A. Fiat;Amiram Wingarten
通讯作者：
A. Fiat;Amiram Wingarten
DOI：
10.1007/978-3-540-77105-0_63
发表时间：
2007-12
期刊：
--
影响因子：
--
作者：
Arpita Ghosh;Hamid Nazerzadeh;Mukund Sundararajan
通讯作者：
Arpita Ghosh;Hamid Nazerzadeh;Mukund Sundararajan
DOI：
10.1007/978-3-319-08016-1
发表时间：
2014
期刊：
--
影响因子：
--
作者：
Jianer Chen;J. Hopcroft;Jian-xin Wang
通讯作者：
Jianer Chen;J. Hopcroft;Jian-xin Wang