Synthesizing Optimal Social Laws for Strategical Agents via Bayesian Mechanism Design

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 cost is known. It is easy to see that 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. 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 maximizes the expected profit for all input cost profiles; however, we can show that this mechanism is computational intractable; so, we finally find out a tractable constant-factor approximation mechanism. CCS Concepts •Computing methodologies → Multi-agent systems;