Research map / Learning theory and algorithms / Submodular and game algorithms
On the Power of Randomization for Obviously Strategy-Proof Mechanisms
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that randomized, universally obviously strategy-proof (OSP) mechanisms achieve constant-factor welfare approximations in multi-unit (single-minded), additive, and unit-demand combinatorial auctions, unlike deterministic OSP mechanisms, and gives randomized impossibility bounds.
Problem
Deterministic obviously strategy-proof mechanisms cannot approximate welfare better than min{m,n} in auctions with additive or unit-demand bidders; the paper asks whether randomization helps OSP mechanism design.
Approach
Randomized mechanisms that are distributions over deterministic OSP mechanisms; sample a random half of bidders to learn valuations and use their values to set item prices (or a secretary-style posted-price/online-matching procedure) for the remaining bidders, which is obviously dominant on each realization, yielding constant approximations.
Key results
- Universally OSP randomized mechanism for additive bidders achieves 4-approximation; lower bound 8/7 for randomized OSP.
- Unit-demand bidders: universally OSP mechanism achieves e (~2.72) approximation; lower bound 8/7.
- Single-minded unknown-demand multi-unit auction: 400-approximation; randomized lower bound 6/5, and welfare cannot exceed 87.5% of optimum for randomized OSP.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use randomized universally OSP sampling and posted prices | Additive bidders in combinatorial auctions · Combinatorial auction, additive bidders | approximation ratio: 4 | Helped |
| Allow randomization in universally OSP mechanisms | Additive bidders in combinatorial auctions · Combinatorial auction, additive bidders | approximation ratio: \frac{8}{7} | Hurt |
| Use the randomized universally OSP online-matching mechanism | Unit-demand bidders in combinatorial auctions · Combinatorial auction, unit-demand bidders | approximation ratio: e | Helped |
| Allow randomization in universally OSP mechanisms | Unit-demand bidders in combinatorial auctions · Combinatorial auction, unit-demand bidders | approximation ratio: \frac{8}{7} | Hurt |
| Use balanced sampling and uniform pricing, with a randomized grand-bundle auction | Unknown single-minded bidders in multi-unit auctions · Multi-unit auction, unknown single-minded bidders | approximation ratio: 400 | Helped |
| Allow randomization in OSP mechanisms | Unknown single-minded bidders in multi-unit auctions · Multi-unit auction, unknown single-minded bidders | approximation ratio: \nicefrac{6}{5} | Hurt |
| Randomly choose a fixed power-of-two bundle size | Random-Bundles for unknown single-minded bidders · Multi-unit auction, unknown single-minded bidders | approximation ratio: \mathcal O(\log{m}) | Helped |
| Use the randomized balanced-sampling mechanism | Bidders with decreasing marginal valuations · Multi-unit auction, decreasing marginal valuations | approximation ratio: 400 | Helped |
| Add an item, allocate one item to each bidder, then run an ascending auction on the remaining item | Deterministic OSP mechanisms for decreasing marginal valuations · Multi-unit auction, 2 bidders, 2 versus 3 items | approximation ratio: 2; 1.5 | Helped |
| Use the randomized mechanism for subadditive valuations | Subadditive bidders · Combinatorial auction, subadditive valuations | approximation ratio: O((\log\log(m))^3) | Helped |
| Use the randomized mechanism for general valuations | General bidders · Combinatorial auction, general valuations | approximation ratio: O(\sqrt{m}) | Helped |
| Mix the grand-bundle auction with random single-item allocation and an auction for the other item | M1 for unknown single-minded bidders · Multi-unit auction, 2 bidders and 2 items | approximation ratio: \nicefrac 4 3 | Helped |
Surprising findings
- For two bidders and two items, adding an item improves deterministic OSP approximation for decreasing marginal valuations (3 items gives 1.5 vs lower bound 2 for 2 items).
Limitations
- Gap between upper bounds (4, e, 400) and lower bounds (8/7, 8/7, 6/5)
- Upper bounds for general complement-free valuations not resolved
- Lower bounds rely on distributions with few instances; super-constant lower bounds need new techniques
Experimental setup
Metrics: approximation ratio of social welfare
Baselines: deterministic OSP mechanisms ascending-price auction for grand bundle VCG
Builds on: obviously strategy-proof mechanisms (Li 2017) Yao's lemma random-order secretary-based online matching mechanism
Closest papers by meaning
- Obvious Strategyproofness Needs Monitoring for Good Approximations (AAAI 2017 · similarity 0.90)
- Breaking Barriers, Finding Boundaries: Not Obviously Manipulable Budget-Feasible Mechanism Design (AAAI 2026 · similarity 0.89)
- Safely Learning Optimal Auctions: A Testable Learning Framework for Mechanism Design (ICML 2025 · similarity 0.88)
- A Unified Framework for Uniform-Price Resource Allocation Mechanisms (NeurIPS 2026 · similarity 0.87)
- Fair Allocation in Dynamic Mechanism Design (NeurIPS 2024 · similarity 0.87)
- Computing Perfect Bayesian Equilibria in Sequential Auctions with Verification (AAAI 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.