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

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.