🤖 AI

Some Results about the Expressivity of Preference-Incomplete Structured Argumentation Frameworks

This paper investigates the expressive power of ASPIC $^+$ argumentation frameworks with uncertain preferences by demonstrating that most comparisons with abstract formalisms yield negative results, while also proposing and partially validating a conjecture regarding a non-trivial threshold for their expressivity.

Original authors: Antonio Yuste-Ginel

Published 2026-06-23

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Antonio Yuste-Ginel

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to figure out who is right in a debate. In the world of computer science and logic, this is called Argumentation. Usually, we have a set of arguments (like "It's raining, so take an umbrella") and a set of rules about how they fight each other (like "The umbrella argument defeats the 'stay dry' argument").

This paper explores what happens when we don't know all the rules of the fight. Specifically, it looks at a scenario where we are unsure about the preferences or hierarchy of the debaters.

Here is a breakdown of the paper's journey, using simple analogies:

1. The Setup: The "Uncertain Judge"

Think of a debate club. Usually, we know exactly who the judge prefers. If Argument A is stronger than Argument B, the judge always picks A.

But in this paper, the authors imagine a situation where the judge's preferences are uncertain. Maybe the judge might prefer A over B, or they might prefer B over A, or they might be undecided. The authors call this a Preference-Incomplete Framework.

The Goal: They want to know: "If we have this uncertainty about the judge's preferences, what kind of 'uncertainty' does that create in the final outcome?"
The Translation: They are trying to translate this complex, structured debate (with rules, premises, and judges) into a simpler, abstract map where we just see arrows pointing from one argument to another (defeats).

2. The Map Makers: Abstract Formalisms

To understand the uncertainty, the authors compare their "Uncertain Judge" model against other existing ways of mapping uncertainty. Think of these as different types of maps:

Simple Maps (def-IAFs): These maps say, "This arrow might exist, or it might not." It's a coin flip. Either the argument defeats the other, or it doesn't.
Connected Maps (dep-IAFs): These maps are smarter. They say, "If this arrow exists, then that arrow must also exist," or "At least one of these two arrows must exist." They have rules connecting the uncertainties.

3. The Big Discovery: The "No-Go" Zones

The authors ran a series of tests to see if their "Uncertain Judge" model could be perfectly copied by these simpler maps. The results were mostly negative (meaning "No, you can't do that").

Here are the main findings, translated:

You can't use a Simple Map: You cannot simply say "maybe this defeat happens, maybe it doesn't" to capture the uncertainty of a judge's preferences. The uncertainty in preferences is too complex; it creates patterns of "maybe" that a simple coin-flip map can't replicate.
You can't use a "Either/Or" Map: Even if you allow maps that say "Either Arrow A exists OR Arrow B exists," it's still not enough. The "Uncertain Judge" creates specific logical dependencies that these maps miss.
You can't use a "If-Then" Map: Similarly, maps that say "If Arrow A exists, then Arrow B must exist" are also insufficient on their own.
The Reverse is also true: Interestingly, the "Uncertain Judge" model cannot create every possible type of simple uncertainty either. There are some weird, abstract scenarios (like a single argument defeating itself) that the Judge model simply cannot produce.

The Metaphor: Imagine trying to describe a specific flavor of ice cream (Uncertain Preferences) using only a list of ingredients (Simple Maps). You can't do it perfectly because the way the ingredients mix creates a unique texture that the list doesn't capture. Conversely, the ice cream can't make every possible flavor combination either.

4. The "Maybe" Zone: A New Conjecture

Since the simple maps failed, the authors looked at a more complex map type called Disjunctive-Implicative Maps. These are maps that allow for both "Either/Or" rules and "If/Then" rules.

The Guess: The authors strongly suspect (conjecture) that their "Uncertain Judge" model can be perfectly translated into these complex maps.
The Status: They haven't proven it 100% yet, but they have taken the first steps. They found that the uncertainty created by the judge follows specific patterns (like "If the judge prefers A over B, then A defeats B") that fit neatly into this complex map structure.

Summary

The paper is essentially a study of translation limits.

The Problem: We have a complex way of modeling uncertainty (uncertain judges in debates).
The Test: Can we translate this into simpler, abstract models of uncertainty?
The Result: No, not with the simple models. The uncertainty is too nuanced.
The Hope: It might be translatable into a slightly more complex model that mixes "Either/Or" and "If/Then" logic, but the authors are still working on the final proof.

The paper concludes that to understand uncertainty in structured arguments, we need to stop treating it as a simple coin flip and start treating it as a web of connected possibilities.

Technical Summary: Expressivity of Preference-Incomplete Structured Argumentation Frameworks

Problem Statement

The paper addresses the expressivity of Preference-Incomplete Structured Argumentation Frameworks (pref-ISAFs), a formalism within the ASPIC+ framework where preference relations between arguments are partially uncertain. While uncertainty in abstract argumentation is often modeled via Incomplete Argumentation Frameworks (IAFs) where arguments or defeats are uncertain, pref-ISAFs introduce a specific type of uncertainty: the uncertainty of the preference ordering itself.

The core research question is: What kind of abstract defeat-uncertainty is generated by preference-uncertainty? Specifically, the authors investigate whether the set of abstract completions (scenarios of possible defeats) generated by pref-ISAFs can be captured by existing abstract formalisms for defeat-uncertainty, such as:

