现代开放和软化系统(如O-RAN电信网络和云计算平台)托管独立开发的应用程序,具有不同的、可能相互冲突的目标。 协调此类应用程序的行为以确保稳定的系统运行带来了重大挑战,特别是当每个应用程序的实用程序只能通过昂贵的黑箱评估访问时。 在本文中,我们考虑了一个集中优化框架,其中系统控制器向代表不同应用程序的多个战略参与者建议联合配置,目标是将其激励机制调整为稳定的结果。 为了模拟这种交互,我们制定了一个Stackelberg游戏,其中中央优化器无法访问分析实用函数,而是必须通过顺序的多保真评估来学习它们。 为了应对这一挑战,我们提出了MF-UCB-PNE,这是一种新颖的多保真贝叶斯优化策略,利用预算受限的采样过程来近似纯纳什均衡(PNE)解决方案。 MF-UCB-PNE系统地平衡了低成本近似的勘探与高保真开采步骤,从而实现与激励兼容配置的高效融合。 我们为查询成本与均衡准确性之间的权衡提供了理论和实证见解,证明了MF-UCB-PNE在有限成本预算下确定有效均衡解决方案的有效性。
随着GenAI平台的增长,他们对来自竞争提供商的内容的依赖,加上对替代数据源的访问,为数据共享决策带来了新的挑战。 在本文中,我们提供了一个内容创建公司与GenAI平台之间的数据共享模型,该平台还可以从第三方专家那里获得内容。 这种交互被建模为Stackelberg游戏:该公司首先决定其专有数据集中有多少与GenAI共享,GenAI随后决定从外部专家那里获得多少额外数据。 他们的公用事业依赖于用户流量,货币转账以及从外部专家获取额外数据的成本。 我们描述了游戏的独特子游戏完美平衡,并揭示了一个令人惊讶的现象:该公司可能愿意支付GenAI分享公司自己的数据,从而导致代价高昂的数据共享均衡。 我们进一步描述了帕累托改善数据价格的一组,并表明只有当公司支付共享数据时才会进行这种改进。 最后,我们研究如何设定价格以优化不同的设计目标,例如促进公司数据共享,专家数据采集或两者的平衡。 我们的研究结果揭示了在GenAI时代塑造数据共享伙伴关系的经济力量,并为寻求设计有效数据交换机制的平台、监管机构和政策制定者提供指导。
经典联合学习(FL)假设客户有有限数量的嘈杂数据,他们自愿参与,并以原则的方式为学习全球,更准确的模型做出贡献。 学习以分布式方式进行,而不与中心共享数据。 然而,这些方法不考虑代理参与和促进过程的激励,因为数据收集和运行分布式算法对客户端来说代价高昂。 最近文献中提出了贡献的合理性问题,并存在一些考虑这一问题的结果。 本文讨论了同时参数学习和激励贡献的问题,这将其与现存文献区分开来。 我们的第一个机制激励每个客户端在纳什均衡下为FL过程做出贡献,并同时学习模型参数。 然而,这种平衡结果可以远离最优,客户贡献他们的完整数据,算法学习最优参数。 我们提出了第二个机制,货币转移是预算平衡的,可以实现完整的数据贡献以及最优的参数学习。 使用真实(联邦)数据集(CIFAR-10,FeMNIST和Twitter)的大规模实验表明,这些算法在实践中收敛得相当快,为所有代理提供了良好的福利保证和更好的模型性能。
我们考虑通过非货币机制反复分配共享资源,其中单个项目必须分配给每轮中的多个代理之一。 我们假设每个代理都有跨轮的项目的 i.i.d. 值,以及附加实用程序。 过去在这个问题上的工作已经提出了机制,代理商可以获得两种保证之一:(i)(近似)贝叶斯-纳什均衡通过基于链接的机制,需要广泛的价值分布知识,以及(ii)简单的分布无关机制,为每个个体代理提供强大的实用保证,这些保证比纳什结果差,但无论其他人的行为如何(包括可能具有勾结行为)都要保持。 最近的工作暗示了同时实现这两个目标的障碍。 然而,我们的工作证明并非如此,通过提出第一个机制,其中每个代理都有自然策略,既是一种贝叶斯 - 纳什平衡,也附带对单个代理公用事业的有力保证。 我们的机制源于在线共享资源分配问题与实施理论之间的惊人联系。 特别是,我们表明,在这种设置中建立稳健的均衡性会降低为显示边界多拓扑的某个特定子集是非空的。 我们通过一个新的联合舒尔-凸率论点来建立这一点。 加强边界取得更有力结论的标准具有独立的技术利益,因为它在其他情况下可能证明是有用的。
我们研究稳定夹具问题,这是经典非双体稳定室友匹配问题的多对多概括。 基于Tan在稳定分区的基础工作,我们将他的结果扩展到这个明显更普遍的设置,并开发了一个丰富的框架,以便在许多到许多上下文中理解稳定结构。 我们的主要贡献,即广义稳定分区(GSP)的概念,不仅表征了这个问题的解决方案空间,而且还充当了推理具有容量限制的普通偏好系统的多功能工具。 我们表明,普惠制可以有效地计算,并提供问题实例的优雅表示,严格描述其偏好结构,并简洁地证明稳定匹配的存在和不存在。 利用与稳定半匹配的连接,我们还建立了农村医院定理的非双体模拟,用于稳定的半匹配和GSP,并将我们的结果与最近关于近可行匹配的工作联系起来,为这个问题提供了更简单的算法和更严格的分析。 我们的工作还解决了寻找最佳稳定半匹配和普惠制的计算挑战,为各种目标提出了灵活的整数线性编程模型。 除了理论见解之外,我们还对随机稳定夹具实例进行了第一次实证分析,发现了令人惊讶的结果,例如容量函数对可溶解性可能性的影响。 我们的工作不仅统一并扩展了关于非双体稳定匹配中稳定性的经典和最近的观点,而且还为推进稳定匹配及其应用的研究建立了新的工具,技术和方向。
我们研究稳定夹具问题,这是经典非双体稳定室友匹配问题的多对多概括。 基于Tan在稳定分区的基础工作,我们将他的结果扩展到这个明显更普遍的设置,并开发了一个丰富的框架,以便在许多到许多上下文中理解稳定结构。 我们的主要贡献,即广义稳定分区(GSP)的概念,不仅表征了这个问题的解决方案空间,而且还充当了推理具有容量限制的普通偏好系统的多功能工具。 我们表明,普惠制可以有效地计算,并提供问题实例的优雅表示,严格描述其偏好结构,并简洁地证明稳定匹配的存在和不存在。 利用与稳定半匹配的连接,我们还建立了农村医院定理的非双体模拟,用于稳定的半匹配和GSP,并将我们的结果与最近关于近可行匹配的工作联系起来,为这个问题提供了更简单的算法和更严格的分析。 我们的工作还解决了寻找最佳稳定半匹配和普惠制的计算挑战,为各种目标提出了灵活的整数线性编程模型。 除了理论见解之外,我们还对随机稳定夹具实例进行了第一次实证分析,发现了令人惊讶的结果,例如容量函数对可溶解性可能性的影响。 我们的工作不仅统一并扩展了关于非双体稳定匹配中稳定性的经典和最近的观点,而且还为推进稳定匹配及其应用的研究建立了新的工具,技术和方向。
演员在演员-批评家-批评家(AC)强化学习中的依赖意味着AC可以被描述为双级优化(BLO)问题,也称为Stackelberg游戏。 这种表征激发了对香草AC算法的两次修改。 首先,应该嵌套批评者的更新,以学习对演员政策的最佳回应。 其次,演员应该根据考虑到批评者行为变化的超梯度来更新。 计算这种超梯度涉及寻找反向Hessian矢量产品,这一过程可能在数值上不稳定。 因此,我们提出了一种新的算法,即使用Nyström Hypergradients(BLPO)进行Bilevel策略优化,该算法使用嵌套来解释BLO的嵌套结构,并利用Nyström方法计算超梯度。 从理论上讲,我们证明BLPO收敛到(一个满足必要条件的点)一个局部强Stackelberg平衡在多项式时间与高概率,假设一个线性参数化的批评者的目标。 从经验上讲,我们证明BLPO在各种离散和连续控制任务上的表现与PPO相同或更好。
Schulze方法是一种在实践中广泛使用的投票规则,具有许多积极的公理性质。 虽然它在多项式时间是可以计算的,但它的直截了当的实施并不能很好地进行大型选举。 在本文中,我们开发了一种高度优化的算法,用于使用Pregel计算Schulze方法,Pregel是大规模并行计算图形问题的框架,并展示了其对大型偏好数据集的适用性。 此外,我们的理论分析表明,Schulze方法确实特别适合并行计算,与相关的排名对法形成鲜明对比。 更准确地说,我们表明受 Schulze 方法约束的获胜者确定是 NL-complete,而对于排名对法来说,这个问题是 P 完全的。
由于其复杂的动态,组合游戏是训练游戏代理算法的关键测试案例和应用程序。 使用自玩训练的算法包括共同进化算法(CoEA)。 然而,由于骑自行车等病态行为,CoEAs的成功应用很难,对于具有不瞬态回报景观的游戏来说,这个问题尤其重要。 了解如何设计CoEA以避免此类行为,可以通过运行时分析提供。 在本文中,我们将CoEA的运行时分析范围推向组合游戏,证明了UMDA发现(高概率)最佳策略所需的模拟游戏数量的一般上限。 此结果适用于任何公正的组合游戏,对于许多游戏,隐含绑定是多项式或准多项式作为游戏位置数量的函数。 在证明了主要结果后,我们为简单的知名游戏提供了几个应用程序:Nim,Chomp,Silver Dollar和Turn Turtles。 作为CoEAs对组合游戏的第一次运行时分析,这一结果是迈向Coevolution综合理论框架的关键一步。
我们分析得出了线性程序(LP)的一类最优解决方案,用于自动化机制设计,满足效率,激励兼容性,强大的预算平衡(SBB)和个人合理性(IR),其中SBB和IR在预期中强制执行。 这些解决方案可以使用一组基本变量表示,其基数比原始公式中的变量总数小成倍。 然而,评估解决方案中的一个关键术语需要指数级许多优化步骤,因为玩家数量增加N。 我们通过将这个术语的评估转化为多臂土匪(MAB)问题来解决这个问题,并开发一个可能近似正确的(PAC)估算器,具有无症状的最优样本复杂性。 这种基于MAB的方法降低了从指数到O(Nlog N)的优化复杂性。 数字实验证实,我们的方法有效地计算了目标属性的机制,扩展到高达N=128个玩家的问题 - 比以前的工作有了很大的改善。
解码策略在现代语言模型的文本生成中起着关键作用,但令人费解的差距将理论和实践分开。 令人惊讶的是,应该直观地优化的策略,例如Maximum a Posteriori(MAP),在实践中通常表现不佳。 与此同时,流行的归人主义方法,如Top-k和Nucleus采样,采用条件下图概率的截断和正常化,取得了巨大的经验成功,但缺乏理论理由。 在本文中,我们提出了解码游戏,这是一个全面的理论框架,将文本生成重新想象为战略家之间的一个双人零和游戏,他试图在真实分布中产生可信的文本,而自然则扭曲了真正的分布。 在讨论了多步骤生成后的可分解性之后,我们以封闭形式导出了一步解码游戏的最佳策略。 结果表明,对抗性自然对可能性最大化施加了隐含的正则化,截断-规范化方法是这种正则化下对最优策略的第一顺序近似。 此外,通过推广解码游戏的目标和参数,近乎最优的策略包括各种方法,如贪婪的搜索,温度缩放和混合。 进行数值实验以补充我们的理论分析。
我们正式介绍和介绍元旋转的概念,作为在学生项目分配问题中导航稳定匹配的格子的工具,讲师对学生的偏好(SPA-S)。 基于任何SPA-S实例中稳定匹配集形成分配格子的结构结果,我们为此定义了该设置的元旋转,并演示了它们如何紧凑地编码匹配之间的过渡。 我们的框架概括了双部分环境中旋转的经典概念,并提供了一种系统的方法来遍历格位,从而能够在任何给定的SPA-S实例中有效地枚举一组稳定匹配。
我们研究最大化纳什社会福利的问题,这是代理商公用事业的几何平均值,在两个着名的模型中。 第一个模型涉及片面的偏好,其中一组不可分割的项目分配给一组代理(通常在公平划分中研究)。 第二种模式涉及两面偏好,其中一组工人和公司,每个工人和公司都有对另一方的数字估值,彼此匹配(通常在匹配偏好不足的文献中研究)。 我们在能力限制下研究这些模型,这些模型限制了代理人(分别为公司)可以接收的物品(分别为工人)的数量。 我们为广泛的估值类别下的两个问题开发恒定因子近似算法。 具体而言,我们的主要结果如下:(a)对于任何ε>0,当代理具有子模块化估值时,单面问题的6 +ε)近似算法,以及(b)当公司具有子附加估值时,双面问题的1.33近似算法。 前者的结果为纳什福利提供了第一个常数因子近似算法,在单方问题中具有亚模块化估值和容量,而后者的结果则改进了现有的√(OPT)近似算法,用于添加剂估值。 我们对双面设置的结果也建立了纳什和功利福利目标之间的计算分离。 我们还通过硬度近似结果来补充我们的算法。 此外,对于添加剂估值,我们修改Feng和Li [ICALP 2024]的配置LP,以获得(e^1/e+ε)-在容量限制下加权双面纳什社会福利的近似算法。
本文介绍了一种估计马尔可夫社会困境的自身利益水平的新方法。 我们将自我利益水平的概念从正常形式的游戏扩展到马尔可夫游戏,提供调整个人和集体利益所需的最低奖励交换的定量度量。 我们在Melting Pot套件的三个环境中演示我们的方法,代表普通池资源或公共产品。 我们的研究结果说明了奖励交换如何能够使代理人在马尔可夫社会困境中从自私过渡到集体均衡。 这项工作通过提供分析复杂、多步骤社会困境的实用工具,有助于多智能体强化学习。 我们的发现提供了有关奖励结构如何促进或阻碍合作的见解,以及机制设计等领域的潜在应用。
为了将社会技术系统中的自私的资源共享代理的行为引导到更高的效率方向,系统设计人员需要代理行为和底层系统基础设施的准确模型。 例如,交通控制器经常使用道路延迟模型来设计收费,其部署可以有效缓解交通拥堵。 然而,系统参数的错误指定可能会限制系统设计者影响集体代理行为的能力。 在这项工作中,我们研究了系统错误对原子拥塞游戏收费设计的影响。 我们证明,在足够小的系统错误规范下设计的通行费,在部署时,与在无噪声设置中设计的通行费相比,在原子拥塞游戏中不会引入新的纳什均衡,这意味着一种局部健壮性。 然后,当部署在特定系统错误规格下设计的通行费时,最坏情况均衡系统性能可能会降低。 我们通过蒙特卡洛模拟验证我们的理论结果,以及实现我们最坏情况的保证。
我们研究多组织调度问题,以Pascual等人[2009]引入的框架为基础。 在这个设置中,多个组织各自拥有一组相同的机器和具有不同处理时间的顺序作业。 挑战在于在组织机器之间最佳分配工作,以尽量减少整体任务,同时确保没有组织的性能恶化。 为了正式确定这种公平性约束,我们引入了个人理性,这是一个游戏理论概念,保证每个组织都能从参与中受益。 我们的分析表明,找到一个具有最小s Θ_2^P 的单独合理时间表是很难的,将其置于比NP和coNP严格更困难的复杂性类中。 我们通过考虑另一个目标来进一步扩展该模型:最大限度地减少单个组织内部和整个系统的工作完成时间的总和。 相应的决策变体被证明是NP-complete。 通过对这两个问题的全面参数化复杂性分析,我们对这些具有计算挑战性的多组织调度场景提供了新的见解。
游戏规则的算法通常以娱乐游戏,经济理论的经典结构,如拥挤和分散游戏,或完全随机的游戏实例为基准。 虽然过去二十年来,安全游戏的兴起 - 基于巡逻和基础设施保护等现实世界的场景 - 它们的实际评估受到对用于生成它们的数据集的访问受限的阻碍。 特别是,尽管这些游戏的结构组件(例如,从地图导出的巡逻路径)可以复制,但定义目标值的关键数据 - 公用事业建模的核心 - 仍然无法访问。 在本文中,我们引入了一个灵活的框架,该框架利用开放获取数据集生成逼真的矩阵和安全游戏实例。 其中包括用于建模反偷猎场景的动物运动数据以及用于基础设施保护的人口统计和基础设施数据。 我们的框架允许用户自定义实用功能和游戏参数,同时还提供一套预配置的实例。 我们提供理论结果,强调随机游戏基准测试的退化性和局限性,并在经验上将我们生成的游戏与计算纳什和斯塔克伯格均衡的各种标准算法的随机基线进行比较,包括线性编程,增量策略生成以及与无后悔学习者的自我游戏。
在过去几年中,在从数据中学习经济解决方案方面看到了几项作品;其中包括最佳的拍卖设计,功能优化,合作游戏中的稳定回报等等。 在这项工作中,我们提供了一个统一的学习理论方法来建模这些问题,并建立了确定是否可以从数据中学习给定的经济解决方案概念的工具。 我们的学习理论框架概括了函数空间维度的概念 - 图维度 - 使其适应解决方案概念学习领域。 我们为解决方案概念的PAC可学习性确定了足够的条件,并表明可以使用我们的方法立即得出现有作品的结果。 最后,我们将我们的方法应用于其他经济领域,产生了PAC竞争均衡和PAC Condorcet获奖者的新概念。
审查电阻是区块链的核心价值主张之一。 一种旨在提供审查抵制的反复设计模式使多个提案人能够为块建设提供输入。 值得注意的是,Fork-Choice Enforced Inclusion Lists(FOCIL)被提议包含在以太坊中。 然而,目前的提案依赖于利他行为,没有交易费用机制(TFM)。 这项研究旨在通过探索如何奖励多个提案人来激励审查抵制来解决这一差距。 这项工作的主要贡献是识别TFM,以确保在贿赂攻击下抵制审查,同时也满足EIP-1559的激励兼容性属性。 我们为FOCIL提供了一个具体的支付机制,并通过分析1)在贿赂对手在场的情况下激励兼容性,2)TFM在协议中具有多个交易包含阶段的TFM,以及3)各方不确定行为和可能贿赂他人的行为的协议的TFM。
我们研究通过非货币机制公平在线资源分配的问题,其中多个代理反复共享一个资源,而无需货币转移。 以前的工作已经表明,每个代理都可以保证其理想效用的1/2(鉴于其公平资源份额,这是最高的可实现的效用),即在其他代理的任意行为下。 虽然这种1/2强守气的保证现在已经在非常不同的机制下建立,包括伪市场和动态最大min分配,但改善它似乎很困难。 在这项工作中,我们获得了在线资源共享稳健性的第一个显着改进。 更详细地说,我们考虑用人造货币进行广泛研究的重复价格拍卖。 我们的主要贡献是表明,一个简单的随机投标策略可以保证每个代理一个2 - √(2)≈0.59个她的理想效用,无论其他人的出价。 具体而言,我们的策略要求每个拥有公平份额的代理商,只要她的价值在她的价值分配的顶端 α ,就使用统一分配的出价。 我们的工作几乎缩小了与已知的1 - 1 /e≈ 0.63硬度的差距,用于稳健的资源共享;我们还表明,任何静态(即独立预算)投标政策不能保证超过0.6段的理想实用程序,表明我们的技术几乎紧张。
由大型语言模型(LLM)驱动的自主代理可以在负责任的行动越来越重要的领域实现新的用例。 然而,LLM固有的不可预测性引发了对代理可靠性的安全问题。 在这项工作中,我们探索了玩具中的代理行为,基于迭代囚徒困境的变化。 我们引入了一种策略修改方法 - 独立于游戏和提示,通过引导残余流,从稀疏的自动解码器潜伏空间中提取可解释的特征。 具有善意谈判功能的引导将平均叛逃概率降低了28个百分点。 我们还为几个开源 LLM 代理确定了可行的转向范围。 最后,我们假设LLM代理的游戏理论评估,结合表示-转向对齐,可以概括为最终用户设备和体现平台上的真实世界应用。
经典联合学习(FL)假设客户有有限数量的嘈杂数据,他们自愿参与,并以原则的方式为学习全球,更准确的模型做出贡献。 学习以分布式方式进行,而不与中心共享数据。 然而,这些方法不考虑代理参与和促进过程的激励,因为数据收集和运行分布式算法对客户端来说代价高昂。 最近文献中提出了贡献的合理性问题,并存在一些考虑这一问题的结果。 本文讨论了同时参数学习和激励贡献的问题,这将其与现存文献区分开来。 我们的第一个机制激励每个客户端在纳什均衡下为FL过程做出贡献,并同时学习模型参数。 然而,这种平衡结果可以远离最优,客户贡献他们的完整数据,算法学习最优参数。 我们提出了第二个机制,货币转移是预算平衡的,可以实现完整的数据贡献以及最优的参数学习。 使用真实(联邦)数据集(CIFAR-10,FeMNIST和Twitter)的大规模实验表明,这些算法在实践中收敛得相当快,为所有代理提供了良好的福利保证和更好的模型性能。
城市自动驾驶汽车决策和规划的主要挑战之一是有效地管理与具有不可预测的运动模式特征的多样化交通参与者的复杂互动。 此外,在快速发展的交通场景中解释和遵守交通法规构成了重大障碍。 本文提出了一个基于规则的自动驾驶汽车决策和规划框架,从交通规则中提取通行权,以生成行为参数,将其整合以有效遵守和浏览交通法规。 该框架通过将决策和规划问题制定成差异游戏,从数学上考虑交通参与者之间的强烈互动。 通过找到问题的纳什均衡,自动驾驶汽车能够找到最佳决策。 拟议的框架在模拟和全尺寸车辆平台下进行了测试,结果表明,自我车辆能够在遵守交通规则的同时安全地与周围的交通参与者进行互动。
我们考虑了一个空间投票模式,候选人和选民都位于欧几里得空间,每个选民根据他们接近选民的理想点对候选人进行排名。 我们关注的是关于选民理想点位置的给定信息不完整的情况;对于每个维度,只有可能值的间隔是已知的。 在这种情况下,我们研究在位置评分规则下确定可能的赢家的计算复杂性。 我们的结果表明,在一个维度中可能的赢家问题可以在多项式时间中解决,所有k截断的投票规则都是恒定k的。 此外,对于一些可能的赢家问题为NP完全的评分规则,例如任何维度的批准投票或d ≥ 2维度的k批准,我们给出一个FPT算法由候选人的数量参数化。 最后,我们将一个维度的加权可能赢家问题的可处理和可解决设置进行分类,并解决d=1时所有两个值位置评分规则的加权案例的计算复杂性。
了解个体代理人如何在集体中做出战略决策对于推进经济学,神经科学和多代理系统等各种领域非常重要。 方法可以为此整合两种互补的方法。 Active Inference 框架 (AIF) 描述了代理如何使用生成模型来调整他们对环境中的信念和行为。 博弈论将具有潜在竞争目标的代理人之间的战略互动形式化。 为了弥合两者之间的差距,我们提出了生成模型的要素化,即每个代理对其他代理的内部状态保持明确的个人层面的信念,并在共同的背景下将其用于战略规划。 我们使用我们的模型来迭代两个和三个玩家的通用和游戏,并研究游戏转换的集合效应,其中代理的偏好(游戏回报)随着时间的推移而变化。 这种非静止性,除了由对等适应引起的,反映了一种更自然的环境,在这种环境中,代理人需要适应不断变化的社会环境。 最后,我们介绍了关键AIF量的动态分析:数值模拟数据中的可变自由能量(VFE)和预期的自由能量(EFE)。 集成级EFE允许我们在不同的条件下使用多个Nash Equilibria来表征游戏的吸引力盆地,我们发现它不一定在聚合级别上最小化。 通过整合AIF和博弈论,我们可以更深入地了解智能集体如何在动态环境中出现,学习和优化他们的行动,无论是合作还是非合作。