Why Prices Need Algorithms
Authors: Tim Roughgarden, Inbal Talgam-Cohen
IJCAI 2016 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this note we survey our main results from [Roughgarden and Talgam-Cohen, 2015], which show that the existence of equilibria in markets is inextricably connected to the computational complexity of related optimization problems, such as revenue or welfare maximization. We demonstrate how this relationship implies, under suitable complexity assumptions, a host of impossibility results. We also suggest a complexity-theoretic explanation for the lack of useful extensions of the Walrasian equilibrium concept: such extensions seem to require the invention of novel polynomial-time algorithms for welfare maximization. Theorem establishes a link between a purely economic question existence of equilibrium and a purely algorithmic one. |
| Researcher Affiliation | Academia | Tim Roughgarden Stanford University, Stanford CA tim@cs.stanford.edu Inbal Talgam-Cohen Hebrew University, Jerusalem Israel inbaltalgam@gmail.com |
| Pseudocode | No | The paper does not contain any pseudocode or clearly labeled algorithm blocks. It is a theoretical paper focusing on complexity theory. |
| Open Source Code | No | The paper is theoretical and does not describe the development of new software or code that would be open-sourced. Therefore, it does not contain any statement about the availability of open-source code. |
| Open Datasets | No | This is a theoretical paper that does not involve the use of datasets for training, validation, or testing. |
| Dataset Splits | No | This is a theoretical paper and does not describe any dataset splits (train/validation/test) for empirical evaluation. |
| Hardware Specification | No | The paper is theoretical and does not describe any experiments that would require hardware specifications. |
| Software Dependencies | No | The paper is theoretical and does not describe any software components with specific version numbers or dependencies for replication. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup with hyperparameters or system-level training settings. |