TY - JOUR
T1 - A Bayesian optimal social law synthesizing mechanism for strategical agents
AU - Wu, Jun
AU - Cao, Jie
AU - Sun, Hongliang
AU - Wang, Chongjun
N1 - Publisher Copyright:
© 2022, Springer Science+Business Media, LLC, part of Springer Nature.
PY - 2022/10
Y1 - 2022/10
N2 - 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 (FPNP-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.
AB - 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 (FPNP-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.
KW - Logic
KW - Mechanism design
KW - Normative systems
KW - Optimization
KW - Social laws
UR - http://www.scopus.com/inward/record.url?scp=85137116836&partnerID=8YFLogxK
U2 - 10.1007/s10458-022-09576-4
DO - 10.1007/s10458-022-09576-4
M3 - Article
AN - SCOPUS:85137116836
SN - 1387-2532
VL - 36
JO - Autonomous Agents and Multi-Agent Systems
JF - Autonomous Agents and Multi-Agent Systems
IS - 2
M1 - 48
ER -