Research On Solving The Core For Boolean Games Based On Hypergraph Structure

Game theory is often used to study how to design interaction strategies to make the system stable and maximize the payoff of each agent in multi-agent system.In recent years,Boolean Game,an emerging game representation framework,provides a new thought for the analysis of multi-agent system.Boolean game is a representation method based on logical reasoning,which formalizes agents' rational behaviors through propositional logic.Boolean game contains a collection of agents and a set of action variables,in which each agent rationally control a set of action variables,each action variable is controlled by one and only one agent,and each agent has an explicit goal that is represented by proposition formulae.Boolean game are not only applied to model representations,but also to some real-world scenarios,such as the coordination of traffic lights,electric vehicle charging,projects allocation,automation control and so on.We investigation the hot direction of Boolean game,that is,the problem of solving stable strategies that include Nash equilibrium and the core.The research on the stable strategies under Boolean game mainly focuses on Nash equilibrium of non-cooperative games,while the research on the core of cooperative games is not much,so we mainly focuses on the algorithm of solving the core under different constraint scenarios.The core of game theory is the set of stable strategy profiles from which no coalition containing non-empty agents is willing to deviate.Deciding whether the core is non-empty is ?2P-complete,while determining whether the core is empty set is?2P-complete.Obviously,the process of solving the core is a typical non-deterministic decision problem,including two sub-processes,i.e.,strategy generation and strategy test.Therefore,we can reduce the search space of the two sub-processes to optimize the algorithm of solving the core.One of the goals of the present work is to reduce search space through specific con-straints that is bounded hypertree width hypergraph and acyclic dependency graph.There are two method.In the first one,we first transform Boolean game into con-straint satisfaction problem,thereby get hypergraph on Boolean game in terms of the constraint satisfaction problem.According to the different variables,Boolean game can be transform into two hypergraph structure,(1)construct hypergraph according to the action variables contained in agents' gaols;(2)construct hypergraph according to the dependency relations between agents.And then an efficient method based on hypertree decomposition is designed on Boolean game with acyclic and bounded hy-pertree width constraint.in the second method,we first construct a directed graph based on the dependence relation between agents,and then decompose the dependen-cy graph based on the concept of stable set to obtain the sub-Boolean game,thus reducing the search space to some extentThe second aim of the present work is a further study of the property of the core.The core is divided into hard core according to whether the core is influenced by cost function,and then we give the basic property of hard core and soft core.We prove that hard core is the solution set of maximize social welfare and is unique,while the existence of soft core can guarantee the existence of incentive mechanism for Boolean game to obtain desirable core.Finally,the problem of solving hard core is transformed into the constraint satisfaction problem based on the dependency between agents,thereby an algorithm for solving hard core based on hypertree decomposition is presented and its effectiveness is verified by experiments.