Simultaneous 2nd Price Item Auctions with No-Underbidding
Authors: Michal Feldman, Galia Shabtai5391-5398
AAAI 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the price of anarchy (Po A) of simultaneous 2nd price auctions (S2PA) under a new natural condition of no underbidding, meaning that agents never bid on items less than their marginal values. We establish improved (mostly tight) bounds on the Po A of S2PA under no underbidding for different valuation classes (including unit-demand, submodular, XOS, subadditive, and general monotone valuations), in both full-information and incomplete information settings. To derive our results, we introduce a new parameterized property of auctions, termed (γ, δ)-revenue guaranteed, which implies a Po A of at least γ/(1+δ). Via extension theorems, this guarantee extends to coarse correlated equilibria (CCE) in full information settings, and to Bayesian Po A (BPo A) in settings with incomplete information and arbitrary (correlated) distributions. We then show that S2PA are (1, 1)-revenue guaranteed with respect to bids satisfying no underbidding. This implies a Po A of at least 1/2 for general monotone valuation, which extends to BPOA with arbitrary correlated distributions. Moreover, we show that (λ, µ)-smoothness combined with (γ, δ)-revenue guaranteed guarantees a Po A of at least (γ + λ)/(1 + δ + µ). This implies a host of results, such as a tight Po A of 2/3 for S2PA with submodular (or XOS) valuations, under no overbidding and no underbidding. |
| Researcher Affiliation | Academia | Michal Feldman and Galia Shabtai Tel Aviv University michal.feldman@cs.tau.ac.il, galiashabtai@gmail.com |
| Pseudocode | No | The paper does not contain structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper states: "*For the full version, see https://arxiv.org/abs/2003.11857 (Feldman and Shabtai 2020)." This link refers to the full version of the paper itself, not source code for the methodology. |
| Open Datasets | No | The paper is theoretical and does not use datasets for training or evaluation. |
| Dataset Splits | No | The paper is theoretical and does not describe data splits for validation. |
| Hardware Specification | No | The paper is theoretical and does not describe running experiments, so no hardware specifications are provided. |
| Software Dependencies | No | The paper is theoretical and does not describe running experiments, so no software dependencies are provided. |
| Experiment Setup | No | The paper is theoretical and does not describe any experimental setup or training configurations. |