Research map / Learning theory and algorithms / Submodular and game algorithms
Merging Mechanisms for Ads and Organic Items in E-commerce Platforms
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.
Designs IC and IR merging mechanisms (G-FIX and G-CHANGE) that combine ad and organic items for multi-slot e-commerce search pages, with approximation guarantees versus the optimal mechanism.
Problem
Merging ads (sponsored search auction) and organic items (recommendation) into one search result page under incentive compatibility, individual rationality, multi-slot feasibility, and avoidance of repeated exposure of the same item in ad and organic forms.
Approach
Characterizes necessary conditions of optimal merging mechanisms (form stability, partial order of organic items in the 2-out-of-3 case) and proposes two simple mechanisms: G-FIX restricts each item to one form and picks the best restriction; G-CHANGE allows ordered items to take either form, decided in reverse order, extending a single-slot model to k slots.
Key results
- G-FIX is (4/5)^3-approximate to the optimal mechanism for 3 items and 2 slots.
- G-CHANGE is optimal for 3 items and 2 slots.
- G-CHANGE is 1/2-approximate in the general n-item, k-slot setting without distributional assumptions.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use G-FIX | content merging with 3 items and 2 slots · 3 items, 2 slots | approximation ratio to optimal objective: (4/5)^3 | Helped |
| use G-FIX with identical bid distributions and 2k ≤ n | content merging with n items and k slots · n items, k slots; 2k ≤ n and identical bid distributions | approximation ratio to optimal objective: C_{n-k}^{k}/C_{n}^{k} | Helped |
| use G-FIX when n ≥ k^2/ε + k and bid distributions are identical | content merging with n items and k slots · n items, k slots; n ≥ k^2/ε + k and identical bid distributions | approximation ratio to optimal objective: 1-ε | Helped |
| use G-CHANGE | content merging with 3 items and 2 slots · 3 items, 2 slots | approximation ratio to optimal objective: optimal | Helped |
| use G-CHANGE | content merging with n items and k slots · n items, k slots | approximation ratio to optimal objective: 1/2 | Helped |
Limitations
- Approximation guarantees for G-FIX require identical bid distributions and 2k <= n; general setting only guarantees 1/2 for G-CHANGE.
- Optimality of G-CHANGE proven only for 3 items and 2 slots.
- Heterogeneous slots not addressed.
Experimental setup
Metrics: approximation ratio relative to optimal mechanism
Baselines: optimal merging mechanism
Builds on: Myerson's lemma single-slot ad-organic merging mechanism (cited prior work)
Closest papers by meaning
- On Designing the Optimal Integrated Ad Auction in E-commerce Platforms (AAAI 2025 · similarity 0.89)
- Strategic Recommendation: Revenue Optimal Matching for Online Platforms (Student Abstract) (AAAI 2024 · similarity 0.82)
- Truthful Aggregation of LLMs with an Application to Online Advertising (NeurIPS 2025 · similarity 0.82)
- Optimal Auction Design in the Joint Advertising (ICML 2025 · similarity 0.82)
- Beyond Last-Click: An Optimal Mechanism for Ad Attribution (NeurIPS 2025 · similarity 0.82)
- Fair Allocation in Dynamic Mechanism Design (NeurIPS 2024 · similarity 0.82)
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.