How Hard to Tell? Complexity of Belief Manipulation Through Propositional Announcements

Eiter, Thomas; Hunter, Aaron; Schwarzentruber, François

doi:10.24963/ijcai.2021/257

How Hard to Tell? Complexity of Belief Manipulation Through Propositional Announcements

Thomas Eiter, Aaron Hunter, Francois Schwarzentruber

Download BibTeX Cite

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence. Main Track. Pages 1866-1872.

https://doi.org/10.24963/ijcai.2021/257

Keywords

Knowledge Representation and Reasoning: Belief Change
Knowledge Representation and Reasoning: Reasoning about Knowledge and Belief

Abstract

Consider a set of agents with initial beliefs and a formal operator for incorporating new information. Now suppose that, for each agent, we have a formula that we would like them to believe. Does there exist a single announcement that will lead all agents to believe the corresponding formula? This paper studies the problem of the existence of such an announcement in the context of model-preference definable revision operators. First, we provide two characterisation theorems for the existence of announcements: one in the general case, the other for total partial orderings. Second, we exploit the characterisation theorems to provide upper bound complexity results. Finally, we also provide matching optimal lower bounds for the Dalal and Ginsberg operators.

Thomas Eiter, Aaron Hunter, and François Schwarzentruber. 2021. How Hard to Tell? Complexity of Belief Manipulation Through Propositional Announcements. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21. IJCAI, 1866–1872. https://doi.org/10.24963/ijcai.2021/257

@inproceedings{ijcai2021p257,
  title     = {How Hard to Tell? Complexity of Belief Manipulation Through Propositional Announcements},
  author    = {Eiter, Thomas and Hunter, Aaron and Schwarzentruber, François},
  booktitle = {Proceedings of the Thirtieth International Joint Conference on
               Artificial Intelligence, {IJCAI-21}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Prof. Zhi-Hua Zhou},
  pages     = {1866--1872},
  year      = {2021},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2021/257},
  url       = {https://doi.org/10.24963/ijcai.2021/257},
}

TY  - CPAPER
TI  - How Hard to Tell? Complexity of Belief Manipulation Through Propositional Announcements
AU  - Eiter, Thomas
AU  - Hunter, Aaron
AU  - Schwarzentruber, François
T2  - Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2021
SP  - 1866
EP  - 1872
DO  - 10.24963/ijcai.2021/257
UR  - https://doi.org/10.24963/ijcai.2021/257
ER  -