一种基于算法机制设计的社会法则合成方法

Social Law Synthesizing Method Based on Algorithmic Mechanism Design

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

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 FP^(NP)-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.