AAAI 2021 | 投票的滑润复杂度

本文是第三十五届人工智能大会(AAAI 2021)入选论文《The Smoothed Complexity of Computing Kemeny and Slater Rankings》的解读。

论文链接:https://arxiv.org/abs/2010.13020

常用投票条例下的优胜者抉择课题(winner determination)的算计复杂性是算计社会抉择(computational social choice)范畴中历史悠久的基本课题。从实际应用的角度出发,我们往往希望优胜者抉择课题的算计复杂性比较低。然而对于一些经典投票条例例如 Kemeny,Slater 等,其优胜者抉择课题在最坏情形(worst-case)下已被证明是 NP-hard 的,即对于大规模课题实例,目前暂不存在高效的算法来确定优胜者。平均情形(average-case)综合虽然比最坏情形综合稍微实际一些,但是其对于输入实例的分布假如相当敏感:例如在算计社会抉择理论中被称为 Impartial Culture 的假如,要求投票者对于候选者的排序服从独立的均匀随机分布。许多经验性证据表明这类分布假如并不贴近现实。

AAAI 2021 | 投票的滑润复杂度

Spielman and Teng(2004)引入了滑润综合(smoothed analysis),拓展并结合了最坏情形综合与平均情形综合。其主要想法是算法的输入数据往往是真正值(ground truth)的微小扰动之后的值。对于任何确定的课题实例,自然会在上面加一个诸如高斯噪音的小扰动形成概率分布,而算法的运转工夫是该分布下的期望运转工夫。由此,算法的滑润运转工夫定义以下图所示:

AAAI 2021 | 投票的滑润复杂度

通过改变扰动的幅度,滑润运转工夫完美地架起了最坏情形运转工夫与平均情形运转工夫之间的桥梁。可以看出,当扰动趋于零时,滑润运转工夫等价于最坏情形运转工夫,而当扰动非常大时,滑润运转工夫等价于均匀分布下的算法运转工夫。对于适当的扰动幅度,滑润综合能够结合两者优点,提供接近真正数据与现实应用场景的算法综合。

滑润综合最著名的应用是线性规划课题,它为最坏情形下需要指数多步骤的单纯形法为什么在实际中的运转速度非常快提供了有力且令人信服的解释。在机器学习,均衡综合,组合优化等范畴,滑润综合也得到了广泛应用。例如纳什均衡算计的滑润复杂度是PPAD-complete的。然而,常用投票条例下的优胜者抉择课题,乃至任何算计社会抉择范畴内的算计课题的滑润复杂性却没有任何结果。

实际上,这个课题不仅仅是算计社会抉择范畴内的理论课题。由于投票机制是自动决策系统中的重要一环,滑润复杂性的研究对于人工智能中也有实际意义。考虑以下例子:当一个智能系统的开发者为了群体决策想要实现一种投票条例例如 Kemeny 来达到共识。这个系统需要估计算计 Kemeny 优胜者的运转工夫,来抉择分配多少算计资源以获得及时的决策。它可以通过智能体过往的行为来学习并预测其偏好,但是只能得到关于偏好排序的概率分布。这个概率分布可以刻画成真正偏好排序加上随机噪音后的结果。在这种情形下,是否存在一种期望运转工夫是多项式的算法呢?

本文首次提供了以下公开课题的理论结果:常用投票机制下的优胜者抉择课题的滑润复杂性是什么?

我们采用了单人偏好模型(single agent preference model, Xia (2020))来综合这个课题。在此模型下,每个投票者可以抉择集合中的任何一个偏好概率分布(等价于存在一个恶意对手为每个投票者抉择任意相关的真正偏好,然后自然为每个投票者加上独立的扰动)。我们证明了以下定理:

[定理]对于满足一定条件的单人偏好模型,如果存在滑润运转工夫为多项式的算计 Kemeny 或者 Slater 的算法,那么 NP=RP。

定理中对于单人偏好模型的假如覆盖了一大类算计社会抉择范畴内已知的统计模型,而 NP=RP 一般被认为是不成立的(常见的复杂性理论假如)。因此,该定理指出在滑润综合框架下,Kemeny 和 Slater 条例的优胜者抉择课题依旧是困难的。虽然如此,我们得到关于参数化一般情形滑润复杂性的部分正面结果:对于一大类基于算计社会抉择中经典的 Mallows 统计模型的单人偏好模型,原有的动态规划算法对于参数规模受限课题实例以高概率在多项式工夫内输出结果。

图文 | 郑炜强

Distributed and Automated Games and Managerial Economics (daGAME)

原创文章,作者:北京大学前沿计算研究中心,如若转载,请注明出处:https://www.iaiol.com/news/aaai2021-tou-piao-de-hua-run-fu-za-du/

(0)
上一篇 2022年 7月 18日 下午3:45
下一篇 2022年 7月 18日 下午5:03

