To Spend or to Gain: Online Learning in Repeated Karma Auctions

技术摘要：消费还是获益：重复性 Karma 拍卖中的在线学习

问题定义
本文探讨了在利用人工货币（具体为“Karma”）而非货币工具的重复拍卖设定中，学习最优出价策略所面临的挑战。与传统的货币拍卖不同，在这种机制中，人工货币在拍卖语境之外没有任何价值。此外，本文关注的是一类特定的 Karma 机制，其中支付金额会在每个时间步长内重新分配给所有用户。在这种设定下，用户不仅通过赢得资源来消耗 Karma，还通过失去资源（即让出资源）来获得 Karma。这种重新分配创造了一个闭环系统，使得系统中 Karma 的总量随时间保持不变。

核心难点在于，用户必须共同学习货币的价值以及如何最优地使用它。用于预算受限货币拍卖的标准自适应步调控制（adaptive pacing）策略在此并不适用，原因如下：

1. 非诚实性（Non-Truthfulness）： 在失去资源时可能获得 Karma 的机制，产生了促使代理人在二价拍卖中进行非诚实出价以最大化其收益的动机。
2. 预算动态（Budget Dynamics）： 由于总 Karma 的守恒，代理人无法同时耗尽其预算，而这是在货币设定中为了固定步调乘数规模通常会假设的条件。
3. 未知成本（Unknown Cost）： 消耗货币的成本并非预先已知，必须通过在线学习获得。

作者将其建模为一个重复资源分配问题（例如，具有优先车道的早高峰通勤场景），其中 $N$ 个代理人为 $\gamma$ 个优先槽位进行竞价。代理人拥有私有的、随时间变化的估值。该机制使用二价拍卖规则：前 $\gamma$ 名出价者获胜，并支付第 $(\gamma+1)$ 高的出价。该支付金额随后被均匀重新分配，使每位代理人都获得与支付额成比例的收益。

方法论
作者提出了一种自适应 Karma 步调控制（策略 $K$），该策略源自针对 Karma 机制特定约束进行改进的在线对偶梯度上升技术。

1. 松弛原问题（Relaxed Primal Problem）： 作者首先为具有“后验知识”（已知未来估值和竞争出价）的代理人制定了最优成本问题。由于涉及收益的预算约束具有复杂性，作者推导出了最优成本的一个松弛下界。这种松弛允许出现暂时的负余额（前提是时界内预算非负），并简化了收益的依赖关系。
2. 对偶公式（Dual Formulation）： 他们构建了一个拉格朗日对偶问题。一项关键的新颖之处是用一个随时间变化的项取代了（在货币拍卖中常见的）固定目标支出率，该项考虑了预期收益。
3. 算法设计： 提出的策略 $K$ 根据代理人的支出（$z_{i,t}$）与收益（$g_{i,t}$）之间的差异来更新步调乘数 $\mu_{i,t}$。
   • 出价： $b_{i,t} = \min(\Delta v_{i,t} / \mu_{i,t}, k_{i,t})$。
   • 更新： $\mu_{i,t+1} = \mu_{i,t} + \epsilon(z_{i,t} - g_{i,t})$。
   • 投影（Projection）： 与标准货币步调控制中在更新期间将乘数投影到某个范围不同，这里是将投影 $P_{[\underline{\mu}, \overline{\mu}]}$ 应用于出价的分母。这一修改对于防止“消失箱问题”（vanishing box problem）至关重要——在消失箱问题中，恒定的初始预算结合递减的步长会导致乘数无法收敛到初始状态以上的值。
   • 规模固定（Scale Fixing）： 为了解决步调乘数非唯一性的问题（因为在零和收益系统中，将所有代理人的乘数按常数缩放会保持均衡），作者依赖于跨代理人的乘数总和的守恒。通过将投影移动到出价端，该更新规则保留了乘数之和 $\sum \mu_{i,t}$，从而将均衡锚定在初始乘数剖面（initial multiplier profile）上。

核心贡献
本文提供了一个针对带有再分配机制的 Karma 拍卖进行自适应学习的理论框架，并确立了三个主要结果：

1. 渐近最优性（单代理人）： 对于在静态分布的竞争出价中进行竞价的单个代理人，自适应 Karma 步调控制策略是渐近最优的。其平均预期遗憾（average expected regret）收敛到具有后验知识的最优成本的一个 $O(\hat{\epsilon})$ 邻域内，其中 $\hat{\epsilon}$ 代表“残余收益”（即价格设定者的出价与次高出价之间的预期差）。随着代理人数量的增加，该残余收益趋于递减。
2. 学习动力学收敛（多代理人）： 当所有代理人都采用策略 $K$ 时，学习动力学渐近收敛于唯一的平稳乘数剖面。作者证明了随时间变化的乘数剖面与平稳剖面之间的预期距离收敛于零。
3. 近似纳什均衡（Approximate Nash Equilibrium）： 在存在大量并行拍卖的设定中（即任何两个特定代理人发生交互的概率随之衰减），自适应步调控制策略的剖面构成了一个近似纳什均衡。任何单个代理人都无法通过单方面偏离该策略来渐近地改善其平均成本。

结果与分析
其分析涉及与货币拍卖文献相比的新颖技术步骤：

• 遗憾界限（Regret Bound）： 遗憾界限包含了一个项 $\hat{\epsilon}$，承认在缺乏后验知识的情况下，代理人无法完美地操纵价格设定者的位置。
• 命中时间控制（Hitting Time Control）： 作者引入了一个更严格的“命中时间”概念（即乘数达到其边界或预算耗尽的时间），以确保梯度上升近似的有效性。他们提供了关于估值和出价分布的假设，以保证该命中时间趋向于时界 $T$。
• 消失箱问题（Vanishing Box Problem）： 本文识别并解决了这样一个收敛问题：在标准自适应步调控制中，固定的初始预算和递减的步长会阻碍收敛。通过将投影改为作用于出价而非乘数更新，解决了这一问题。

意义
本文声称其意义在于弥补了非货币机制中理论均衡分析与实际学习之间的差距。虽然以往的研究建立了 Karma 机制中均衡的存在性，但这项工作提供了一种简单的、去中心化的学习规则，使代理人能够在无需中央协调或预知估值分布的情况下达到这些均衡。

作者指出，其研究结果对于那些认为货币工具不公平或不合适的应用场景特别具有相关性，例如食物捐赠分配、课程席位分配或交通拥堵管理。所提出的策略为用户提供了一种在重复交互中高效且公平地表达随时间变化的偏好的机制，确保资源分配给那些具有最高估值的用户，而无需使用金钱。论文最后指出，尽管其分析假设了特定的再分配方案和技术条件（如分布的绝对连续性），但数值实验表明其对离散分布具有鲁棒性，并具有向可变步长扩展的潜力。