Infinite-Dimensional Fisher Markets: Equilibrium, Duality and Optimization
Authors: Yuan Gao, Christian Kroer5432-5439
AAAI 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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. ... 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. |
| Researcher Affiliation | Academia | Yuan Gao, Christian Kroer Columbia University, Department of Industrial Engineering and Operations Research gao.yuan@columbia.edu, christian.kroer@columbia.edu |
| Pseudocode | Yes | Algorithm 1: Stochastic dual averaging (SDA) Initialize: Choose β1 dom Ψ and g0 = 0 for t = 1, 2, . . . do Sample θt D and compute gt βf(β, θt) gt = t 1 t gt βt+1 = arg minβ { gt, β + Ψ(β)} ( ) |
| Open Source Code | No | The paper does not provide explicit statements or links indicating that the source code for the described methodology is publicly available. |
| Open Datasets | No | The paper is theoretical and does not use or evaluate on a publicly available dataset for training or other purposes. The illustrative example uses a synthetic setup. |
| Dataset Splits | No | The paper does not describe empirical experiments with data, therefore, it does not specify training, validation, or test dataset splits. |
| Hardware Specification | No | The paper is theoretical and focuses on algorithmic complexity analysis rather than empirical evaluation, thus it does not specify hardware used for experiments. |
| Software Dependencies | No | The paper does not provide specific software dependencies with version numbers for its implementation or analysis. |
| Experiment Setup | No | The paper is theoretical and does not describe an empirical experimental setup with specific hyperparameters or training configurations. |