First-Order Methods for Large-Scale Market Equilibrium Computation
Authors: Yuan Gao, Christian Kroer
NeurIPS 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Numerical experiments show that Proportional Response dynamics is highly efficient for computing approximate market equilibria, while projected gradient with linesearch can be much faster when higher-accuracy solutions are needed. We perform numerical experiments on market instances under all three utilities with various generated parameters. |
| Researcher Affiliation | Academia | Yuan Gao Department of IEOR, Columbia University New York, NY, 10027 gao.yuan@columbia.edu Christian Kroer Department of IEOR, Columbia University New York, NY, 10027 christian.kroer@columbia.edu |
| Pseudocode | Yes | We prove that proximal gradient with a non-standard practical linesearch scheme (Algorithm 1 in the appendix) converges linearly |
| Open Source Code | Yes | Codes for the numerical experiments are available at https://github.com/Coffee And Convexity/fom-for-me-codes. |
| Open Datasets | No | For linear utilities, we generate market data v = (vij) where vij are i.i.d. from standard Gaussian, uniform, exponential, or lognormal distribution. For each of the sizes n = 50, 100, 150, 200 (on the horizontal axis) and m = 2n, we generate 30 instances with unit budgets Bi = 1 and random budgets Bi = 0.5 + Bi (where Bi follows the same distribution as vij). |
| Dataset Splits | No | The paper describes generating synthetic data and uses a termination criterion based on convergence error, not standard training/validation/test dataset splits. |
| Hardware Specification | No | Part of the numerical experiments were run on the computing server of Columbia University Data Science Institute https://datascience.columbia.edu/about-us/work-with-us/computing-resources/. This only states the location, not specific hardware components like CPU/GPU models. |
| Software Dependencies | No | The paper mentions CVXPY and Mosek but does not provide specific version numbers for these or other software dependencies. |
| Experiment Setup | Yes | For PGLS, we report the number of linesearch iterations (that is, the total number of projection computations). For other algorithms, we report the number of iterations. As a fair comparison, we use the same parameters α, β, Γ for PGLS throughout without handpicking. |