7.6.1 动态定价问题
动态定价问题是重复拍卖中的最重要的研究问题。在重复拍卖中，拍卖方为了能够提高收益，往往会设计一个保留价，这就涉及到了动 态定价的问题。作为收入管理的一个组成部分，动态定价问题在各行 各业都有广泛的应用。对动态定价的研究横跨统计学、机器学习、经 济学和运筹学等领域。对于动态定价的研究成为了人工智能与博弈论 交叉学科研究的前沿问题。
经典的定价模型中关注的是通过在重复拍卖中设定保留价格使得卖家在一段时间内实现收益最大化。关于经典定价模型的研究最早可以追溯到R. Kleinberg 和 T. Leighton 的工作[1] 。在这篇文章中，作者研究了一个基本市场情景的定价算法。假设有一个卖方，他有无限数量的同样物品，他要与连续的 n 个买方进行交易，每个买方只能购买一件物品。卖方向特定的买方提出的价格可能会受之前交易结果的影响，但每个买方只能参与一次交易。一个有趣的问题是，相比于卖方事先知道买方估值的情况，不知情的卖方预计能够获得多少利润。
在本文中，作者根据买家对物品估值的建模方式分三种情况讨论了这个问题。首先是所有买家的估价都等于单一价格𝑝 ∈ [0,1]，作者证明了有一种确定性定价策略能达到遗憾值𝑂(log log 𝑛)，没有一种定价策略能达到遗憾值为𝑜(log log 𝑛)。第二种情况是买家的估值是来自 [0, 1]上固定概率分布的独立随机样本。作者证明了在保证函数
𝑓(𝑥) = 𝑥 ⋅ Pr(𝑏𝑢𝑦𝑒𝑟’𝑠 𝑣𝑎𝑙𝑢𝑎𝑡𝑖𝑜𝑛 𝑖𝑠 ≥ 𝑥)在[0, 1]的内部有唯一的全局最大值𝑥∗且𝑓′′(𝑥∗) < 0的条件下，存在一种定价策略可以实现事后遗憾𝑂(√𝑛 𝑙𝑜𝑔 𝑛)。最后一种情况是，买方的估值没有任何假设。
他们可能由对手选择，而对手对卖方定价策略的随机选择一无所知。
2 1
在这种情况下，有定价策略能实现𝑂 (𝑛3( 𝑙𝑜𝑔 𝑛 )3)的遗憾，但没有
2
定价策略能实现𝑜 (𝑛3)的遗憾。Josef Broder 和 Paat Rusmevichientong
进一步考虑了这样一个问题[2] ：如何通过动态定价的方法来估计买方对物品的需求水平。对零售商来说，一个物品在每个价格水平下的需求量对最大化预期收入非常关键。如果零售商无法获知该物品在每个价格水平下的需求量，那么他们很有可能无法做出正确的决策。而在实际操作中，事实也常常如此。为了解决这个问题，作者研究了尝试使用动态定价策略，即通过调整商品价格来获得需求曲线信息，然后利用这些信息提供接近最优的销售价格。作者提出了一个通用的参数选择模型，用于描述买方依次到来时的决策行为以及卖方如何定价以最小化遗憾。在这个模型下，作者分别给出了卖家策略所能达到的遗憾值的上下界。作者利用“无信息价格”的存在，在减少需求曲线参数的不确定性和利用最佳猜测价格之间进行权衡，从而得出任意定价策略的遗憾值为Ω(√𝑇)。作者还提出了一种基于最大似然估计的定价策略，它在所有问题实例中的遗憾值都是𝑂(√𝑇)。Kareem Amin, Afshin Rostamizadeh 和Umar Syed 把买家看成一个策略性的博弈参与者[3] 在一个只有一个买家和单个物品的重复拍卖中，买家会采取策略性的行为来引诱卖家降低出价，以最大化其长期盈余。在重复的情
况下，许多拍卖的真实性很难得到保证，因此卖家需要设计算法来尽可能提高自己的收益。为此，作者提出了一个卖方算法，该算法从最高价格 1 开始，每当买家拒绝接受价格时，将价格降低𝛽倍，否则保持不变。在考虑买家对未来盈余的贴现条件下，即买家倾向于尽早获得物品的情况下，该卖方算法是无战略遗憾的。作者还给出了战略遗憾的下限，该下限随着买方折扣的减弱而增大，并特别表明，如果不存在折扣， 任何卖方算法都能够实现线性战略遗憾。 Cesa-Bianci，Cesari 和 Perchet 研究了同样的动态定价问题[5] ，其中买家对产品的估值只有有限个未知点，通过比较估值与卖家设计的保留价格来确定是否购买商品。利用推广的 UCB 算法，作者得到了𝑂(𝐾𝑙𝑜𝑔𝑇)阶的遗憾。
上述研究都是考虑的单物品以及单个买家的重复拍卖场景，在这场景中，卖家只需要设置一个价格，买家根据自己对物品的估值来决定是否购买物品。 Nicolò Cesa-Bianchi, Claudio Gentile 和 Yishay Mansour 进一步研究了在带有保留价的重复二价拍卖中的最大化收益算法[4] 。在这个场景中，待售物品只有一个，但是，在这个拍卖中有多个买家。在一个 T 轮的重复拍卖中，卖家在每一轮都会收集𝑚(𝑚 ≥ 2)个独立同分布的报价，这些报价的累积分布函数 F 是任意且未知的。然后，卖家根据带有保留价的二价拍卖的规则来分配物品并收取来自买家的支付。在这个研究中，作者通过买家报价的顺序统计量来构造卖家的保留价并提出了一个两阶段的保留价设置算法。在第一阶段，算法将保留价设为 0 以获得对买家报价的分布的一个估计。在第二阶段，作者设置了一个迭代算法，根据第一阶段获得的对买家报价的分布的估计来计算能获得最大收益的保留价。最后，作者证明了该算法具有较高的计算效率，并且在𝑇次
拍卖序列中取得了𝑂̃(√𝑇)的遗憾。不过， 这个模型并没有考虑
策略性的买家， Alexey Drutsa 则考虑了在策略性买家参与的情况下，重复二价拍卖的保留价设置策略[6] 。在这项研究中，作者关注了卖方通过使用第二价格拍卖与 M 个策略投标人（ 也被称为买家）进行反复互动的情景。在每一轮中，买家参与这个博弈，他们对某个物品（ 比如广告位）持有一个固定的私人估值，并根据他们对其他竞标者的行为，试图最大化他们预期的未来贴现盈余。作者提出了一种新的算法，该算法可以应用于具有𝑂(𝐿𝑜𝑔𝑙𝑜𝑔𝑇)上界的策略买家。
在这之后， Zhe Feng, Sébastien Lahaie, Jon Schneider 和 Jinchao Ye 研究了在重复一价拍卖中的保留价优化问题[7] 。由于第二价格拍卖中优良性质，诚实报价总是出价人的占优策略。所以，卖家可以通过设计算法来获得投标人的价值分布。但是，由于在一价拍卖中，卖家可以通过策略性的行为来让自己获益。所以，卖家想要估计买家对物品的估值分布就不那么容易了。因此，这个时候，就需要用到保留价。通过设定保留价来了解竞标者对保留价的估值。在这篇工作中，作者提出了一种基于梯度的算法来自适应地更新和优化保留价格，并通过理论分析和实验证明了该算法的优良性。