要利用战略承诺,这是玩游戏的有用策略,领导者必须学习有关追随者的回报功能的足够信息。但是,这使追随者有机会提供虚假信息并影响最终的游戏结果。通过对学习领导者的精心虚假的回报功能,与他的真实行为相比,追随者可能会引起更多使他受益的结果。我们通过广泛的游戏中这种战略行为研究追随者的最佳操纵。追随者的不同态度被考虑在内。乐观的追随者在所有游戏成果中最大限度地发挥了他的真实用途,这些效用可以由某些回报功能引起。悲观的追随者只考虑了导致独特游戏结果的错误报告的回报功能。对于本文中考虑的所有设置,我们表征了可以成功诱导的所有可能的游戏结果。我们证明,追随者可以找到误会其私人收益信息的最佳方法是多项式时间的。我们的工作完全解决了该追随者在广泛的游戏树上的最佳操纵问题。
translated by 谷歌翻译
Function approximation (FA) has been a critical component in solving large zero-sum games. Yet, little attention has been given towards FA in solving \textit{general-sum} extensive-form games, despite them being widely regarded as being computationally more challenging than their fully competitive or cooperative counterparts. A key challenge is that for many equilibria in general-sum games, no simple analogue to the state value function used in Markov Decision Processes and zero-sum games exists. In this paper, we propose learning the \textit{Enforceable Payoff Frontier} (EPF) -- a generalization of the state value function for general-sum games. We approximate the optimal \textit{Stackelberg extensive-form correlated equilibrium} by representing EPFs with neural networks and training them by using appropriate backup operations and loss functions. This is the first method that applies FA to the Stackelberg setting, allowing us to scale to much larger games while still enjoying performance guarantees based on FA error. Additionally, our proposed method guarantees incentive compatibility and is easy to evaluate without having to depend on self-play or approximate best-response oracles.
translated by 谷歌翻译
\ emph {ex ante}相关性正在成为\ emph {顺序对抗团队游戏}的主流方法,其中一组球员在零和游戏中面对另一支球队。众所周知,团队成员的不对称信息同时使平衡计算\ textsf {apx} - hard和团队的策略在游戏树上不可直接表示。后一个问题阻止采用成功的2个玩家零和游戏的成功工具,例如,\ emph {e.g。},抽象,无regret学习和子游戏求解。这项工作表明,我们可以通过弥合顺序对抗团队游戏和2次玩家游戏之间的差距来恢复这种弱点。特别是,我们提出了一种新的,合适的游戏表示形式,我们称之为\ emph {Team-Public-information},其中团队被代表为单个协调员,他只知道整个团队的共同信息,并向每个成员开出一个行动对于任何可能的私人状态。最终的表示形式是高度\ emph {可解释},是一棵2播放器树,在设计抽象时,团队的策略具有直接解释和更具表现力的行为,并且具有更高的表现力。此外,我们证明了代表性的回报等效性,并提供了直接从广泛形式开始的技术,从而在没有信息损失的情况下产生了更紧凑的表示形式。最后,我们在应用于标准测试床上的技术时对技术进行了实验评估,并将它们的性能与当前的最新状态进行了比较。
translated by 谷歌翻译
Information asymmetry in games enables players with the information advantage to manipulate others' beliefs by strategically revealing information to other players. This work considers a double-sided information asymmetry in a Bayesian Stackelberg game, where the leader's realized action, sampled from the mixed strategy commitment, is hidden from the follower. In contrast, the follower holds private information about his payoff. Given asymmetric information on both sides, an important question arises: \emph{Does the leader's information advantage outweigh the follower's?} We answer this question affirmatively in this work, where we demonstrate that by adequately designing a signaling device that reveals partial information regarding the leader's realized action to the follower, the leader can achieve a higher expected utility than that without signaling. Moreover, unlike previous works on the Bayesian Stackelberg game where mathematical programming tools are utilized, we interpret the leader's commitment as a probability measure over the belief space. Such a probabilistic language greatly simplifies the analysis and allows an indirect signaling scheme, leading to a geometric characterization of the equilibrium under the proposed game model.
translated by 谷歌翻译
While Nash equilibrium has emerged as the central game-theoretic solution concept, many important games contain several Nash equilibria and we must determine how to select between them in order to create real strategic agents. Several Nash equilibrium refinement concepts have been proposed and studied for sequential imperfect-information games, the most prominent being trembling-hand perfect equilibrium, quasi-perfect equilibrium, and recently one-sided quasi-perfect equilibrium. These concepts are robust to certain arbitrarily small mistakes, and are guaranteed to always exist; however, we argue that neither of these is the correct concept for developing strong agents in sequential games of imperfect information. We define a new equilibrium refinement concept for extensive-form games called observable perfect equilibrium in which the solution is robust over trembles in publicly-observable action probabilities (not necessarily over all action probabilities that may not be observable by opposing players). Observable perfect equilibrium correctly captures the assumption that the opponent is playing as rationally as possible given mistakes that have been observed (while previous solution concepts do not). We prove that observable perfect equilibrium is always guaranteed to exist, and demonstrate that it leads to a different solution than the prior extensive-form refinements in no-limit poker. We expect observable perfect equilibrium to be a useful equilibrium refinement concept for modeling many important imperfect-information games of interest in artificial intelligence.
translated by 谷歌翻译
大多数算法研究到目前为止,多智能经纪信息设计的研究专注于没有代理商外部性的限制情况;一些例外调查了真正的战略游戏,如零和游戏和二价格拍卖,但只关注最佳的公共信令。本文启动了\ emph {public}和\ emph {privy}信号传导的算法信息设计,其中of基本的外部性,即单例拥塞游戏,在今天的数字经济中的应用范围广,机器调度,路由,对于公共和私人信令等,我们表明,当资源数量是常数时,可以有效地计算最佳信息设计。为了我们的知识,这是一系列高效的\ EMPH {精确}算法,用于在简明地代表的许多玩家游戏中的信息设计。我们的结果符合新颖的技术,如开发某些“减少形式”,以便在公共信令中紧凑地表征均衡或代表私人信令中的球员边际信仰。当有许多资源时,我们会显示计算难扰性结果。为了克服多个均衡问题,这里我们介绍了均衡 - \ EMPH {忽视}硬度的新概念,这条规定了计算良好信令方案的任何可能性,而不管均衡选择规则如何。
translated by 谷歌翻译
尽管自1970年代以来就已经知道,普通付款游戏中的全球最佳策略概况是纳什均衡,但全球最优性是严格的要求,它限制了结果的适用性。在这项工作中,我们表明任何本地最佳的对称策略概况也是(全局)NASH平衡。此外,我们证明了这一结果对通用收益和本地最佳的扰动是可靠的。应用于机器学习,我们的结果为任何梯度方法提供了全球保证,该方法在对称策略空间中找到了局部最佳。尽管该结果表明单方面偏差的稳定性,但我们仍然确定了广泛的游戏类别,这些游戏混合了当地的最佳选择,在不对称的偏差下是不稳定的。我们通过在一系列对称游戏中运行学习算法来分析不稳定性的普遍性,并通过讨论结果对多代理RL,合作逆RL和分散的POMDP的适用性来得出结论。
translated by 谷歌翻译
数字推荐系统(例如Spotify和Netflix)不仅会影响消费者的行为,还会影响生产者的激励措施:生产商试图提供系统推荐的内容。但是将产生什么内容?在本文中,我们研究了内容推荐系统中的供应方均衡。我们将用户和内容建模为$ d $维矢量,并推荐与每个用户具有最高点产品的内容。我们模型的主要特征是生产者的决策空间高维,用户群是异质的。这引起了平衡的新定性现象:首先是流派的形成,生产者专门竞争用户的亚集。使用二元参数,我们得出了这种专业化的必要条件。其次,我们表明生产商可以在平衡下实现正利润,这在完美的竞争中通常是不可能的。我们得出了足够的条件,并证明它与内容的专业化密切相关。在这两种结果中,用户的几何形状与生产者成本的结构之间的相互作用都会影响供应方均衡的结构。从概念上讲,我们的工作是研究推荐系统如何塑造生产者之间供应方竞争的起点。
translated by 谷歌翻译
我们考虑战略设置,其中几个用户在重复的在线互动中聘用,辅助最小化的代理商代表他们反复发挥“游戏”。我们研究了代理人的重复游戏的动态和平均结果,并将其视为诱导用户之间的元游戏。我们的主要焦点是用户可以在此元游戏中从“操纵”他们自己的代理商中可以受益于他们自己的代理商。我们正式定义了普通游戏的这种“用户代理元荟萃游戏”模型,讨论了自动化代理动态的不同概念下的属性,并分析了2x2游戏中用户的均衡,其中动态收敛到a单均衡。
translated by 谷歌翻译
游戏理论到目前为止在各个领域都发现了许多应用,包括经济学,工业,法学和人工智能,每个玩家都只关心自己对非合作或合作方式的兴趣,但对其他玩家没有明显的恶意。但是,在许多实际应用中,例如扑克,国际象棋,逃避者追求,毒品拦截,海岸警卫队,网络安全和国防,球员通常都具有对抗性立场,也就是说,每个球员的自私行动不可避免地或故意造成损失或对其他球员造成严重破坏。沿着这条线,本文对在对抗性游戏中广泛使用的三种主要游戏模型(即零和零正常形式和广泛形式游戏,stackelberg(Security)游戏,零和差异游戏)提供了系统的调查。观点,包括游戏模型的基本知识,(近似)平衡概念,问题分类,研究前沿,(近似)最佳策略寻求技术,普遍的算法和实际应用。最后,还讨论了有关对抗性游戏的有希望的未来研究方向。
translated by 谷歌翻译
我们研究了非参数在线回归中的快速收敛速度,即遗憾的是关于具有有界复杂度的任意函数类来定义后悔。我们的贡献是两倍: - 在绝对损失中的非参数网上回归的可实现设置中,我们提出了一种随机适当的学习算法,该算法在假设类的顺序脂肪破碎尺寸方面获得了近乎最佳的错误。在与一类Littlestone维度$ D $的在线分类中,我们的绑定减少到$ d \ cdot {\ rm poly} \ log t $。这结果回答了一个问题,以及适当的学习者是否可以实现近乎最佳错误的界限;以前,即使在线分类,绑定的最知名错误也是$ \ tilde o(\ sqrt {dt})$。此外,对于真实值(回归)设置,在这项工作之前,界定的最佳错误甚至没有以不正当的学习者所知。 - 使用上述结果,我们展示了Littlestone维度$ D $的一般总和二进制游戏的独立学习算法,每个玩家达到后悔$ \ tilde o(d ^ {3/4} \ cdot t ^ {1 / 4})$。该结果概括了Syrgkanis等人的类似结果。 (2015)谁表明,在有限的游戏中,最佳遗憾可以从普通的o(\ sqrt {t})$中的$ o(\ sqrt {t})为游戏设置中的$ o(t ^ {1/4})$。要建立上述结果,我们介绍了几种新技术,包括:分层聚合规则,以实现对实际类别的最佳错误,Hanneke等人的适当在线可实现学习者的多尺度扩展。 (2021),一种方法来表明这种非参数学习算法的输出是稳定的,并且证明Minimax定理在所有在线学习游戏中保持。
translated by 谷歌翻译
经济学和政策等现实世界应用程序往往涉及解决多智能运动游戏与两个独特的特点:(1)代理人本质上是不对称的,并分成领导和追随者; (2)代理商有不同的奖励功能,因此游戏是普通的。该领域的大多数现有结果侧重于对称解决方案概念(例如纳什均衡)或零和游戏。它仍然开放了如何学习Stackelberg均衡 - 从嘈杂的样本有效地纳入均衡的不对称模拟 - 纳入均衡。本文启动了对Birtit反馈设置中Stackelberg均衡的样本高效学习的理论研究,我们只观察奖励的噪音。我们考虑三个代表双人普通和游戏:强盗游戏,强盗加固学习(Bandit-RL)游戏和线性匪徒游戏。在所有这些游戏中,我们使用有义的许多噪声样本来确定Stackelberg均衡和其估计版本的确切值之间的基本差距,无论算法如何,都无法封闭信息。然后,我们在对上面识别的差距最佳的基础上的数据高效学习的样本高效学习的敏锐积极结果,在依赖于依赖性的差距,误差容限和动作空间的大小,匹配下限。总体而言,我们的结果在嘈杂的强盗反馈下学习Stackelberg均衡的独特挑战,我们希望能够在未来的研究中阐明这一主题。
translated by 谷歌翻译
在本说明中,我研究了制度和游戏理论假设,这些假设将阻止AI*表示的“超人级”弧形通用智能的出现。这些假设是(i)“心灵自由”,(ii)开源“访问” AI*,以及(iii)与AI*竞争的代表人类代理人的合理性。我证明,在这三个假设下,AI*不可能存在。该结果引起了公共政策的两个即时建议。首先,“克隆”以数字方式受到严格调节,并应禁止假设的脑部进入大脑。其次,如果不公开,应广泛进行AI*研究。
translated by 谷歌翻译
我们研究了一个多领导的单追随者拥塞游戏,多个用户(领导者)选择一个资源中的一个资源,并且在观察实现的负载后,对手(单追随器)攻击最大负载的资源,导致额外的资源领导者的成本。对于领导者之间产生的战略游戏,我们表明纯净的纳什均衡可能无法存在,因此,我们考虑了近似均衡。作为我们的第一主要结果,我们展示了$ k $的存在,可以始终保证$ k $的均衡,其中$ k \约1.1974 $是立方多项式方程的独特解决方案。为此,我们提供了一种多项式时间组合算法,其计算$ k $的均衡。因子$ k $很紧,这意味着有一个实例不承认任何$ \ alpha <k $的$ \ alpha $。因此,$ \ alpha = k $是$ \ alpha $的最小可能值,使得可以保证$ \ alpha $-ruckimate均衡的存在,以查找考虑游戏的任何实例。其次,我们专注于给定固定实例的近似均衡。我们展示了如何有效地计算最佳近似平衡,即在给定实例的所有$ \ alpha $中具有最小的$ \ alpha $。
translated by 谷歌翻译
事后观察合理性是一种玩一般游戏的方法,该游戏规定了针对一组偏差的单个代理的无重格学习动态,并进一步描述了具有介导的平衡的多个代理商之间的共同理性行为。为了在依次的决策设置中发展事后理性学习,我们将行为偏差形式化为一般偏差,尊重广泛形式游戏的结构。将时间选择的概念整合到反事实遗憾的最小化(CFR)中,我们介绍了广泛的遗憾最小化(EFR)算法,该算法对于任何给定的行为偏差都具有与集合的复杂性紧密相关的计算相关的行为偏差。我们识别行为偏差子集,部分序列偏差类型,这些类型还包含先前研究的类型并导致长度中等的游戏中有效的EFR实例。此外,我们对基准游戏中不同偏差类型实例化的EFR进行了彻底的经验分析,我们发现更强大的类型通常会引起更好的性能。
translated by 谷歌翻译
在正常游戏中,简单,未耦合的无regret动态与相关的平衡是多代理系统理论的著名结果。具体而言,已知20多年来,当所有玩家都试图在重复的正常游戏中最大程度地减少其内部遗憾时,游戏的经验频率会收敛于正常形式相关的平衡。广泛的形式(即树形)游戏通过对顺序和同时移动以及私人信息进行建模,从而推广正常形式的游戏。由于游戏中部分信息的顺序性质和存在,因此广泛的形式相关性具有与正常形式的属性明显不同,而正常形式的相关性仍然是开放的研究方向。已经提出了广泛的形式相关平衡(EFCE)作为自然的广泛形式与正常形式相关平衡。但是,目前尚不清楚EFCE是否是由于未耦合的代理动力学而出现的。在本文中,我们给出了第一个未耦合的无regret动态,该动态将$ n $ n $ - 玩家的General-sum大型游戏收敛于EFCE,并带有完美的回忆。首先,我们在广泛的游戏中介绍了触发遗憾的概念,这扩展了正常游戏中的内部遗憾。当每个玩家的触发后悔低时,游戏的经验频率接近EFCE。然后,我们给出有效的无触发式算法。我们的算法在每个决策点在每个决策点上都会从每个决策点构建播放器的全球策略,从而将触发遗憾分解为本地子问题。
translated by 谷歌翻译
最近的一项工作已经建立了未耦合的学习动力学,以至于当所有玩家在游戏中使用所有玩家时,每个玩家的\ emph {sorex} $ t $ recretitions在$ t $中增长了polygarithmarithm,这是$ t $的指数改进,比指数级的改进,比传统的保证在无缩写框架。但是,到目前为止,这些结果仅限于具有结构化策略空间的某些类别的游戏,例如正常形式和广泛形式的游戏。关于$ o(\ text {polylog} t)$遗憾界限是否可以为一般凸和紧凑型策略集获得的问题 - 这在经济学和多种系统中的许多基本模型中都发生 - 同时保留有效的策略更新是一种重要的问题。在本文中,我们通过建立$ o(\ log t)$ player后悔的第一个未耦合学习算法来回答这一点凸和紧凑的策略集。我们的学习动力基于对适当的\ emph {升起}空间的乐观跟随领导者的实例化,使用\ emph {self-condcordant正规器},这是特殊的,这不是可行区域的障碍。此外,我们的学习动力是可以有效地实现的,如果可以访问登录策略的近端甲骨文,从而导致$ o(\ log \ log \ log t)$ ter-ter-ter-tir-tir-tir-tir-tir-tir-tir-tir-tir-tir-tir-tir-tirceptimity;当仅假设仅对\ emph {Linear}优化Oracle访问时,我们还会给出扩展。最后,我们调整动力学以保证对抗性制度中的$ O(\ sqrt {t})$遗憾。即使在适用先前结果的特殊情况下,我们的算法也会改善最先进的遗憾界限,无论是依赖迭代次数还是对策略集的维度的依赖。
translated by 谷歌翻译
在本文中,我们建立了高效且取消耦合的学习动力学,因此,当由所有玩家在多人游戏中使用Perfect-Recall Inderfect Interfect Inderfection Formfortation Gartensive Games时,每个玩家的\ emph {触发后悔}会成长为$ o(\ log t t t t t t )$ $ t $重复播放。这比$ o(t^{1/4})$的先前最著名的触发regret键呈指数改进,并解决了Bai等人最近的一个开放问题。 (2022)。作为直接的结果,我们保证以$ \ frac {\ log log t} {t} $的接近速率以接近{粗相关的平衡}融合。基于先前的工作,我们的构造核心是关于从\ emph {polyenmial genter}衍生的固定点的更一般的结果,这是我们为\ emph {(粗)触发偏差函数建立的属性}。此外,我们的构造利用了凸壳的精制\ textit {遗憾电路},与先验保证不同 - 保留了Syrgkanis等人引入的\ emph {rvu属性}。 (NIPS,2015年);这种观察对基于CFR型遗憾的分解,在学习动态下建立近乎最佳的遗憾具有独立的兴趣。
translated by 谷歌翻译
迄今为止,游戏中的学习研究主要集中在正常形式游戏上。相比之下,我们以广泛的形式游戏(EFG),尤其是在许多代理商远远落后的EFG中对学习的理解,尽管它们与许多现实世界的应用更加接近。我们考虑了网络零和广泛表单游戏的天然类别,该游戏结合了代理收益的全球零和属性,图形游戏的有效表示以及EFG的表达能力。我们检查了这些游戏中乐观梯度上升(OGA)的收敛属性。我们证明,这种在线学习动力学的时间平均值表现出$ O(1/t)$ rate contergence convergence contergence contergence。此外,我们表明,对于某些与游戏有关的常数$ c> 0 $,日常行为也与速率$ o(c^{ - t})$收敛到nash。
translated by 谷歌翻译
We study the problem of training a principal in a multi-agent general-sum game using reinforcement learning (RL). Learning a robust principal policy requires anticipating the worst possible strategic responses of other agents, which is generally NP-hard. However, we show that no-regret dynamics can identify these worst-case responses in poly-time in smooth games. We propose a framework that uses this policy evaluation method for efficiently learning a robust principal policy using RL. This framework can be extended to provide robustness to boundedly rational agents too. Our motivating application is automated mechanism design: we empirically demonstrate our framework learns robust mechanisms in both matrix games and complex spatiotemporal games. In particular, we learn a dynamic tax policy that improves the welfare of a simulated trade-and-barter economy by 15%, even when facing previously unseen boundedly rational RL taxpayers.
translated by 谷歌翻译