TL;DR
This paper tackles the question of whether diverse individual viewpoints on arguments, represented as abstract argumentation frameworks (AFs), can be explained by a single underlying "master" framework and individual value-based preferences. They introduce a formal model and explore algorithmic questions, identifying both tractable and intractable scenarios for this "rationalisation" problem, which is crucial for understanding how to aggregate or interpret collective arguments.
What Problem Does This Paper Address?
In artificial intelligence, abstract argumentation frameworks (AFs) are a powerful tool for modeling reasoning, representing arguments as nodes in a graph and attacks as directed edges. When multiple agents interact, each might have their own AF reflecting their individual understanding of the arguments and their relationships. A key challenge arises: how can we explain the differences between these individual AFs? This paper proposes that these differences can be rationalized by assuming a common underlying structure (a master AF) and individual agents' personal preferences over certain values associated with the arguments. The core problem is to determine if a given profile of individual AFs can be explained by such a model, and under what conditions this explanation is computationally feasible. This is important for understanding the coherence of collective reasoning and for developing robust aggregation mechanisms.
Methods
The authors build upon the value-based argumentation framework proposed by Bench-Capon. Their approach formalizes the "rationalisation" problem: given a profile of $n$ argumentation frameworks $(AF_1, \dots, AF_n)$, one for each agent, can this profile be explained by a single master argumentation framework (Arg, $\rightarrow$), a set of values (Val), a mapping from arguments to values (val: Arg $\rightarrow$ Val), and a profile of individual preference orders over values $(\geq_1, \dots, \geq_n)$? Specifically, for each agent $i$, their observed AF ($AF_i = \langle Arg, \Rightarrow_i \rangle$) must be derivable from the master framework by removing attacks $A \rightarrow B$ where agent $i$ strictly prefers the value of $B$ over the value of $A$ (i.e., $val(B) >_i val(A)$).
They then investigate algorithmic questions related to this rationalisation problem, considering various constraints such as fixing the master attack relation, fixing the value-argument mapping, bounding the number of values, or requiring complete preference orders. They analyze both single-agent and multi-agent scenarios, identifying conditions for tractability and intractability.
Datasets
Not discussed in the paper. The paper focuses on theoretical modeling and algorithmic analysis rather than empirical evaluation on specific datasets.
Key Insights and Ideas
- Value-Based Rationalisation: The core idea is that differing argumentation frameworks among agents can be explained by a shared underlying structure and individual preferences over values. This provides a principled way to understand disagreement.
- Single-Agent Rationalisation is Often Tractable: For a single agent, rationalising their observed AF against a given master AF and value assignment is often computationally straightforward, involving checks for acyclicity of removed attacks.
- Multi-Agent Rationalisation is More Complex: Even without constraints, a profile of AFs from multiple agents might not be rationalisable. Example 5 demonstrates a simple case where disagreement on attacks, even with flexible preferences, can lead to an unrationalisable profile.
- Constraints Drive Complexity: The computational complexity of rationalisation heavily depends on the constraints imposed. NP-completeness emerges when bounding the number of values in the multi-agent case, highlighting the trade-off between expressiveness and computational feasibility.
- Understanding Disagreement: The failure of rationalisation can provide valuable insights into the nature and source of disagreement between agents, pointing towards fundamental differences in their value systems or interpretations.
Key Results
- Single-Agent Case:
- Without constraints, any single AF is rationalisable.
- With a fixed master attack relation, rationalisability can be checked efficiently using three conditions related to the acyclicity of removed attacks.
- With a fixed master attack relation, a bound $k$ on the number of values, and complete preferences, the problem is solvable in polynomial time by reduction to integer programming.
- Multi-Agent Case:
- A profile of AFs is not always rationalisable, even without constraints.
- The general multi-agent rationalisation problem with a bound $k$ on the number of values is NP-complete.
- Polynomial-time solvability is achieved when the number of values is very large relative to the number of arguments.
Limitations and Future Work
- Limitations:
- The NP-completeness result for the multi-agent case with a bound on values suggests that efficient algorithms may not exist for all scenarios.
- The paper acknowledges that the current proof of NP-completeness heavily relies on agents having different sets of arguments, leaving open the question of intractability when all agents share the same argument set.
- The tractability of the single-agent case with a bound on values and incomplete preferences remains an open question.
- Future Work:
- Investigate the complexity of the multi-agent case with exactly two values.
- Explore the multi-agent case with a bound on values when all agents share the same set of arguments.
- Explore alternative models of rationalisation beyond the value-based approach.
- Apply the rationalisation framework to richer models of argumentation that consider the internal structure of arguments, not just abstract attacks.
- Develop efficient algorithms for scenarios where rationalisation is computationally feasible.
Summary updated