On the Power of Randomization for Obviously Strategy-Proof Mechanisms
Authors: Shiri Ron, Daniel Schoepflin
AAAI 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our main results are upper bounds and lower bounds for randomized OSP mechanisms. We focus our attention on universally OSP mechanisms, i.e., mechanisms which are a distribution over deterministic OSP mechanisms. We analyze all the settings considered by (Ron 2024) and show that: 1. For additive bidders in a combinatorial auction, there is a mechanism that obtains a 4 approximation and no mechanism has approximation better than 8 7 1.14 (Theorem 5 and Theorem 6). 2. For unit-demand bidders in a combinatorial auction, there is a mechanism that obtains an e 2.72 approximation and no mechanism has approximation better than than 8 7 1.14 (Theorem 7 and Theorem 8). 3. For single-minded bidders in a multi-unit auction with unknown demands, there is a mechanism that obtains a 400 approximation and no mechanism has approximation better than 1.2 (Theorem 2 and Theorem 4). |
| Researcher Affiliation | Academia | 1Weizmann Institute of Science 2Rutgers University DIMACS EMAIL, EMAIL |
| Pseudocode | Yes | MECHANISM 1: SINGLE-MINDED Input: A set of bidders N and m identical items 1 With probability 1/2: 2 Bundle all m items together and run an ascending price auction on the grand bundle 3 With remaining probability 1/2: 4 let S , U 5 Place each bidder independently in S w.p. 1/2 and each bidder in U with the remaining probability 6 Discard each bidder and S and learn their valuation function 7 Compute the optimal solution among bidders only in S and let O denote the value of this solution 8 Iterate over the bidders (in an arbitrary) order, and for each bidder i N, let them purchase their preferred bundle from the remaining items at a price of O/10m per item |
| Open Source Code | No | The paper does not provide any statements about code availability, nor does it include links to repositories or supplementary materials containing code. |
| Open Datasets | No | The paper discusses theoretical 'instances' of bidder valuations for its analysis and does not refer to or provide access information for any publicly available or open datasets for experimental use. |
| Dataset Splits | No | The paper does not conduct experiments using empirical datasets, therefore, it does not specify any training/test/validation dataset splits. |
| Hardware Specification | No | The paper describes theoretical models and mathematical proofs, and does not conduct experiments that would require specific hardware. Therefore, no hardware specifications are mentioned. |
| Software Dependencies | No | The paper presents theoretical work on mechanism design and does not describe any specific software implementations or dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical in nature, presenting proofs and analysis of mechanism design. It does not include any experimental results or, consequently, details about an experimental setup, hyperparameters, or training configurations. |