The Price of Anarchy in Auctions
Authors: Tim Roughgarden, Vasilis Syrgkanis, Eva Tardos
JAIR 2017 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | This survey outlines a general and modular theory for proving approximation guarantees for equilibria of auctions in complex settings. This theory complements traditional economic techniques, which generally focus on exact and optimal solutions and are accordingly limited to relatively stylized settings. We highlight three user-friendly analytical tools: smoothness-type inequalities, which immediately yield approximation guarantees for many auction formats of interest in the special case of complete information and deterministic strategies; extension theorems, which extend such guarantees to randomized strategies, no-regret learning outcomes, and incomplete-information settings; and composition theorems, which extend such guarantees from simpler to more complex auctions. Combining these tools yields tight worst-case approximation guarantees for the equilibria of many widely-used auction formats. |
| Researcher Affiliation | Collaboration | Tim Roughgarden EMAIL Computer Science Department, Stanford University, Stanford, CA USA. Vasilis Syrgkanis EMAIL Microsoft Research, 1 Memorial Drive, Cambridge, MA USA. Eva Tardos EMAIL Computer Science Department, Cornell University, Ithaca, NY USA. |
| Pseudocode | No | The paper does not contain any clearly labeled pseudocode or algorithm blocks. It primarily presents theoretical arguments, definitions, and proofs in a narrative and mathematical format. |
| Open Source Code | No | This paper is a theoretical survey and does not present new methodology that would typically involve source code release. There is no mention of providing open-source code or links to repositories. |
| Open Datasets | No | The paper is a theoretical survey and does not conduct empirical experiments using specific datasets. It discusses theoretical models and distributions (e.g., "uniform distribution on [0, 1]") but does not provide access information for any open datasets. |
| Dataset Splits | No | The paper is theoretical and does not involve experimental evaluation on datasets, thus it does not mention any training, validation, or test dataset splits. |
| Hardware Specification | No | The paper is a theoretical survey and does not describe any computational experiments or the hardware used to perform them. |
| Software Dependencies | No | The paper is a theoretical survey and does not describe any software implementations or specific dependencies with version numbers. |
| Experiment Setup | No | The paper is a theoretical survey and does not include any experimental setup details such as hyperparameters or system-level training settings. |