A Bayesian optimal social law synthesizing mechanism for strategical agents

One of the effective and well studied approaches for coordinating multiagent systems is to synthesize social laws which restrict the behavior of individual agents. We show that when rational behavior of the agents and private information are considered, the optimal social law synthesizing problem naturally evolves into a setting which can be handled by the framework of algorithmic mechanism design. We focus on the Bayesian case in this paper, that is, the probability distribution of each agent’s private cost is known by the public. In this case, our problem closely relates to path/spanning-tree auctions and Myerson’s optimal auction mechanism, but the optimization objective is new, that is, we focus on profit maximization instead of payment maximization in a reverse auction, and as far as we know in this setting no existing mechanism can be directly applied. By studying this problem: We further extend the logic-based framework of social law optimization problem to the strategic case, and show that it becomes a new problem of algorithmic mechanism design; We find out a mechanism that is incentive compatible, individually rational and maximize the expected profit for all input cost profiles; However, we can show that this mechanism is computational intractable (FP^NP-complete); So, we try to specify Computation Tree Logic semantics as a set of linear-integer constraints, design a Integer-Linear Programming based algorithm for computing the proposed mechanism, enabling it to be handled by current ILP solvers, and finally find out a tractable 2-approximation mechanism.