Seminar CogniGron - Prof. dr. D. Baumeister

Title: Computational Complexity of Incomplete Argumentation Frameworks

Abstract:
Computational Social Choice is an interdisciplinary research area at the interface between computer science and social choice theory. The use of mechanisms originating from social choice theory in computer science technologies, especially in artificial intelligence (e.g., recommender systems and multi-agent systems), emerges diverse research questions. A formal mathematical specification and analysis of these mechanisms is required and different forms of influence arise new importance since the outcome may have major consequences. When considering different forms of interference on decision-making processes, computational complexity plays a crucial role.

In this talk, I will give a short introduction into the field of computational social choice, with a special focus on the complexity of problems related to abstract argumentation. An argumentation may be modeled as a directed graph, representing arguments and attacks between them. One of the main tasks is then to identify sets of arguments having good properties, so-called extensions. In the context of AI technologies it is especially important to study dynamic setting. There may for example be uncertainty about the arguments or attacks. The computational complexity in different settings will be considered. I will conclude with some possible directions for future research.