A Perfect Price Discrimination Market Model with Production, and a Rational Convex Program for It

• 成果类型: Article
• 署名作者: Goel, Gagan; Vazirani, Vijay V.
• 署名单位: Alphabet Inc.; Google Incorporated; University System of Georgia; Georgia Institute of Technology
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.1110.0517
• 发表日期: 2011
• 页码: 762-782
• 关键词: equilibrium

摘要

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.