Feb, 2024
对首价拍卖中的无懊悔学习者进行策略规划
Strategizing against No-Regret Learners in First-Price Auctions
Aviad Rubinstein, Junyao Zhao
TL;DR我们研究了重复的一阶售价拍卖和一般重复贝叶斯博弈的情况，在这种情况下，一个参与者（学习者）采用了一个无悔学习算法，而另一个参与者（优化者）在了解学习者的算法的情况下，策略化地追求自己的效用最大化。 对于一类被称为基于均值的无悔学习算法，我们证明：（i）在标准（即完全信息）的一阶售价拍卖中，优化者不能获得超过 Stackelberg 效用的效用 -- 这是文献中的标准基准，但是（ii）在贝叶斯一阶售价拍卖中，存在优化者可以获得远高于 Stackelberg 效用的实例。 另一方面，Mansour 等人（2022）证明了一类更复杂的算法，称为无多面体交换后悔算法可以将优化者的效用限制在任意重复贝叶斯博弈（包括贝叶斯一阶售价拍卖）的 Stackelberg 效用上，并提出是否有必要使用无多面体交换后悔算法来限制优化者的效用。对于一般的贝叶斯博弈，在一个合理且必要的条件下，我们证明了无多面体交换后悔算法确实是将优化者的效用限制在 Stackelberg 效用上的必要条件，从而回答了他们的开放性问题。对于贝叶斯一阶售价拍卖，我们通过利用贝叶斯一阶售价拍卖的结构给出了一个简单的改进标准算法来最小化多面体交换后悔。