PoA of Simple Auctions with Interdependent Values
Authors: Alon Eden, Michal Feldman, Inbal Talgam-Cohen, Ori Zviran5321-5329
AAAI 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We expand the literature on the price of anarchy (Po A) of simultaneous item auctions by considering settings with correlated values; we do this via the fundamental economic model of interdependent values (IDV). It is well-known that in multi-item settings with private values, correlated values can lead to bad Po A, which can be polynomially large in the number of agents n. In the more general model of IDV, we show that the Po A can be polynomially large even in singleitem settings. On the positive side, we identify a natural condition on information dispersion in the market, which enables good Po A guarantees. Under this condition, we show that for single-item settings, the Po A of standard mechanisms degrades gracefully. For settings with multiple items we show a separation between two domains: If there are more buyers, we devise a new simultaneous item auction with good Po A, under limited information asymmetry. To the best of our knowledge, this is the first positive Po A result for correlated values in multi-item settings. The main technical difficulty in establishing this result is that the standard tool for establishing Po A results the smoothness framework is unsuitable for IDV settings, and so we must introduce new techniques to address the unique challenges imposed by such settings. |
| Researcher Affiliation | Academia | Alon Eden 1, Michal Feldman 2, Inbal Talgam-Cohen 3, Ori Zviran 2 1 Harvard University 2 Tel Aviv University 3 Technion, Israel Institute of Technology |
| Pseudocode | Yes | Figure 1: Simultaneous privatized second-price auctions. Input: Bid and participation profiles b and a. Output: An allocation and payments. For every item ℓ(simultaneously): 1. For every agent j, compute the privatized value ˆvjℓ(bℓ) = vjℓ(bjℓ, 0 jℓ) 2. Allocate item ℓto agent i argmax{ˆvjℓ(bℓ)|ajℓ= 1} 3. Charge agent i a payment piℓ(bℓ, aℓ) = max{0, max j =i {ˆvjℓ(bℓ)|ajℓ= 1}} |
| Open Source Code | No | The paper states |
| Open Datasets | No | The paper is theoretical and does not use datasets or perform experiments, therefore no public dataset information is provided. |
| Dataset Splits | No | The paper is theoretical and does not perform experiments, therefore no dataset split information is provided. |
| Hardware Specification | No | The paper is theoretical and does not discuss hardware used for experiments. |
| Software Dependencies | No | The paper is theoretical and does not mention specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup with hyperparameters or training settings. |