The Competition Complexity of Dynamic Pricing
研究了在单一物品销售中，动态定价相对于最优拍卖的竞争复杂度，即需要多少个独立同分布的随机变量才能使动态定价的期望收益接近最优拍卖的期望收益，并给出了精确的竞争复杂度函数。
We study the competition complexity of dynamic pricing relative to the optimal auction in the fundamental single-item setting. In prophet inequality terminology, we compare the expected reward [Formula: see text] achievable by the optimal online policy on m independent and identically distributed (i.i.d.) random variables distributed according to F to the expected maximum [Formula: see text] of n i.i.d. draws from F. We ask how big m has to be to ensure that [Formula: see text] for all F. We resolve this question and characterize the competition complexity as a function of ε. When [Formula: see text], the competition complexity is unbounded. That is, for any n and m there is a distribution F such that [Formula: see text]. In contrast, for any [Formula: see text], it is sufficient and necessary to have [Formula: see text], where [Formula: see text]. Therefore, the competition complexity not only drops from unbounded to linear, it is actually linear with a very small constant. The technical core of our analysis is a lossless reduction to an infinite dimensional and nonlinear optimization problem that we solve optimally. A corollary of this reduction is a novel proof of the factor [Formula: see text] i.i.d. prophet inequality, which simultaneously establishes matching upper and lower bounds. Funding: This work was supported by ANID (Anillo ICMD) [Grant ACT210005] and the Center for Mathematical Modeling [Grant FB210005].