arXiv:2507.09473cs.GTcs.LG2025-07中稿 · NeurIPS

提出新框架,让资源分配既高效又防作弊。

Efficiency, Feasibility, and Incentive-Awareness in Constrained Online Resource Allocation

  • 设计激励感知的优化机制,抑制用户谎报
  • 实现近似最优社会福利,约束满足率高
  • 适合长期资源分配场景,如广告投放

研究在长期约束下,对战略型参与者动态分配不可分资源的问题。目标是最大化社会福利、满足多重约束,并诱导接近诚实的报告。发现传统原始-对偶方法在此场景脆弱:参与者易通过虚报扭曲对偶变量,牺牲整体效率换取个人收益。为此提出激励感知原始-对偶(IAPD)框架。在原始侧,结合VCG支付消除即时谎报收益,采用周期性懒更新与随机探索使未来潜在收益被即时惩罚覆盖;在对偶侧,为克服懒更新带来的学习障碍(称作“激励代价”),设计新型乐观在线学习算法O-FTRL-FP,利用固定点预言机解决对偶变量与分配间的循环依赖。最终机制达到$ ilde{/mathcal O}(\ oot T)$的社会福利后悔值,严格满足所有长期约束,并诱导近诚实均衡。可自然推广至多单位多需求分配问题。该$ ilde{/mathcal O}(\ oot T)$后悔率近乎逼近非策略情形的$Ω(\ oot T)$下界,表明激励感知几乎无需付出额外代价。

原文摘要 · Abstract (English)

We study the dynamic allocation of indivisible resources to strategic agents under long-term constraints, where the planner aims to maximize social welfare, satisfy multiple constraints, and elicit near-truthful reports. We find standard primal-dual methods fragile in this setting: agents easily manipulate their reports to distort dual variables, sacrificing social efficiency for individual utility. To address this, we propose the Incentive-Aware Primal-Dual (IAPD) framework. On the primal side, we integrate three components to suppress manipulation: a VCG-based payment neutralizes immediate misreporting benefits, while epoch-based lazy updates and random exploration together ensure potential future gains are outweighed by immediate penalties. On the dual side, to overcome a learning barrier due to lazy updates -- which we call the "price of incentives" -- we design a novel optimistic online learning algorithm, O-FTRL-FP. It utilizes a fixed-point oracle to resolve the circular dependency between optimistic dual variables and the resulting allocations. Ultimately, our mechanism attains $\tilde{\mathcal O}(\sqrt T)$ social welfare regret, satisfies all long-term constraints, and induces a near-truthful equilibrium. It also smoothly generalizes to multi-unit multi-demand allocation problems. Notably, this $\tilde{\mathcal O}(\sqrt T)$ regret near-matches the non-strategic $Ω(\sqrt T)$ lower bound, demonstrating that incentive-awareness can be accommodated at nearly no cost.

资源分配在线学习激励机制博弈论

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。