Infinite-Dimensional Fisher Markets: Equilibrium, Duality and Optimization

Authors

  • Yuan Gao Columbia University
  • Christian Kroer Columbia University

DOI:

https://doi.org/10.1609/aaai.v35i6.16684

Keywords:

Equilibrium, Fair Division, Other Foundations of Game Theory & Economic Parad

Abstract

This paper considers a linear Fisher market with n buyers and a continuum of items. In order to compute market equilibria, we introduce (infinite-dimensional) convex programs over Banach spaces, thereby generalizing the Eisenberg-Gale convex program and its dual. Regarding the new convex programs, we establish existence of optimal solutions, KKT conditions, as well as strong duality. All these properties are established via non-standard arguments, which circumvent the limitations of duality theory in optimization over infinite-dimensional vector spaces. Furthermore, we show that there exists a pure equilibrium allocation, i.e., a division of the item space. Similar to the finite-dimensional case, a market equilibrium under the infinite-dimensional Fisher market is Pareto optimal, envy-free and proportional. We also show how to obtain the (a.e. unique) equilibrium prices and a pure equilibrium allocation from the (unique) equilibrium utility prices. When the item space is the unit interval [0,1] and buyers have piecewise linear utilities, we show that approximate equilibrium prices can be computed in polynomial time. This is achieved by solving a finite-dimensional convex program using the ellipsoid method. To this end, we give nontrivial and efficient subgradient and separation oracles. For general buyer valuations, we propose computing market equilibrium using stochastic dual averaging, which finds approximate equilibrium prices with high probability.

Downloads

Published

2021-05-18

How to Cite

Gao, Y., & Kroer, C. (2021). Infinite-Dimensional Fisher Markets: Equilibrium, Duality and Optimization. Proceedings of the AAAI Conference on Artificial Intelligence, 35(6), 5432-5439. https://doi.org/10.1609/aaai.v35i6.16684

Issue

Section

AAAI Technical Track on Game Theory and Economic Paradigms