【IJTCS 2020】算法博弈论论坛精彩回顾

  首届国际理论计算机联合大会(International Joint Conference on Theoretical Computer Science,IJTCS)于2020年8月17日-22日在线上举行,主题为“理论计算机科学领域的最新进展与焦点问题”,由北京大学与中国工业与应用数学学会(CSIAM)、中国计算机学会(CCF)、国际计算机学会中国委员会(ACM China Council)联合主办,北京大学前沿计算研究中心承办。  

 

  8月17日,大会“算法博弈论”论坛如期举行,苏州科技大学程郁琨教授和上海财经大学唐志皓助理教授共同主持。小编为大家带来论坛精彩回顾。

 

Envy-freeness up to Any Item with High Nash Welfare
Nick Gravin,上海财经大学

 

  本次报告是关于不可分割物品分配的公平性和高效性的问题。首先,讲者介绍了相关背景知识,和问题的设定情景,结合例子解释了刻画分配公平性的重要概念——envy-free(EF)、envy-free up to one item(EF1)和 envy-free up to any item(EFX),和刻画高效性的重要概念——纳什福利(Nash Welfare)和帕雷托最优(Pareto Optimality)。同时他指出 EF 不一定存在,EF1 总是存在,而 EFX 目前只知道特殊情景下的存在性。接着,他用一个例子强调在 EFX 的公平分配下也可能会有很低的纳什福利,这也正是论文要探索和解决的问题。

 

  关于这个问题,讲者先说明了局部 EFX 分配(partial EFX allocation)的想法,如将部分物品捐给慈善机构等可能性,然后讲者分享了三个成果。第一个是总存在局部 EFX 分配使得它的纳什福利至少是最优纳什福利的1/2,并且该分配是帕雷托最优的;另外,这里的1/2是紧的,即存在一种情形使得任何 EFX 分配的纳什福利都不超过最优纳什福利的1/2。第二个是在大市场条件下,即每个物品的价值相对于整个市场中物品总价值而言足够小,此时存在局部 EFX 分配使得它的纳什福利足够接近最优纳什福利。第三个是找到上述局部 EFX 分配的算法。

 

Fair Division of Mixed Divisible and Indivisible Goods
贝小辉,南洋理工大学

 

  如何公平地分配资源一直是一个研究的热门话题。相关研究的模型可以分为两个类别:其一,假设资源是多种多样并且无限可分的,也就是 cake cutting 问题;其二,假设资源是不可分割的。对前者而言,公平性由 envy-freeness(EF)刻画,即相比于别人得到的物品,每个参与者都更喜欢自己的那一份;而对后一种假设而言,EF 性质可能不存在,因此被放宽为 envy-freeness up to one good(EF1):如果从别人的物品中移走一种,那么所有人都更喜欢自己的那一份物品。在此基础上,讲者考虑了一个更加现实的模型——资源是混合的,既包含可分的也包含不可分的。相应的,讲者也将 EF 和 EF1 融合为 envy-freeness for mixed goods(EFM)。直观地说,EFM 要求对于每个参与者,如果其份额中仅包含不可分割的资源,则其他人将使用 EF1 标准进行比较;但如果参与者分到了可分割的资源,则其他人将使用更严格的 EF 标准进行比较。

 

  讲者证明了对于任意数量的参与者始终存在 EFM 分配,并根据是否存在 oracle 分别给出了算法,最后讨论了如何在 Robertson-Webb 模型下用多项式时间内找到 ε-EFM 近似的分配。

 

Truthful Mechanisms for Location Games of Dual-Role Facilities
陈旭瑾,中国科学院数学与系统科学研究院

 

  在 Facility Location Game(FLG)中,政府要根据用户的位置选择公共设施的建造地点,而设施与用户的距离决定了用户要支付的费用。在传统模型中,用户的位置是私有的信息,因此用户可以有策略地上报自己的位置来减少需要支付的费用,而政府是无策略的,并且建造设施的地点是任意的。但在现实场景中,建造地点也需要在几个预先公开的场地中选择一个或多个,同时还往往要考虑政府的财政收入。因此,讲者提出 Dual-Role FLG(DFLG),将政府和用户统一为有策略的 agent,这些 agent 的位置是公开的。每个 agent 都是潜在的设施建造者,同时他们各自的建造成本是私有信息。当一个 agent 成为建造者时,会产生建造成本同时对其他 agent 收费。因此,agent 的收益是其收取的服务费减去成本,而每个 agent 可以通过有策略地上报自己的成本来提高收益。

 

      在此基础上,讲者研究了真实机制设计,并有如下结果:
      1. 当目标为最小化最大费用时,给出了多项式时间的最优真实机制。
      2. 当目标为最小化总费用时,给出了 individually rational 并且 normalized(不是建造者的 agent 收取费用为0)的真实机制;以及一个多项式时间,近似比为1.61的近似算法。

 

Dominantly Truthful Multi-task Peer Prediction with a Constant Number of Tasks
孔雨晴,北京大学

 

  同伴预测是日常生活中常见的问题,例如发放调查问卷时,需要设计合理的机制鼓励回答者填写其真实的倾向。其挑战在于需要在尽可能少的先验知识和预设下,设计实际可行的真实(truthful)机制。过去的工作或者真实性是近似的(ε-δ truthfulness),或者需要无穷多次询问。

 

  在该工作中,讲者在通常的框架下,设计了一种基于行列式的互信息函数。讲者证明了该函数对询问结果所提供的信息量是单调的,并用常数次询问获得了该互信息函数的一个无偏估计作为回报函数,得一真实机制,对过去的工作作出了突破式的改进。最后,讲者还根据该机制设计了一个 scoring rule,后者还可用于机器学习中,设计对标签噪音鲁棒的损失函数。

 

Data-driven Auctions, Prophet Inequality, and Pandora's Problem
黄志毅,香港大学

 

  在机器学习理论领域,算法的样本复杂度是一个重要的研究方向。它代表了我们需要提供给该算法的训练样本的数量,从而算法才能在一组函数中寻找到一个几乎最优的函数。近年来,在贝叶斯优化问题(Bayesian Optimization Problem)的样本复杂性也逐渐被大家所重视。其中,关于拍卖(Auctions),先知不等式(Prophet Inequality)和潘多拉问题(Pandora's Problem)已有一系列研究。在先前的研究中,人们对这些问题的样本复杂性研究是基于具体问题单独分析的。此报告首次给出了一个通用方法,在三个问题的样本复杂度上都得到了最优或是接近最优解。

 

  具体地,讲者关注了高维数据点满足乘积分布,即数据的不同维度之间独立的情况。分析主要分为三步进行,把对于数据集的假设逐步放宽。首先对于数据集有界且支撑集有限的情况,讲者得到的结论可直接推广,得到多物品拍卖问题的最优样本复杂度。第二步,讲者把支撑集有限的假设替换为强单调性,其中强单调性是以上三个问题均满足的性质。在这个条件下,得到的结论可以直接推出单物品拍卖、先知不等式和潘多拉问题接近最优的样本复杂度。最后一步,将有界的条件去掉,得到的结论能直接推出在分布无界情况下的单物品拍卖、先知不等式和潘多拉问题接近最优的样本复杂度。