Infinite-Dimensional Fisher Markets and Tractable Fair Division

• 成果类型: Article
• 署名作者: Gao, Yuan; Kroer, Christian
• 署名单位: Columbia University
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2022.2344
• 发表日期: 2023
• 页码: 688-707
• 关键词: Fisher market; Fair division; Market equilibrium; Convex Optimization

摘要

Linear Fishermarkets are a fundamental economicmodelwith diverse applications. In the finite-dimensional case of n buyers and m items, amarket equilibriumcan 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 ameasurable itemspace. We introduce generalizations of the Eisenberg-Gale convex program and its dual to this setting, which leads to infinitedimensional Banach-space optimization problems. We show that these convex programs always have optimal solutions, and these optimal solutions correspond tomarket 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 ofmarket 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, envyfree, and proportional. Moreover, when the itemspacemeasure is atomless (e.g., the Lebesgue measure), we showthat there always exists a pure equilibriumallocation, 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 ameasurable set. When the itemspace is a closed interval and buyers have piecewise linear valuations, we show that the infinite-dimensional Eisenberg-Gale-type convex programcan 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 showthatmost of the above results easily extend to the case of quasilinear utilities.