第三届国际理论计算机联合大会（International Joint Conference on Theoretical Computer Science-Frontier of Algorithmic Wisdom，IJTCS-FAW）由北京大学讲席教授邓小铁于2020年牵头发起，第三届于2022年8月15日-19日线上线下交互举行。大会由中国计算机学会（CCF）、国际计算机学会中国委员会（ACM China Council）、中国工业与应用数学学会（CSIAM）联合主办，香港城市大学（CityU）承办，北京大学前沿计算研究中心、北京大学人工智能研究院协办。

　　

　　8月16日，大会“算法博弈论”分论坛如期举行，由苏州科技大学程郁琨教授和北京理工大学刘正阳助理教授共同主持。小编为大家带来论坛精彩回顾。

 

特邀报告精彩回顾

　　

Practical Fixed-parameter Algorithms for Defending Active Directory Style Attack Graph

郭明宇，阿德莱德大学

 

 

　　活动目录（Active Directory）是 Windows 域网，也是网络攻击的一个主要目标。报告介绍了活动目录上网络攻击的防范问题。一个活动目录的环境可以描述称一个攻击图的形式，节点代表每个账户，电脑等个体，而从A到B的有向边代表一个攻击者可以从 A 连接到 B。而网络攻击的防范问题可以建模成一个贝叶斯 Stakelberg 博弈问题。令 G(V,E)  代表攻击图，其中 n=|V|, m=|E| ，攻击者从一个服从某个分布的进入节点 s 出发，目标是到达被称为 DA 的目标节点。防御者可以选择阻塞 b 条有向边，b 代表防御者的防御预算，之后攻击者将会选一条从 s 到 DA 的最短路径来攻击 DA 。攻击者的成功率 f(x) 仅与最短路径长度 x 有关，要求 f(x) 单调不减且 f(∞)=0。防御者的目标是最小化攻击者的成功率。

 

 

　　当进入节点只有一个时，这个问题也被证明是 NP-hard 的，因此作者只需要考虑设计出固定参数可解（FPT）的算法。报告提出了三种固定参数可解的算法 BUDGETFPT，DP，SPLITFPT，并对这三种算法的复杂度进行了理论分析。讲者的工作还将 SPLITFPT 算法转化成一个基于图卷积神经网络的启发式算法。除去精确算法以外，他们也训练了一个神经网络用于猜测最优解，而基于神经网络的方法也是一个加速 FPT 算法的普遍的方法。他们对这些算法进行了广泛的实验，并且以贪婪算法作为基准算法，在特定参数下，精确算法以及神经网络算法给出的结果相比于贪婪算法有20%到30%的降低。报告指出，他们提出的算法可以在实际环境下帮助IT管理者识别高风险的边，以达到防御的目的。

　　

接收论文报告精彩回顾

 

EFX under Budget Constraints

戴思佳，中国科学院深圳先进技术研究院

 

 

　　公平分配（fair division）问题在疫苗分配、政府拍卖和遗产继承等方面有着广泛的应用。在实际生活中，agent 能否被分配某个物品还受到他们自身预算的限制。本报告研究了在预算限制下物品分配的效率和无妒忌（envy-free）性质。在预算限制下，每个物品都对应一个非负的价格，而 agent 的预算要求他们所得物品得总价格不超过其预算。此时 envy-free（BFEF）是指对于任何一个给定的 agent i 和 j ，i 不会认为 j 所分配到的任何一个满足 i 自己预算限制的物品子集 S 比自己所分配到的物品更有价值，反之亦然。由于 EF 一般地是无法保证成立的，报告考虑了 EF 的一个松弛版本：将前述定义的 S 修改为 S 去掉任何一个其中的物品 g 的价值，所得限制称为 BFEFX。在每个 agent 对物品的估值是0或者1的情况下，报告给出了一个基于 round robin 和妒忌消除的算法，在多项式时间内可计算出一个满足预算限制的 BFEFX 的分配。同时报告还研究了分配的效率问题，并证明：在同样的条件下，任何一个最大化纳什社会福利的分配都是1/4-近似 BFEFX 的。这里，α-  近似 BFEFX 是指任何一个 agent 对自己分配到物品的估值都至少是其它 agent 满足预算的物品子集去掉任何一个物品的价值的 α 倍。

　　

Two Faciality Location Games with Distance Requirement

盖玲，东华大学

 

 

　　设施选址问题是生活中常见的一类问题，一个基本的问题是适当地安排设施的地址，使得参与者到最近设施的距离之和最短。假设参与者 i 的位置能够被 X_i∈[0,1] 表示，当设施只有一个时，最优方案显然是将设施放在参与者的中位数位置上。在一些其他问题中，假如参与者知道设施将会以最优方案被安放，那么参与者可以通过谎报自己的位置来使自己与设施的距离更近。因此我们只考虑 strategy-proof 的机制，在这种机制下参与者不能通过谎报来使自己达到更优的收益。由于对机制的约束加强了，因此最优机制带来的社会福利只有可能更低。我们把无约束情况的最优值与带约束情况的最优值之比称为该问题的近似比。前人已经证明过当 k≥3 时，有 n≥k+1 个参与者的 k- 设施选址问题具有无界的近似比，而 k=1 又存在平凡解，因此研究者们将 k=2 作为了首要考虑的问题。

　　

