近日，高瓴人工智能学院王子贺团队的学术论文《Improved Approximation Ratios of Fixed-Price Mechanisms in Bilateral Trades》被ACM 计算理论年会（ACM Symposium on Theory of Computing，STOC）正式录用。这是中国人民大学师生首次在该顶级学术会议上发表论文。STOC是理论计算机领域的顶级国际会议之一，始于1969年，在整个计算机科学领域享有崇高的声望，属于公认难度较高的会议。与人工智能不同，计算机理论领域被认为是国内学界与全球顶级水平相距较大的方向，在 STOC 大会中，近五年里中国科研机构参与的论文共43篇，其中完全由国内科研机构完成的论文只有11篇。

STOC会议涵盖了算法和数据结构、计算复杂性、组合数学、近似算法、密码学、算法博弈论和量子计算等一系列理论计算机方向。本届STOC共收到投稿479篇，录用155篇，接收率约为32%。该工作由中国人民大学高瓴人工智能学院准聘助理教授王子贺、2020级博士生任泽宇和北京理工大学助理教授刘正阳合作完成。

论文概述

双边交易是经济学中的经典问题，双人双边模型仅包含一个买家和一个卖家，他们希望交易一个不可分割的物品，且对该物品有私人估值，分别用S和B表示。机制设计者假设知道两个价值分布，但不知道具体的价值。双边交易中的激励兼容（Incentive Compatibility）、个体理性（Individual Rationality）、预算平衡（Budget Balance）机制的研究始于1983年，Myerson和Satterthwaite提出的不可能定理表明，不存在同时满足上述三项性质且社会福利达到max{B，S}的机制。1987年，Hagerty和Rogerson证明了唯一的占优策略激励相容（Dominant Strategy Incentive Compatibility）、个体理性、强预算平衡（Strong Budget Balance）机制是固定价格机制。在该机制中，机制根据双方估值分布选择一个价格p，当S≤p≤B时交易发生。该工作旨在探讨双边交易问题中固定价格机制的社会福利近似效果。本文发现根据买家和卖家的估值分布信息选择最优价格的近似效果，与只根据买家估值分布信息设计一组价格分布的近似效果相同。并给出了买家分布与价格选取的关系，从而刻画出了近似社会福利的极限情况，并通过数值求解将之前近似比最好的下界1−1/e+0.0001≈0.632提高至了0.71。

作者介绍

王子贺，系中国人民大学高瓴人工智能学院准聘助理教授。本科期间就读于清华大学计算机科学实验班，于2016年在清华大学分别取得博士学位，博士导师是唐平中和姚期智。2016-2020年任职于上海财经大学信息管理与工程学院，2020年加入中国人民大学高瓴人工智能学院。研究兴趣是理论计算机与经济学的交叉学科，如：博弈论、机制设计、算法设计等。

（责任编辑：陈子玥）