一种基于算法机制设计的社会法则合成方法
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

TP18

基金项目:

国家自然科学基金(91646204,92046026,61876080,71871109);国家重点研发计划(2017YFD0401001,2018YFB1403400);江苏省重点研发计划(BE2019105)


Social Law Synthesizing Method Based on Algorithmic Mechanism Design
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    社会法则是在多Agent系统中为确立某种目标属性而对各个Agent实施的行为限制集合.在Agent具有“个体理性”及“私有信息”的“策略情况”下,社会法则合成问题不应建模成通常的优化问题,而应建模成算法机制设计问题.“最小化副作用”经常是社会法则需要满足的基本要求.从博弈论的角度来看,“最小化副作用”与“最大化社会福利”的概念紧密相关,可以将“最小化副作用的社会法则合成”建模为一种效率机制设计问题.不仅需要为给定目标属性找到有效且社会福利最大的社会法则,还需要向Agent支付适当的金额,以实现激励相容性和个体理性.首先基于VCG机制设计一种名叫VCG-SLM的效率机制,证明它可满足所有必需的形式属性.然而,由于发现可证明该机制的计算是一个FPNP-完全问题,针对性地提出该机制的一种基于整数规划的实现方式VCG-SLM-ILP,基于ATL语义将分配及支付的计算转化为整数规划,并严格地证明其正确性,从而可有效利用目前已非常成熟的工业级整数规划求解器,成功解决棘手的机制计算问题.

    Abstract:

    A social law is a set of restrictions on the available actions of agents to establish some target properties in a multiagent system. In the strategic case, where the agents have individual rationality and private information, the social law synthesizing problem should be modeled as an algorithmic mechanism design problem instead of a common optimization problem. Minimal side effect is usually a basic requirement for social laws. From the perspective of game theory, minimal side effect closely relates to the concept of maximum social welfare, and synthesizing a social law with minimal side effect can be modeled as an efficient mechanism design problem. Therefore, this study not only needs to find out the efficient social laws with maximum social welfare for the given target property but also pays for the agents to induce incentive compatibility and individual rationality. The study first designs an efficient mechanism based on the VCG mechanism, namely VCG-SLM, and proves that it satisfies all the required formal properties. However, as the computation of VCG-SLM is an FPNP-complete problem, the study proposes an ILP-based implementation of this mechanism (VCG-SLM-ILP), transforms the computation of allocation and payment to ILPs based on the semantics of ATL, and strictly proves its correction, so as to effectively utilize the currently mature industrial-grade integer programming solver and successfully solve the intractable mechanism computing problems.

    参考文献
    相似文献
    引证文献
引用本文

吴骏,曹杰,王崇骏,谢俊元.一种基于算法机制设计的社会法则合成方法.软件学报,2024,35(3):1440-1465

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2021-08-04
  • 最后修改日期:2022-05-05
  • 录用日期:
  • 在线发布日期: 2023-06-14
  • 出版日期:
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号