arXiv:2409.03129cs.GTcs.LG2024-09被引 4

设计智能补贴可改善多方系统中的自私行为,提升社会效率。

Subsidy design for better social outcomes

  • 通过数据驱动方法学习有效补贴值,避免复杂计算
  • 在重复博弈中可实现无遗憾学习,保障性能提升
  • 适用于成本分摊与设备维护等实际工程场景

在多智能体系统中,理性个体的自利行为会导致系统整体效率低下,表现为高昂的“价格悖论”(Price of Anarchy)。近期研究发现,理性参与者甚至会主动回避免费获取的游戏信息,进一步恶化社会结果。中央规划者可通过注入补贴降低特定成本,从而显著改善系统表现。然而,我们证明在标准复杂性假设下,精确设计能最优提升社会效益的补贴(即最小化价格悖论或阻止信息规避)是计算上困难的问题。正面结果是:我们可在来自同一领域的重复博弈中,通过多项式数量的游戏学习出有保证的良好补贴值。该数据驱动方法避免了对未见游戏求解难问题。此外,在成本矩阵满足弱假设下,最优补贴可实现无遗憾学习。本研究聚焦两类典型博弈:经典的公平成本分摊博弈的贝叶斯扩展,以及具有工程应用的部件维护博弈。

原文摘要 · Abstract (English)

Overcoming the impact of selfish behavior of rational players in multiagent systems is a fundamental problem in game theory. Without any intervention from a central agent, strategic users take actions in order to maximize their personal utility, which can lead to extremely inefficient overall system performance, often indicated by a high Price of Anarchy. Recent work (Lin et al. 2021) investigated and formalized yet another undesirable behavior of rational agents, that of avoiding freely available information about the game for selfish reasons, leading to worse social outcomes. A central planner can significantly mitigate these issues by injecting a subsidy to reduce certain costs associated with the system and obtain net gains in the system performance. Crucially, the planner needs to determine how to allocate this subsidy effectively. We formally show that designing subsidies that perfectly optimize the social good, in terms of minimizing the Price of Anarchy or preventing the information avoidance behavior, is computationally hard under standard complexity theoretic assumptions. On the positive side, we show that we can learn provably good values of subsidy in repeated games coming from the same domain. This data-driven subsidy design approach avoids solving computationally hard problems for unseen games by learning over polynomially many games. We also show that optimal subsidy can be learned with no-regret given an online sequence of games, under mild assumptions on the cost matrix. Our study focuses on two distinct games: a Bayesian extension of the well-studied fair cost-sharing game, and a component maintenance game with engineering applications.

博弈论补贴设计社会效率机器学习

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