On the Complexity of Probabilistic Abstract Argumentation

Fazzinga, Bettina; Flesca, Sergio; Parisi, Francesco

On the Complexity of Probabilistic Abstract Argumentation

Bettina Fazzinga, Sergio Flesca, Francesco Parisi

Download BibTeX Cite

Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Pages 898-903.

Abstract

Probabilistic abstract argumentation combines Dung's abstract argumentation framework with probability theory in order to model uncertainty in argumentation. In this setting, we address the fundamental problem of computing the probability that a set of arguments is an extension according to a given semantics. We focus on the most popular semantics (i.e., admissible, stable, complete, grounded, preferred, ideal), and show the following dichotomy result: computing the probability that a set of arguments is an extension is either PTIME or FP#P-complete depending on the semantics adopted. Our PTIME results are particularly interesting, as they hold for some semantics for which no polynomial-time technique was known so far.

Bettina Fazzinga, Sergio Flesca, and Francesco Parisi. 2013. On the Complexity of Probabilistic Abstract Argumentation. In Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13. IJCAI, 898–903. https://ijcai.org/proceedings/2013/138

@inproceedings{ijcai2013p138,
  title     = {On the Complexity of Probabilistic Abstract Argumentation},
  author    = {Fazzinga, Bettina and Flesca, Sergio and Parisi, Francesco},
  booktitle = {Proceedings of the Twenty-Third International Joint Conference on
               Artificial Intelligence, {IJCAI-13}},
  publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
  editor    = {Francesca Rossi},
  pages     = {898--903},
  year      = {2013},
  month     = {8},
  url       = {https://ijcai.org/proceedings/2013/138},
}

TY  - CPAPER
TI  - On the Complexity of Probabilistic Abstract Argumentation
AU  - Fazzinga, Bettina
AU  - Flesca, Sergio
AU  - Parisi, Francesco
T2  - Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13
PB  - AAAI Press / International Joint Conferences on Artificial Intelligence
PY  - 2013
SP  - 898
EP  - 903
UR  - https://ijcai.org/proceedings/2013/138
ER  -