Constantinos Daskalakis2014-03-14 1:18 PM

最优多维定价的极值定理 Extreme-Value Theorems for Optimal Multidimensional Pricing

论文摘要: 
对于多维度单位需求定价问题即当消费者的心理价值相互独立时(但是未必是恒等分布的),我们提供了一个多项式时间近似算法。对于任意epsilon>0的情况,我们得到(1+epsilon)这个因子来近似最优收益。有以下三种情况:当这些价值数据是从符合单调风险率分布中取样得到时,近似值符合时间多项式;而从常规分布中取样时,近似值符合准多项式;而对于点集[u,r*u]上的广义分布,近似值符合n^poly(log r)的多项式。同时我们对于所有有界分布提供一个附加的近似算法。我们的算法是基于关于单调风险率以及常规分布的特殊极值定理,而且运用概率论来理解收益分布的统计性质,同时缩小算法的搜索空间大小。我们证明了最优化问题算法的结构特性,而这得益于我们的方法。我们证明了对于任意epsilon>0,g(1/epsilon)不同的价格足够得到一个(1+epsilon)因子近似得到对于MHR分布的最优收益,而此时g(1/epsilon)是关于1/epsilon的不依赖于物品数的拟线性函数。同样的,对于任意epsilon>0以及n>0,g(1+epsilon*logn)不同的价格对于常规分布而言也能满足,这里n是物品数,而g()是一个多项式函数。最后,在独立且等分布的MHR分布中,我们证明了,只要物品数对于关于1/epsilon的函数足够大,单个价格也足以得到(1+epsilon)因子近似值。

Abstract:
We provide a Polynomial Time Approximation Scheme for the multi-dimensional unit-demand pricing problem, when the buyer's values are independent (but not necessarily identically distributed). For all epsilon>0, we obtain a (1+epsilon) factor approximation to the optimal revenue in time polynomial, when the values are sampled from Monotone Hazard Rate (MHR) distributions, quasi-polynomial, when sampled from regular distributions, and polynomial in n^poly(log r), when sampled from general distributions supported on a set [u, r * u]. We also provide an additive PTAS for all bounded distributions. Our algorithms are based on novel extreme value theorems for MHR and regular distributions, and apply probabilistic techniques to understand the statistical properties of revenue distributions, as well as to reduce the size of the search space of the algorithm. As a byproduct of our techniques, we establish structural properties of optimal solutions. We show that, for all epsilon >0, g(1/epsilon) distinct prices suffice to obtain a (1+epsilon)-factor approximation to the optimal revenue for MHR distributions, where g(1/epsilon) is a quasi-linear function of 1/epsilon that does not depend on the number of items. Similarly, for all epsilon>0 and n>0, g(1/epsilon * log n) distinct prices suffice for regular distributions, where n is the number of items and g() is a polynomial function. Finally, in the i.i.d. MHR case, we show that, as long as the number of items is a sufficiently large function of 1/epsilon, a single price suffices to achieve a (1+epsilon)-factor approximation.

KEYWORDS

SHARE & LIKE

COMMENTS

ABOUT THE AUTHOR

Constantinos Daskalakis

Associate Professor at MIT's Electrical Engineering and Computer Science department, a member of CSAIL, and affiliated with LIDS and ORC.

0 Following 2 Fans 0 Projects 10 Articles

SIMILAR ARTICLES

论文摘要 最近在[12]中表明, 在所有具有任意(可能的组合)可行性约束和受任意(可能组合)需求约束的独立添加的投标人的多维贝叶斯拍卖问题中,收入最优化可以从计算上有效减持至福利最优化。这种减持在所有拍卖假设中给可以得到有效解决的最优化机制设计问题提供了一种多项式时间解决方案,但它的这种逼近很脆弱且不

Read More

论文摘要 线性编程低密度奇偶校验码(和例如压缩感知的相关领域)的解码由于其近似于迭代解码算法的实际性能和它对有限块长度分析的可处理性在近几年已获得越来越多的关注。一些和Feldman等人所著同期的著作展示了如何使用膨胀曲线特性分析LP解码。这一分析线性具有低误差率,比经验观察性能更低上几个数量级。如同

Read More

Abstract:We propose a new no-regret learning algorithm. When used against an adversary, our algorithm achieves average regret that scales as O (1/√T) w

Read More

论文摘要: 1951年,约翰·F·纳什证明了任何博弈都存在纳什均衡。但是他的证明是非构造性质的,依赖于布劳威尔的不动点定理,于是也引发了以下的问题:是不是存在一种多项式时间算法来计算纳什均衡呢?以及这是不是取决于布劳威尔其不动点定理的内在规律?基于此点出发,之后提出了很多算法试图寻找纳什均衡点,但是没

Read More

论文摘要: 基于允许插入与缺失(即简称为indels)条件的层序演化模型我们引进了一级多项式时间系统发育重建算法。基于合适的假设,我们的算法要求序列长度随叶形分类群数呈现多项式形式的增长。我们的方法是是基于距离测量而且在很大程度上绕开了多重调节的问题。Abstract:We introduce the

Read More

论文摘要: 对于多维度单位需求定价问题即当消费者的心理价值相互独立时(但是未必是恒等分布的),我们提供了一个多项式时间近似算法。对于任意epsilon>0的情况,我们得到(1+epsilon)这个因子来近似最优收益。有以下三种情况:当这些价值数据是从符合单调风险率分布中取样得到时,近似值符合时间多项式

Read More

论文摘要 我们引入了一种新系统发育重建算法,不同于以往大多数严谨的推理技术,该算法不依赖于有关分支长度或树深度的假设。该算法返回了保证含有以下所有边界的森林: 1)足够长 2)足够接近叶。 真正树中有多少能够得到恢复依赖于所提供序列的长度。该算法基于距离且在多项式时间中运行。 Abstract:We

Read More

论文摘要 排序和搜索的经典问题假设了被比较对象的一个基本线性排序。在本文中我们基于偏序背景研究了这些问题,其中对象的某些对不可类比。从组合角度来看,这种概括很有趣,且它可在例如会议提交的非基于线性排序排名场景中有直接应用。它也可应用于例如包括生物网络的某些类型网络的重构中。与二十年前由Faigle和T

Read More

Abstract:A major task of evolutionary biology is the reconstruction of phylogenetic trees from molecular data. The evolutionary model is given by a Mar

Read More

Abstract:We introduce CLS, for continuous local search, a class of polynomial-time checkable total functions that lies at the intersection of PPAD and

Read More