Research map / Reinforcement learning / Policy gradient and actor-critic
Optimal Mechanism in a Dynamic Stochastic Knapsack Environment
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.
Derives a revenue-maximizing dynamic mechanism for a stochastic knapsack with impatient buyers reporting value and quantity, with a quantity-overbidding penalty, and approximates the optimal policy via MC regression and DDPG.
Problem
Designing a revenue-maximizing, incentive-compatible dynamic mechanism for selling a divisible item to impatient buyers who privately report two-dimensional types (marginal value and demanded quantity) under random arrivals and a finite horizon.
Approach
Extends Myerson-style characterization to two-dimensional types with piecewise linear utility and a finite-horizon Bellman equation; adds a penalty for quantity overbidding to ensure incentive compatibility, and approximates the state value function via Chebyshev regression (Monte Carlo) or learns allocation with DDPG.
Key results
- MC regression with m=50 nodes achieves average test reward 163.40 at (T,Q)=(100,100), versus 91.24 for DDPG and 170.62 for full information.
- At (T,Q)=(10,10), MC (m=5 to 50) achieves about 21.8-21.9 reward, versus 13.40 for DDPG and 22.78 for full information.
- MC regression outperforms DDPG in all settings but requires much longer training time (714.4 min vs 5.1 min at largest size).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use MC regression instead of DDPG | approximation of the optimal policy · (T, Q̄) = (10, 10), (30, 30), and (100, 100) | average test rewards: 13.40 vs 21.77; 32.16 vs 56.71; 91.24 vs 115.88 | Helped |
| Increase MC node count from m=5 to m=10 (ablation) | MC regression · (T, Q̄) = (10, 10), (30, 30), and (100, 100) | average test rewards: 21.77 -> 21.80; 56.71 -> 62.84; 115.88 -> 132.62 | Helped |
| Increase MC node count from m=5 to m=20 (ablation) | MC regression · (T, Q̄) = (10, 10), (30, 30), and (100, 100) | average test rewards: 21.77 -> 21.88; 56.71 -> 63.48; 115.88 -> 146.75 | Helped |
| Increase MC node count from m=5 to m=50 (ablation) | MC regression · (T, Q̄) = (10, 10), (30, 30), and (100, 100) | average test rewards: 21.77 -> 21.88; 56.71 -> 63.74; 115.88 -> 163.40 | Helped |
| Increase MC node count from m=5 to m=50 (ablation) | MC regression · (T, Q̄) = (10, 10), (30, 30), and (100, 100) | training time (min): 0.9 -> 65.4; 2.7 -> 208.9; 9.1 -> 714.4 | Hurt |
| Use DDPG instead of MC regression | approximation of the optimal policy · (T, Q̄) = (10, 10), (30, 30), and (100, 100) | training time (min): 1.0 vs 0.9; 1.9 vs 2.7; 5.1 vs 9.1 | Helped |
Surprising findings
- DDPG allocates items early to arriving buyers, possibly due to value overestimation and insufficient late-stage state exploration.
Limitations
- Penalty scheme requires the seller to observe whether allocated quantity exceeds true demand at no cost (Assumption 1).
- Optimality relies on a regularity condition on the virtual valuation being non-decreasing in value and quantity.
- DDPG underperforms MC regression due to exploration issues in later periods.
Experimental setup
Datasets: synthetic buyer distributions: Poisson(10) arrivals, uniform(0,2) quantities, exponential values conditional on quantity
Benchmarks: simulated dynamic knapsack environments with (T, Q) = (10,10), (30,30), (100,100)
Metrics: average discounted test reward training time
Baselines: MC regression with varying nodes m DDPG full information virtual value maximization
Builds on: Myerson optimal auction dynamic stochastic knapsack problem DDPG
Closest papers by meaning
- Online Learning of Optimal Bidding Strategy in Repeated Multi-Commodity Auctions (NeurIPS 2017 · similarity 0.87)
- Robust Pricing in Dynamic Mechanism Design (ICML 2020 · similarity 0.86)
- Fair Allocation in Dynamic Mechanism Design (NeurIPS 2024 · similarity 0.86)
- Time Fairness in Online Knapsack Problems (ICLR 2024 · similarity 0.86)
- Mechanism Design via the Interim Relaxation (NeurIPS 2025 · similarity 0.86)
- Contextual Decision-Making with Knapsacks Beyond the Worst Case (NeurIPS 2024 · 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.