KR2020Proceedings of the 17th International Conference on Principles of Knowledge Representation and ReasoningProceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning

Rhodes, Greece. September 12-18, 2020.

Edited by

ISSN: 2334-1033
ISBN: 978-0-9992411-7-2

Sponsored by
Published by

Copyright © 2020 International Joint Conferences on Artificial Intelligence Organization

Explainable Acceptance in Probabilistic Abstract Argumentation: Complexity and Approximation

  1. Gianvincenzo Alfano(DIMES Department, University of Calabria)
  2. Marco Calautti(DIMES Department, University of Calabria, DISI Department, University of Trento)
  3. Sergio Greco(DIMES Department, University of Calabria)
  4. Francesco Parisi(DIMES Department, University of Calabria)
  5. Irina Trubitsyna(DIMES Department, University of Calabria)


  1. Argumentation-General


Recently there has been an increasing interest in probabilistic abstract argumentation, an extension of Dung's abstract argumentation framework with probability theory. In this setting, we address the problem of computing the probability that a given argument is accepted. This is carried out by introducing the concept of probabilistic explanation for a given (probabilistic) extension. We show that the complexity of the problem is FP^#P-hard and propose polynomial approximation algorithms with bounded additive error for probabilistic argumentation frameworks where odd-length cycles are forbidden. This is quite surprising since, as we show, such kind of approximation algorithm does not exist for the related FP^#P-hard problem of computing the probability of the credulous acceptance of an argument, even for the special class of argumentation frameworks considered in the paper.