2024 年算法博弈论研讨会 (SAGT) 特刊引言

《ACM Transactions on Economics and Computation》：Introduction to the Special Issue for the Symposium on Algorithmic Game Theory (SAGT) 2024

　　第17届算法博弈论国际研讨会（SAGT 2024）于2024年9月3日至6日在荷兰阿姆斯特丹举行。SAGT为计算机科学、经济学和博弈论交叉领域的研究提供了一个论坛，涵盖算法机制设计、计算社会选择、均衡及其效率，以及匹配和分配问题。SAGT 2024上部分会议论文的作者受邀向《ACM Transactions on Economics and Computation》的本期专刊投稿。本专刊收录的六篇论文均经过大幅修改和扩展，并按照该期刊的标准流程进行了同行评审。这些论文共同展示了算法博弈论的广泛性，将结构分析与复杂性理论分析同策略系统的设计与评估相结合。第一篇论文，Gennaro Auricchio和Jie Zhang撰写的《利用最优传输为设施选址问题设计最优机制》，研究了贝叶斯机制设计设置下线上的$k$-设施选址问题，重点关注真实的百分位机制。通过将问题与瓦瑟斯坦空间中的投影联系起来，作者刻画了这些机制的渐近贝叶斯近似比，建立了收敛性保证，并识别了针对代理人位置分布定制的最优百分位机制。该论文还处理了单位区间边界处的百分位向量，并将分析从社会成本扩展到$?\_p$范数和最大成本目标。在《铺装拟阵拥塞博弈中的无政府状态价格》一文中，Bainian Hao和Carla Michini研究了拟阵结构如何在对称拥塞博弈中限制纯纳什均衡的低效性。他们推导了通用延迟函数类下$k$-均匀拟阵和铺装拟阵的上界，以及仿射延迟的改进上界。他们的分析使用均衡与社会最优解之间的交换流，从而将拟阵基交换与无政府状态价格联系起来。所得到的上界表明，铺装拟阵的组合结构可以显著限制均衡的低效性。第三篇论文，Yiannis Giannakopoulos和Johannes Hahn撰写的《离散单参数最优拍卖设计》，发展了Myerson最优拍卖理论核心方面的离散对应物。利用线性规划对偶和多面体方法，作者为有限支撑值分布推导了收入最优拍卖的虚拟福利刻画，并证明了对抗更广泛的贝叶斯激励相容机制类时，确定性的占优策略激励相容拍卖是最优的。他们随后将该框架推广到一般的凸单参数环境和将收入与社会福利相结合的目标，利用KKT条件刻画广义虚拟福利最大化。该论文还给出了一个在树上进行有容量流量拍卖的应用。接下来讨论维持策略行为所需的信息资源，Farid Arthaud撰写的《使用次线性随机性玩重复博弈》一文研究了在随机化稀缺或成本高昂的情况下，有限重复标准型博弈中纳什均衡所需的熵。该文完整刻画了重复版本存在常数随机性均衡的博弈，并证明了一条零一规律：重复博弈要么存在仅需$O(1)$随机性的均衡，要么每个均衡所需随机性都与重复次数成线性增长。该文进一步刻画了可达收益分布，并研究了可观测混合策略设置以及仅对部分博弈者有界随机性的设置。在《室友问题中稳定圈与稳定划分的结构结果和算法结果》一文中，Frederik Glitzner和David Manlove研究了稳定划分——一个即使稳定室友问题的实例不存在稳定匹配时仍然存在的解概念。作者建立了稳定圈和稳定划分的新结构结果，开发了高效的枚举算法，并展示了稳定划分与稳定半匹配之间的对应关系。他们还将从稳定匹配中借用的若干公平性和最优性准则推广到稳定划分，识别了可处理与不可处理的变体，并对后者的一些变体给出了近似结果。最后，Ioannis Caragiannis和Sebastian Homrighausen撰写的《估计随机序列独裁制的期望社会福利与成本》一文，探讨了随机序列独裁制在分配问题中的评估。作者考虑了基于价值和度量成本两种设置，并证明采样相对少量的优先顺序即可分别近似随机序列独裁制的期望社会福利和期望社会成本。尽管精确评估是#P-难的，这些结果提供了计算上可行的估计器。我们感谢各位作者对会议论文进行的细致修改与扩展，也感谢匿名审稿人提出的富有建设性和详尽的评审报告。我们同样感谢SAGT 2024程序委员会、会议组织者以及《ACM Transactions on Economics and Computation》编辑团队对本期专刊的支持。Guido Sch?fer荷兰莱顿数学与计算机科学研究中心，荷兰阿姆斯特丹大学邮箱：[e-mail] Ventre英国伦敦国王学院邮箱：[e-mail]客座编辑