def-IAFs: IAFs with uncertain defeats but no dependencies between them.
dep-IAFs: IAFs with uncertain defeats and logical dependencies (e.g., disjunctive or implicative constraints) between them.
Subclasses: Disjunctive (dis-IAFs) and Implicative (imp-IAFs) IAFs.

Methodology

The authors employ a comparative expressivity analysis based on the notion of completions.

Formal Definitions:
- pref-ISAF: A structured framework where the preference relation $\leq$ is split into certain ( $\leq_F$ ) and uncertain ( $\leq_?$ ) components. A preference-completion is any framework where $\leq_?$ is resolved.
- Abstract Completions: The set of abstract Argumentation Frameworks (AFs) associated with all possible preference-completions of a pref-ISAF.
Equivalence Criterion: Two sets of AFs (from different formalisms) are considered equivalent if they are isomorphic regarding their sets of arguments and defeat relations across all completions.
Expressivity Relation ( $\preceq$ ): Formalism $X$ is at least as expressive as $Y$ ( $Y \preceq X$ ) if for every $Y \in Y$ , there exists an $X \in X$ such that their sets of completions are equivalent.
Analysis: The paper constructs specific counterexamples (witnesses) to test whether pref-ISAFs can be simulated by simpler abstract formalisms and vice versa.

Key Contributions and Results

1. Negative Expressivity Results

The paper provides several negative results, demonstrating that pref-ISAFs cannot be fully captured by simpler abstract formalisms, nor can they capture all forms of abstract defeat-uncertainty.

pref-ISAFs $\not\preceq$ def-IAFs: As previously shown in [17], standard IAFs with uncertain defeats (without dependencies) are insufficient. Uncertain preferences can generate sets of completions that are not isomorphic to any set of completions of a def-IAF.
pref-ISAFs $\not\preceq$ dis-IAFs: Even allowing for disjunctive dependencies (where if one defeat exists, its symmetric counterpart must not, or vice versa) is insufficient. The authors use a witness from Example 3 to show that pref-ISAFs encode dependencies that dis-IAFs cannot replicate.
pref-ISAFs $\not\preceq$ imp-IAFs: Similarly, implicative dependencies alone are insufficient. The paper notes that while uncertain rules and premises can be captured by implicative IAFs [16], uncertain preferences encode a mix of implicative and disjunctive dependencies that imp-IAFs cannot handle.
def-IAFs $\not\preceq$ pref-ISAFs: Conversely, pref-ISAFs are not expressive enough to simulate all types of abstract defeat-uncertainty. The authors provide a witness (a single argument with a self-defeat) that can be modeled by a def-IAF but cannot be generated by any pref-ISAF. This is because the structure of ASPIC+ arguments (specifically the relationship between premises, rules, and preferences) imposes constraints that prevent the generation of certain "empty" defeat scenarios required by simple def-IAFs.

Corollaries: Consequently, pref-ISAFs are not equivalent to dis-imp-IAFs (disjunctive-implicative) or general dep-IAFs in a bidirectional sense, though they are subsumed by dep-IAFs (i.e., pref-ISAFs $\preceq$ dep-IAFs).

2. Positive Results and Conjectures

While negative results dominate, the paper establishes a positive, non-trivial threshold for expressivity:

Proposition 7: The authors define specific sets of dependencies ( $\Delta_{OR}$ $Δ_{O R}$ and $\Delta_{IMPLY}$ $Δ_{I M P L Y}$ ) derived from the structure of a pref-ISAF. They prove that:
- Certain defeats are fixed ( $D_F$ ) across all completions.
- Uncertain defeats ( $D_?$ ) arise only under specific preference conditions.
- The set of completions satisfies specific disjunctive constraints (if $X$ defeats $Y$ , then $Y$ cannot defeat $X$ in the same completion, or vice versa) and implicative constraints (if $X$ defeats $Y$ , and $Y$ is a sub-argument of $W$ , then $X$ defeats $W$ ).
Conjecture 1: Based on the analysis of Proposition 7 and the failure of counterexamples, the authors conjecture that pref-ISAFs are at least as expressive as dis-imp-IAFs ( $pref\text{-}ISAFs \preceq dis\text{-}imp\text{-}IAFs$ ). This suggests that the uncertainty generated by preferences can be fully captured by abstract frameworks allowing both disjunctive and implicative dependencies between defeats.

Significance and Claims

The paper claims to provide a rigorous characterization of the expressive power of uncertain preferences in structured argumentation. Its significance lies in:

Clarifying Limits: It demonstrates that abstract formalisms relying solely on uncertain defeats (def-IAFs) or simple dependency types (dis-IAFs, imp-IAFs) are theoretically insufficient to model the uncertainty arising from preference incompleteness in ASPIC+.
Identifying Complexity: It highlights that preference-uncertainty generates a specific, complex pattern of defeat-uncertainty involving both disjunctive and implicative constraints, distinguishing it from uncertainty in rules or premises.
Future Direction: The paper modestly positions its main contribution as the formulation of Conjecture 1. Proving this conjecture would establish a precise "non-trivial upper threshold" for the expressivity of pref-ISAFs, linking structured argumentation with uncertain preferences to the well-studied fragment of disjunctive-implicative IAFs. This connection is noted to potentially offer insights into the computational complexity of reasoning with uncertain preferences.

The authors explicitly state that they have not yet proven the conjecture but have examined substantial potential counterexamples without success, making it the primary avenue for future work. They also suggest future comparisons with uncertainty in contrary functions and naming conventions.