A Perfect Price Discrimination Market Model with Production, and a Rational Convex Program for It
A Perfect Price Discrimination Market Model with Production, and a Rational Convex Program for It
复制标题
具有生产的完美价格歧视市场模型及其有理凸规划
DOI：
10.1287/moor.1110.0517
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
V. Vazirani
中科院分区：
文献类型：
--
作者：
G. Goel;V. Vazirani
最近的结果表明，在加法可分、分段线性、凹 (PLC) 效用下计算费雪市场模型均衡问题的 PPAD 完整性，对在“传统”市场模型中获得计算均衡的有效算法的计划造成了严重打击，并促使人们寻找既现实又适合高效计算的替代模型。在本文中，我们表明，将完美价格歧视引入具有 PLC 实用程序的 Fisher 模型使其均衡多项式时间可计算。此外，它的均衡集是由凸程序捕获的，该凸程序概括了经典的艾森伯格-盖尔程序，并且总是承认有理解。我们还给出了用于计算平衡的组合多项式时间算法。
接下来，我们将产生式引入模型中，并再次给出一个捕获其平衡点的有理凸程序。我们使用这个程序获得了该模型的两个福利定理的令人惊讶的简单证明。最后，我们还将价格歧视市场模型应用于在线展示广告市场。
Recent results showing PPAD-completeness of the problem of computing an equilibrium for Fisher's market model under additively separable, piecewise-linear, concave (PLC) utilities have dealt a serious blow to the program of obtaining efficient algorithms for computing equilibria in “traditional” market models, and has prompted a search for alternative models that are realistic as well as amenable to efficient computation. In this paper, we show that introducing perfect price discrimination into the Fisher model with PLC utilities renders its equilibrium polynomial time computable. Moreover, its set of equilibria are captured by a convex program that generalizes the classical Eisenberg-Gale program, and always admits a rational solution. We also give a combinatorial, polynomial time algorithm for computing an equilibrium.
Next, we introduce production into our model, and again give a rational convex program that captures its equilibria. We use this program to obtain surprisingly simple proofs of both welfare theorems for this model. Finally, we also give an application of our price discrimination market model to online display advertising marketplaces.