近日,必赢官网特聘教授韩恺(第一作者)所著论文“Triple Eagle: Simple, Fast and Practical Budget-Feasible Mechanisms”被NeurIPS‘2023接收。NeurIPS是国际公认的人工智能和机器学习领域最具权威的两个世界顶级会议之一(另一个为ICML),于每年的12月举行,其全称是神经信息处理系统大会(Conference on Neural Information Processing Systems),为CCF A类会议。
该NeurIPS‘2023论文研究了人工智能与算法博弈论交叉领域的经典问题之一:“预算受限的机制设计”(Budget Feasible Mechanisms)问题。该问题由哈佛大学教授、人工智能领域权威学者Yaron Singer于2010年在计算机算法领域国际Top 2会议FOCS’10提出,并受到广泛关注。针对该问题,许多国内外著名学者如算法博弈论开创者之一Eva Tardos(美国三院院士、ACM Fellow)、国内计算机算法理论领域的领军学者之一陆品燕教授等人曾展开了跟踪研究并在STOC、SODA、EC、WINE、ACM Trans. on Economics and Computation、Mathematics of Operations Research等国际顶级会议和期刊发表了一系列论文。该NeurIPS’23论文的主要贡献是针对该问题提出了一种创新的算法框架和若干算法,使得在面向单调或非单调次模函数时均在近似比指标上提升了前人所提的系列算法,同时将前人算法的最低时间复杂度O(n2)大幅降低为O(n)。NeurIPS审稿人给予该论文高度评价,认为该论文给出了创新(“novel”)的解决方案,并在理论和实验上均显著超越了state-of-the-art。因此,四个审稿人给出了4个7分(即4个accept)的高分。