Research map / Bandits and online learning / Online convex optimization and games
Dynamic Service Fee Pricing under Strategic Behavior: Actions as Instruments and Phase Transition
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.
Studies dynamic service-fee pricing against far-sighted strategic buyers, using non-i.i.d. actions as instrumental variables, active randomness injection and low-switching updates to get e O(1) regret when supply is noisy and e O(sqrt T) otherwise, with a phase transition at supply variance ~1/sqrt(T).
Problem
Revenue-maximizing service-fee pricing on a third-party platform when only equilibrium prices and quantities are observed (confounded by supply and demand shocks), and the representative buyer is far-sighted and may misreport her demand.
Approach
Uses the platform's own service-fee actions (non-i.i.d., endogenous) as instrumental variables to consistently estimate a linear demand curve from equilibrium data; injects exploration noise only when supply is deterministic; uses low-switching (doubling-episode) updates to make far-sighted buyers nearly truthful; supply randomness itself provides exploration, yielding a phase transition in regret
Key results
- Regret of e O(sqrt T) when supply has no noise (Theorem 3.1), and e O(1) regret when supply variance is constant (Theorem 3.2); matching lower bounds up to logs.
- Adaptive AAaI algorithm achieves e O(min(sqrt T, sigma_S^{-2})) regret without knowing sigma_S (Theorem 4.3), giving a phase transition near sigma_S^2 ~ 1/sqrt T.
- Simulation with sigma_S^2=1 at T=10^5 gives regret about 237, versus over 1200 for sigma_S=0 (reported in the paper).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use AaI with supply randomness instead of the deterministic-supply setting | AaI · Dynamic service-fee pricing | regret: O(√T) to O(log T) | Helped |
| Use AAaI to adapt to unknown supply randomness | Dynamic service-fee pricing · Unknown supply randomness | expected regret: eO(√T ∧ σ−2S) | Helped |
| Increase supply variance | AaI · Simulation | regret | Helped |
| Apply the low-switching pricing policy to strategic buyers | AaI · Dynamic service-fee pricing with γ ∈ [0, 1) | regret: O(log T/(σ²S(1−γ))) | Helped |
Surprising findings
- Supply randomness helps learning: regret drops from order sqrt(T) to order constant once supply noise is present.
- Abstract claims no learning algorithm achieves sublinear regret when buyer patience matches seller, which motivates restricting to discount rates below one.
Limitations
- Restricted to linear supply and demand curves with a single representative buyer.
- Discount rate gamma must be strictly below one; gamma=1 admits no sublinear regret.
- Conjectured Omega(1/(1-gamma)) dependence on discount rate remains open.
Experimental setup
Benchmarks: simulated linear pricing environment (T=10^5 and T=10^4)
Metrics: cumulative revenue regret log-regret slope
Baselines: Golrezaei et al. repeated auction pricing Amin et al. (no-regret impossibility for patient buyers)
Builds on: Nambiar et al. instrumental variable demand learning Golrezaei et al. strategic buyer pricing Amin et al. patient buyer lower bound Broder and Rusmevichientong dynamic pricing
Closest papers by meaning
- Revenue Maximization Under Sequential Price Competition Via The Estimation Of $s$-Concave Demand Functions (ICLR 2026 · similarity 0.87)
- Dynamic Pricing for Reusable Resources in Competitive Market With Stochastic Demand (AAAI 2018 · similarity 0.86)
- Improved Algorithms for Contextual Dynamic Pricing (NeurIPS 2024 · similarity 0.85)
- Contextual Dynamic Pricing with Heterogeneous Buyers (NeurIPS 2025 · similarity 0.84)
- Non-Linear Pricing Restores Tractability for a Data Seller (NeurIPS 2026 · similarity 0.84)
- Pricing Online LLM Services with Data-Calibrated Stackelberg Routing Game (AAAI 2026 · 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.