　　一种变体是考虑两个设施的距离不能低于一个给定的常数，这种问题已经被前人研究并给出了不错的近似比的上下界。报告人的主要工作考虑了两个设施的距离不能高于一个给定常数的情形，并且该问题取其反形式，即参与者到最近设施的距离之和越大越好。报告通过对机制进行分类讨论，对该问题的近似比给出了常数上界的证明。她也考虑的两个设施的距离在某个区间内的情形，并给出了类似的结果。针对听众关于这个界是否是紧的的提问，她指出该问题本身具有很强的非连续性，其证明难度显著高于距离不低于给定常数的问题，因此虽然分类讨论略显繁杂，但也是一个必要的手段。如图为报告给出的近似比上界随距离上界 b 的示意图，她也认为该结果也是可能存在提升空间的。

 

　　

Optimally Integrating Ad Auction into E-Commerce Platforms

李维安，北京大学

 

 

　　竞价广告是电商平台的重要收入来源。当用户发出搜索请求时，电商平台需要决定在搜索结果的哪些位置插入广告，以在广告的点击率与用户体验之间取得平衡。不同于许多电商平台设置固定的广告数量和位置的做法，报告人考虑了广告与原有搜索结果的混合排列，提出了一个集成广告系统以同时决定广告和搜索结果的排列位置，并在最优化广告收入的同时兼顾用户体验。用户体验的衡量标准是预期成交金额，它能反映搜索结果的有效性。

　　

　　集成广告系统由分配规则与支付规则两部分组成，其中分配规则决定广告和搜索结果的排列位置，而支付规则决定每个广告被点击时平台收取的广告费。报告人提出了两类优化问题模型：有约束问题和无约束问题，并分别刻画了最优的真实报价机制。在无约束问题中，优化目标是广告收入与预期成交金额的凸线性组合。在这一问题模型下，报告人通过每个广告的虚拟价值与预期成交金额的组合，计算出修正虚拟价值，而每个搜索结果的修正虚拟价值只包含预期成交金额一项。报告人证明了，最优排列方案是将所有广告与搜索结果按照修正虚拟价值从高到低排序，并给出了对于广告的支付规则。在有约束问题中，优化目标是在预期成交金额不低于一个值的约束之下最大化广告收入。报告人证明了存在某个最优组合比例，使得有约束问题的最优机制等价于使用最优组合比例的无约束问题的最优机制，并给出了求解最优组合比例的二分算法。报告人还考虑了问题的多种扩展，例如对广告数量的限制。最后报告人通过实验表明了算法的有效性。

　　

Verifiable Crowd Computing: Coping with Bounded Rationality

Lu Dong, Pace University

 

 

　　报告人使用重复博弈框架，设计与分析了可验证云计算场景中主从（master-worker）架构的机制。一个主服务器不断将计算任务派发给工作者服务器，并为工作者服务器完成的计算任务支付报酬。在此场景下如何保证工作者服务器诚实地完成计算是一个重要的问题。先前的工作通常假设工作者是完全理性的，以最大化自己的期望收益为目的，从而所有工作者都会遵循均衡行为。但在现实中，这样的假设很可能无法被满足，一些工作者可能会为了短期利益而偏离均衡行为。报告人考虑了在工作者只有有限理性的条件下的主从模型的机制设计。

　　

　　在提出的模型中，工作者分为跟从者（follower）与偏离者（deviator）两类，跟从者将会遵守均衡行为，同时尝试找出偏离行为；偏离者只有有限理性，当每个偏离者被惩罚一次后就变为遵守均衡行为的跟从者。跟从者检测到偏离者没有正确计算时，将会调整自己的行为以降低偏离者的收益，达到惩罚偏离者的目的。主服务器会对跟从者发放补偿以激励跟从者惩罚偏离行为。在分析中，报告人利用 Chernoff Bound 保证计算正确率和偏离行为被检测到的概率，并计算当一个跟从者惩罚其检测到的偏离者时双方的收益，以此决定适当的惩罚轮数和补偿金额。

　　

　　通过模拟实验，报告人将这一有限重复博弈机制（FRG）与进化动态机制（ED）和无限重复博弈机制（IRG）进行比较，表明提出的机制能用较少的主服务器支出取得较高的计算正确率。

　　

Constrained Heterogeneous Two-facility Location Games with Max-variant Cost

Qi Zhao, Ocean University of China

 

 

　　报告人提出了一个带有约束的异质性设施选址模型。模型中考虑有两个异质性的设施需要决定建造位置。在实数轴上有 n 个代理，每个代理有可能同时需要两种设施，也可能只需要两种设施中的一种。一个可重集合A代表在实数轴上可以建造设施的位置，A中的每个位置最多能建造一个设施。每个代理产生的开销是他的位置到他所需要的设施的最大距离。报告人考虑了两种社会目标：最小化所有代理的开销总和，或最小化所有代理的开销的最大值。

　　

　　报告人设计确定性机制，根据代理报告的位置和需求决定两个设施的选址。机制同时需要满足群体策略防范（group strategyproof），也就是任意一个子集的代理无法通过同时谎报位置使得子集中每个代理的开销降低。机制的近似比定义为机制产生的选址方案的社会目标与所有选址方案中最优的社会目标之比的最大值。

　　

　　报告人首先分析了每个代理都需要两种设施的情形，对于开销总和与开销最大值两种优化目标都给出了3-近似的群体策略防范的机制。对于开销总和的目标，报告人证明了3是任何策略防范的确定性机制的近似比的下界。

　　

　　报告人之后考虑有一些代理只需要一种设施的情形，对于开销总和的社会目标提出了 (2n+1)-近似的群体策略防范的机制，对于开销最大值的社会目标提出了9-近似的群体策略防范的机制。

　　

主持人与讲者交流