在线学习动态拍卖机制，适应未知市场变化。
Online Learning for Dynamic Vickrey-Clarke-Groves Mechanism in Unknown Environments
- 将VCG机制扩展至序列拍卖，保持效率与诚实性。
- 通过强化学习在线估计市场状态，实现近似最优机制。
- 适用于动态市场中需长期优化的拍卖设计场景。
我们研究在未知环境下序列拍卖的在线动态机制设计问题，其中市场状况和投标者价值随卖家与投标者交互过程动态变化。将序列拍卖建模为无限时域平均奖励马尔可夫决策过程（MDP）。每轮中，卖家决定分配方案并设定每位投标者的支付，每位投标者获得私有收益并提交密封报价。状态代表底层市场，根据未知转移核及卖家分配策略演化，无周期重置。首先将维克里-克拉克-格罗夫斯（VCG）机制扩展至序列拍卖，得到保持效率、诚实性和个体理性性质的动态版本。随后聚焦在线设置，开发一种强化学习算法，使卖家学习底层MDP并实施接近动态VCG机制的机制。证明所学机制近似满足效率、诚实性和个体理性，并在多种悔悟定义下保证性能。
原文摘要 · Abstract (English)
We consider the problem of online dynamic mechanism design for sequential auctions in unknown environments, where the underlying market and, thus, the bidders' values vary over time as interactions between the seller and the bidders progress. We model the sequential auctions as an infinite-horizon average-reward Markov decision process (MDP). In each round, the seller determines an allocation and sets a payment for each bidder, while each bidder receives a private reward and submits a sealed bid to the seller. The state, which represents the underlying market, evolves according to an unknown transition kernel and the seller's allocation policy without episodic resets. We first extend the Vickrey-Clarke-Groves (VCG) mechanism to sequential auctions, thereby obtaining a dynamic counterpart that preserves the desired properties: efficiency, truthfulness, and individual rationality. We then focus on the online setting and develop a reinforcement learning algorithm for the seller to learn the underlying MDP and implement a mechanism that closely resembles the dynamic VCG mechanism. We show that the learned mechanism approximately satisfies efficiency, truthfulness, and individual rationality and achieves guaranteed performance in terms of various notions of regret.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。