Strategic Argumentation is NP-Complete
arXiv:1312.4287v123 citations
Originality Synthesis-oriented
AI Analysis
This addresses a computational problem for researchers in AI and argumentation theory, but it is incremental as it applies known complexity results to a specific formalism.
The paper tackles the complexity of strategic decision-making in dialogue games, showing that determining the optimal move at each turn is NP-complete.
In this paper we study the complexity of strategic argumentation for dialogue games. A dialogue game is a 2-player game where the parties play arguments. We show how to model dialogue games in a skeptical, non-monotonic formalism, and we show that the problem of deciding what move (set of rules) to play at each turn is an NP-complete problem.