ATL Strategic Reasoning Meets Correlated Equilibrium (IJCAI 2017)

Title: ATL Strategic Reasoning Meets Correlated Equilibrium
Authors: Xiaowei Huang and Ji Ruan

Abstract: This paper is motivated by analysing a Google self-driving car accident, i.e., the car hit a bus, with the framework and the tools of strategic reasoning by model checking. First of all, we find that existing ATL model checking may find a solution to the accident with irrational joint strategy of the bus and the car. This leads to a restriction of treating both the bus and the car as rational agents, by which their joint strategy is an equilibrium of certain solution concepts. Second, we find that a randomly-selected joint strategy from the set of equilibria may result in the collision of the two agents, i.e., the accident. Based on these, we suggest taking Correlated Equilibrium (CE) as agents' joint strategy and optimising over the utilitarian value which is the expected sum of the agents' total rewards. The language ATL is extended with two new modalities to express the existence of a CE and a unique CE, respectively. We implement the extension into a software model checker and use the tool to analyse the examples in the paper. We also study the complexity of the model checking problem.


Keywords: Knowledge Representation, Reasoning, and Logic: Automated Reasoning and Theorem Proving Agent-based and Multi-agent Systems: Coordination and cooperation Agent-based and Multi-agent Systems: Formal verification, validation and synthesis

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence Main track. Pages 1102-1108. https://doi.org/10.24963/ijcai.2017/153

BibTex:

@inproceedings{ijcai2017-153,
  author    = {Xiaowei Huang, Ji Ruan},
  title     = {ATL Strategic Reasoning Meets Correlated Equilibrium},
  booktitle = {Proceedings of the Twenty-Sixth International Joint Conference on
               Artificial Intelligence, {IJCAI-17}},
  pages     = {1102--1108},
  year      = {2017},
  doi       = {10.24963/ijcai.2017/153},
  url       = {https://doi.org/10.24963/ijcai.2017/153},
}

Normative Multiagent Systems: A Dynamic Generalization (IJCAI 2016)

Title: Normative Multiagent Systems: A Dynamic Generalization
Authors: Xiaowei Huang, Ji Ruan, Qingliang Chen, Kaile Su

Abstract: Social norms are powerful formalism in coordinating autonomous agents' behaviour to achieve certain objectives. In this paper, we propose a dynamic normative system to enable the reasoning of the changes of norms under different circumstances, which cannot be done in the existing static normative systems. We study two important problems (norm synthesis and norm recognition) related to the autonomy of the entire system and the agents, and characterise the computational complexities of solving these problems.

Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI-16), Pages 1123-1129, New York, USA, July 2016.

Conference version: http://www.ijcai.org/Proceedings/16/Papers/163.pdf

An extended version can be accessed here: http://arxiv.org/abs/1604.05086