Infinite-Dimensional Fisher Markets and Tractable Fair Division

Yuan Gao () and Christian Kroer ()
Additional contact information
Yuan Gao: Department of Industrial Engineering and Operations Research, Columbia University, New York, New York 10027
Christian Kroer: Department of Industrial Engineering and Operations Research, Columbia University, New York, New York 10027

Operations Research, 2023, vol. 71, issue 2, 688-707

Abstract: Linear Fisher markets are a fundamental economic model with diverse applications. In the finite-dimensional case of n buyers and m items, a market equilibrium can be computed using the celebrated Eisenberg-Gale convex program. Motivated by large-scale Internet advertising and fair division applications, we consider a generalization of a linear Fisher market where there is a finite set of buyers and a measurable item space. We introduce generalizations of the Eisenberg-Gale convex program and its dual to this setting, which leads to infinite-dimensional Banach-space optimization problems. We show that these convex programs always have optimal solutions, and these optimal solutions correspond to market equilibria. In particular, a market equilibrium always exists. We also show that Karush-Kuhn-Tucker–type optimality conditions for these convex programs imply the defining properties of market equilibria and are necessary and sufficient for a solution pair to be optimal. Then, we show that, similar to the classical finite-dimensional case, a market equilibrium is Pareto optimal, envy-free, and proportional. Moreover, when the item space measure is atomless (e.g., the Lebesgue measure), we show that there always exists a pure equilibrium allocation, which can be viewed as a generalized fair division, that is, a Pareto optimal, envy-free, and proportional partition of the item space. This leads to generalizations of classical results on the existence and characterizations of fair division of a measurable set. When the item space is a closed interval and buyers have piecewise linear valuations, we show that the infinite-dimensional Eisenberg-Gale–type convex program can be reformulated as a finite-dimensional convex conic program, which can be solved efficiently using off-the-shelf optimization software. Based on the convex conic reformulation, we also develop the first polynomial-time algorithm for finding a fair division of an interval under piecewise linear valuations. For general buyer valuations or a very large number of buyers, we propose computing market equilibria using stochastic optimization and give high-probability convergence guarantees. Finally, we show that most of the above results easily extend to the case of quasilinear utilities.

Keywords: Revenue Management and Market Analytics; Fisher market; fair division; market equilibrium; convex optimization (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2022.2344 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:71:y:2023:i:2:p:688-707

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().