Research map / Learning theory and algorithms / Submodular and game algorithms
Ad Auctions and Cascade Model: GSP Inefficiency and Algorithms
Gabriele Farina, Nicola Gatti
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use APDC-aware allocation instead of GSP's value-ordered allocation | GSP · APDC, unrestricted bidding | social-welfare PoA: unbounded | Improved |
| Use APDC-aware allocation instead of VCG with PDC | VCG with PDC · APDC, unrestricted bidding | social-welfare PoA: unbounded | Improved |
| Discard ads proven to be dominated before searching for an allocation | APDC allocation algorithms · Yahoo! Webscope A3, K = 5, N = 1,000 | prune ratio: approximately 96% | Improved |
| Use randomized color coding on the reduced ad set | colored-ads · Yahoo! Webscope A3, K = 5, N = 1,000 | running time: less than 1ms | Improved |
| Use randomized color coding on the reduced ad set | colored-ads · Yahoo! Webscope A3, K = 10 | running time: ≈0.5 seconds | Mixed |
| Approximate the allocation by searching over 2K^3 random ad orders | sorted-ads · Yahoo! Webscope A3, shrunk instances | approximation ratio: >97%; >99% | Improved |
| Approximate the allocation using sorted-ads | APDC allocation · Yahoo! Webscope A3, N = 1,000 | running time: less than 5ms | Improved |
| Use 1.3K colors instead of K colors (ablation) | colored-ads · APDC allocation | approximation improvement | No clear effect |
Closest papers by meaning
- Fair Allocation in Dynamic Mechanism Design (NeurIPS 2024 · similarity 0.85)
- AuctionNet: A Novel Benchmark for Decision-Making in Large-Scale Games (NeurIPS 2024 · similarity 0.85)
- Autobidder's Dilemma: Why More Sophisticated Autobidders Lead to Worse Auction Efficiency (NeurIPS 2024 · similarity 0.85)
- Efficiency of the First-Price Auction in the Autobidding World (NeurIPS 2024 · similarity 0.84)
- Maximizing the Success Probability of Policy Allocations in Online Systems (AAAI 2024 · similarity 0.84)
- Dynamic Budget Throttling in Repeated Second-Price Auctions (AAAI 2024 · similarity 0.84)
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.
