学习型竞标者下,随机拍卖比固定拍卖更能提升长期收益。
Randomized Truthful Auctions with Learning Agents
- 用随机拍卖机制应对学习型竞标者,突破传统固定拍卖局限。
- 当交互次数足够多时,随机拍卖的收益严格优于带保留价的第二价格拍卖。
- 适合研究机制设计与学习博弈的学者,尤其关注非理性行为场景。
我们研究代理使用无后悔学习算法参与重复拍卖的场景。已有研究表明,即使在第二价格拍卖中,使用无后悔出价算法的竞标者,无论交互次数T多大,次高报价者也不一定收敛到真实出价。本文首先证明该现象对一般确定性真价拍卖同样成立,并发现竞标者学习率的比率会定性影响其收敛行为。接着,在收益最大化问题上,经典理论表明完全理性的竞标者下,通过带保留价的第二价格拍卖可实现最优收益;但在本设定中,当T足够大时,随机拍卖能提供严格更优的收益保障。最后,我们研究非渐近情形下的收益最大化问题,定义了拍卖人悔恨度(auctioneer regret),比较实际收益与基于真实出价的第二价格拍卖收益。若拍卖人必须全程使用同一拍卖机制,我们给出几乎紧的悔恨界$\widetilde Θ(T^{3/4})$;若拍卖人可动态更换机制但不依赖出价,悔恨界为几乎紧的$\widetilde Θ(\sqrt{T})$。
原文摘要 · Abstract (English)
We study a setting where agents use no-regret learning algorithms to participate in repeated auctions. \citet{kolumbus2022auctions} showed, rather surprisingly, that when bidders participate in second-price auctions using no-regret bidding algorithms, no matter how large the number of interactions $T$ is, the runner-up bidder may not converge to bidding truthfully. Our first result shows that this holds for \emph{general deterministic} truthful auctions. We also show that the ratio of the learning rates of the bidders can \emph{qualitatively} affect the convergence of the bidders. Next, we consider the problem of revenue maximization in this environment. In the setting with fully rational bidders, \citet{myerson1981optimal} showed that revenue can be maximized by using a second-price auction with reserves.We show that, in stark contrast, in our setting with learning bidders, \emph{randomized} auctions can have strictly better revenue guarantees than second-price auctions with reserves, when $T$ is large enough. Finally, we study revenue maximization in the non-asymptotic regime. We define a notion of {\em auctioneer regret} comparing the revenue generated to the revenue of a second price auction with truthful bids. When the auctioneer has to use the same auction throughout the interaction, we show an (almost) tight regret bound of $\smash{\widetilde Θ(T^{3/4})}.$ If the auctioneer can change auctions during the interaction, but in a way that is oblivious to the bids, we show an (almost) tight bound of $\smash{\widetilde Θ(\sqrt{T})}.$
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。