arXiv:2511.19842 · v4

Strategy-robust Online Learning in Contextual Pricing

首次提交 2025-11-25 10:16

版本更新 2026-11-09 13:11

雷达观测 2026-11-10 13:18

摘要

Learning effective pricing strategies is crucial in digital marketplaces, especially when buyers' valuations are unknown and must be inferred through interaction. We study online contextual pricing with sealed bids from multiple recurring buyers. The seller selects an affine pricing policy before observing the current context and competes with the best fixed policy in the same class. Buyers may misreport their values to influence future prices, a challenge known as strategic overfitting (Amin et. al., 2013). We introduce a strategy-robust notion of regret for multi-buyer online environments, capturing worst-case strategic behavior in the spirit of the Price of Anarchy. Our first contribution is a polynomial-time approximation scheme (PTAS) for learning affine pricing policies against arbitrary context-value sequences: for every fixed $ε>0$, it runs in polynomial time and its regret is $O(εT)$ plus a term sublinear in $T$. The scheme is based on an online sketch constructed from past contexts. We then propose the Sparse Update Mechanism (SUM), which learns only from a privately selected subset of rounds and occasionally posts a random price drawn from a finite grid. SUM is a PTAS for strategic regret, and its guarantee holds uniformly over all Nash equilibria. Both schemes use an online expert algorithm as a black box and run in $(T/ε)^{O(ε^{-2})}\mathsf{poly}(d,T,1/ε)$ time. Furthermore, we show that, even with truthful bids, no seller algorithm can achieve regret $\mathsf{poly}(d,1/ε)\,T^z+εT$ with $z<1$ in time $\mathsf{poly}(d,T,1/ε)$ unless $\mathrm{NP}\subseteq\mathrm{BPP}$.

作者备注：30 pages. v3 is the preliminary version published at ALT 2026. This version extends the results to affine pricing policies, improves the regret and running-time bounds, and bases the lower bound on NP-hardness rather than ETH, which was recently claimed to be false