相关推荐

  • ICLR 2022 | 操纵3D铰接物体的视觉操纵轨迹学习

    本文是 ICLR 2022入选论文《VAT-Mart: Learning Visual Action Trajectory Proposals for Manipulating 3D ARTiculated Objects》的解读。该论文由北京大学前沿计算研究中心董豪课题组与斯坦福大学、腾讯人工智能试验室合作实现。文章提出了一种新型的物体功能可操纵性表示,设计了一个通过交互进行感知学习的框架以学习这个表示,并在百般的物体上实现操纵工作。

    2022年 7月 18日
  • 争取盟友、洞察人心,最新的Meta智能体是个谈判高手

    AI 学会了「揣度人心」,这本来是世界上最难的事情之一。

    2022年 11月 23日
  • 全球首台百亿亿级超算用AMD的GPU:性能增7倍,能效提升3倍

    E 级超算,每秒钟百亿亿次运算,1 后面跟 18 个零。

    2021年 12月 26日
  • 十二年穿越周期,“AIGC第一股”外出问问今日挂牌上市

    4月24日,“AIGC第一股”外出问问有限公司(简称“外出问问”或“公司”,股份代号:2438),正式登陆香港交易所主板,股份代号为2438.HK,每手买卖单位1,000股股份。截至9:40,外出问问报于每股3.23港元,市值48.18亿港元。据配发结果公告显示,此次外出问问(02438.HK)寰球出售8456.8万股股份,国际出售4228.4万股股份,公开出售4228.4万股股份,其中,公开出售获117.39 倍认购。最终出售价每股3.8港元,寰球出售净筹约2.67亿港元。据悉,外出问问在招股期认购异常火爆,创下

    AI 2024年 4月 24日
  • 欧洲投资银行供应1.5亿欧元反对欧洲人工智能企业

    欧洲投资银行团体(EIB Group)启动了一项高达1.5亿欧元的新的融资东西,反对人工智能及与人工智能直接相干/互补的区块链、物联网和机器人技能。与新的融资东西相干的资金反对将在将来四年内布置,供应给欧盟和Horizon 2020相干国家与地区,重点投资开发突破性人工智能应用的晚期和成长阶段的公司。这项东西是EIB团体和欧盟委员会更大计划的一部分,旨在反对高性能计算、量子技能和网络安全等规模的欧洲数字将来倒退。12月3日,在2020年Web峰会上,欧洲投资银行团体(EIB Group)启动了一项新的融资东西,以支

    2020年 12月 9日
  • Hologres揭秘:深度解析高效率分布式查问引擎

    Hologres(中文名交互式分析)是阿里云自研的一站式及时数仓,这个云原生体系融合了及时服务和分析大数据的场景,全面兼容PostgreSQL协议并与大数据生态无缝打通,能用同一套数据架构同时支持及时写入及时查问以及及时离线联邦分析。它的出现简化了业务的架构,与此同时为业务提供及时决策的能力,让大数据发挥出更大的商业价值。Hologres作为HSAP服务分析一体化的落地最佳实践,其查问引擎是一个完全自研的施行引擎,它的核心设计目标是支持所有类型的分布式分析和服务查问,并做到极致查问机能。为了做到这一点,我们借鉴了各

    2021年 8月 11日
  • google并未放弃TensorFlow,将于2023年发布新版,明确四大支柱

    2015 年,google大脑开放了一个名为「TensorFlow」的钻研项目,这款产品迅速流行起来,成为人工智能业界的主流深度进修框架,塑造了现代呆板进修的生态系统。从那时起,成千上万的开源贡献者以及众多的开发人员、社区组织者、钻研人员和教育工作者等都投入到这一开源软件库上。然而七年后的今天,故事的走向已经完全不同:google的 TensorFlow 失去了开发者的拥护。因为 TensorFlow 用户已经开始转向 Meta 推出的另一款框架 PyTorch。众多开发者都认为 TensorFlow 已经输掉了这场战争,并将其比

    2022年 10月 24日
  • 硬科技起飞,这家成立仅三年的AI钻研院已颇具国际风范

    摘要:「我认为历史上多数突破性钻研成果的出现都是偶然事件,而钻研机构所有努力都是为了提升这类偶然事件发生的概率。」张宏江说道。他所牵头的「革新型钻研院」,即是一种积极探索,短短3年已展现一派生机。

    2022年 1月 11日
  • 华盛顿大学《天生模型》2020秋季课程完结,课件、讲义全部放出

    这门课聚焦天生建模技术的理论和数学基础,探讨多种天生模型技术。

    2021年 1月 29日
  • 拖拽公式图片、一键转换LaTex公式,这款开源公式识别神器比Mathpix Snip更适合你

    只必要把公式图片用鼠标拖动到东西内,就能一键转成 LaTex 公式。

    2021年 8月 15日

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注