🤖 AI

Tenability and Weak Semantics: Modeling Non-uniform Defense -- Extended Version

This paper introduces "tenability," a family of dialogue-based argumentation semantics that relax the uniform defense requirement of traditional weak semantics by modeling strategic, non-uniform defense through monotone commitment games, and it establishes the computational complexity and theoretical relationships of its three variants (static, standard, and strong) against existing benchmarks.

Original authors: Uri Andrews, Luca San Mauro, John Spoerl

Published 2026-05-06

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Uri Andrews, Luca San Mauro, John Spoerl

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

The Big Idea: The "One-Size-Fits-All" Problem

Imagine you are in a debate. In traditional argumentation theory (the rules used by computers to decide what is "true"), there is a strict rule: To win, you must have one single, perfect story that defends you against every possible attack at the same time.

The authors of this paper call this "Uniform Defense."

They argue this is too rigid. In real life, if someone attacks you with two different, contradictory accusations, you don't need one story that explains both. You just need to be able to say, "If you accuse me of X, I have a defense for X. If you accuse me of Y, I have a different defense for Y." You don't need to hold both defenses in your head simultaneously; you just need to be ready to switch depending on what the opponent actually says.

The paper introduces a new concept called Tenability. It asks: Can you maintain your position against any consistent line of attack, even if your answer changes depending on which attack you face?

The Three Test Cases (The "Why")

To prove why the old rules are too strict, the authors use three scenarios (like test drives for a new car):

1. The Self-Defeating Attack (The "Cry Wolf" Scenario)

The Setup: You are accused by someone who is clearly lying or attacking themselves.
Old Rule: You still have to defend against them, even though their attack is nonsense.
New Rule (Tenability): If the attacker is self-defeating, they aren't a "real" threat. You don't need to waste energy defending against a lie that contradicts itself. Tenability says you are safe here.

2. The Floating Assignment (The "Impossible Choice" Scenario)

The Setup: Two people accuse you. They are enemies of each other (they can't both be telling the truth).
- Accuser A says: "You stole the car."
- Accuser B says: "You stole the boat."
- To defend against A, you need evidence that supports B. To defend against B, you need evidence that supports A.
The Problem: You can't hold both defenses at once because they contradict each other.
Old Rule: Since you can't have one story that covers both, you lose.
New Rule: This is where Tenability says "No." If the accusers are enemies, they can't team up to attack you in a single, consistent line. If you can't answer either one on its own, you are in trouble. But if you can answer them individually, you are fine. The old rules failed here because they forced you to answer both at once.

3. Disjunctive Reinstatement (The "Choose Your Own Adventure" Scenario)

The Setup: Two enemies accuse you.
- Enemy 1 attacks you with a lie. You have a specific counter-argument (C1) that defeats Enemy 1.
- Enemy 2 attacks you with a different lie. You have a different counter-argument (C2) that defeats Enemy 2.
- Crucial Point: C1 and C2 are enemies. You can't use both at the same time.
Old Rule: You lose. Why? Because there is no single "Master Story" that includes you, C1, and C2 all working together. The old rules demand you have one perfect shield that blocks everything simultaneously.
New Rule (Tenability): You win! Why? Because the enemies can't attack you with both lies at the same time (since the lies contradict each other).
- If the opponent picks Enemy 1, you use C1.
- If the opponent picks Enemy 2, you use C2.
- You don't need to hold both C1 and C2 in your pocket at the same time. You just need to be ready to pull the right one out when the opponent makes their move.

The Three Levels of Tenability

The authors define three versions of this new rule, like different levels of difficulty in a video game:

Static Tenability (The "Snapshot"):
- Imagine the opponent throws a single punch. Can you find a shield that blocks it?
- Analogy: It's like checking a map. "If I go this way, is there a path?" It's a one-time check. It's simple but doesn't account for a long, back-and-forth fight.
Strong Tenability (The "Master vs. Novice"):
- This is a game. You (the Proponent) and your opponent take turns.
- The Catch: You must defend your arguments forever. But the opponent? They don't have to defend their own arguments. They can throw out wild, unsupported claims, and you still have to have an answer for them.
- Analogy: It's like a debate where you have to be perfect, but your opponent is allowed to be messy and inconsistent. You win if you can keep answering their messy questions without falling apart.
Tenability (The "Master vs. Master"):
- This is the most realistic version. Both you and your opponent must play "fair."
- If your opponent throws a new argument, they must also be able to defend that argument if you attack it.
- Analogy: This is a real courtroom or a serious debate. Both sides have to stick to their guns. If the opponent changes their story, they have to own the new story. You win if you can navigate this fair fight, switching your defenses as needed, without ever getting stuck.

The "Master vs. Ignoramus" Effect

The paper uses a funny phrase to describe the old way of thinking: Master vs. Ignoramus.

The Master (You): Must have a perfect, consistent story for everything.
The Ignoramus (Opponent): Can throw out any random, contradictory nonsense, and you still have to answer it all with one perfect story.

The authors say this is unfair. In the real world, if an opponent is inconsistent, they aren't a serious threat. Tenability fixes this by saying: "You only have to answer the consistent lines of attack. If the opponent tries to mix two contradictory attacks, we ignore the mix."

The Results (The "Scoreboard")

The authors did some heavy math to see how hard it is for computers to figure out if a position is "Tenable."

Static Tenability: Hard to calculate, but manageable (similar to checking complex logic puzzles).
Strong Tenability & Tenability: Very hard to calculate (similar to solving complex strategy games like Chess or Go).
The Good News: Even though it's hard, it's not impossible for computers to do. It's on the same level of difficulty as other advanced argumentation methods we already use.

Summary

The paper argues that defensibility shouldn't be about having one perfect, all-encompassing story. Instead, it should be about having a flexible strategy.

If you can answer every consistent attack the opponent might make—by switching your defense depending on which attack they choose—you are "Tenable." You don't need to be able to answer every possible attack at the exact same time; you just need to be ready for whatever they actually throw at you.

Technical Summary: Tenability and Weak Semantics

Problem Statement
In Dung-style abstract argumentation frameworks (AFs), standard semantics (e.g., complete, grounded, preferred) rely on admissibility, which requires a set of arguments to be internally consistent and capable of defending every member against all relevant attacks simultaneously via a single, uniform stance. This "uniform witness" requirement is often overly conservative in the presence of pathological patterns, such as self-defeating arguments or odd cycles, where an attack may fail to constitute a serious challenge because its source is incoherent.

While existing "weak semantics" (e.g., weak admissibility, cogency-based approaches, weakly complete semantics) relax admissibility by filtering out certain attacks (like self-defeating ones), they largely retain the structural commitment to a uniform defense. They require a single extension or labeling that adequately counters all deemed-relevant attacks at once. The authors argue this is insufficient for scenarios where defensibility is inherently strategic: the appropriate reply to a challenge may depend on the specific line of attack the opponent commits to, and mutually incompatible challenges need not be met jointly by one fixed position.

Methodology
The paper introduces tenability, a family of dialogue-based semantics that formalize non-uniform defense. The core conceptual shift is from "there exists one stance answering all relevant attacks" to "for every consistent line of attack, there exists an appropriate response."

The methodology employs monotone commitment games over finite conflict-free moves. The authors define three variants of tenability, differing in the obligations imposed on the disputants (Proponent and Opponent):

Static Tenability: A one-shot strategic check. A set $A$ is statically tenable if for every finite conflict-free set $B$ attacking $A$ , there exists a conflict-free extension $C \supseteq A$ that is "as cogent as" $B$ (i.e., $C$ counterattacks every element of $B$ that attacks $C$ ). This captures the idea that a position has a reply for every consistent incoming attack, but does not account for dynamic escalation.
Strong Tenability: A dynamic dispute where the Proponent must maintain a winning strategy. The game proceeds in alternating moves where the Proponent extends her position to counter the Opponent's attack. Crucially, the Opponent is not required to defend their own arguments (a "Master vs. Novice" dynamic). The Proponent wins if she can indefinitely defend her initial position or force the Opponent into a position where they cannot play a strictly more cogent move.
Tenability: A refined dynamic dispute modeling a "Master vs. Master" debate. Both players must argue in good faith, meaning both must defend the positions they introduce. The game requires that every move be "as cogent as" the preceding move, and the Opponent's move must be "more cogent" (strictly better) than the Proponent's previous move to constitute a valid challenge. This prevents "attack switching" where an opponent introduces incompatible arguments without defending them.

Key Contributions

Formalization of Non-Uniform Defense: The paper provides the first formal semantics where the defense against a set of attacks can vary depending on the specific consistent subset of attacks presented by the opponent.
Benchmark Patterns: The authors motivate their definitions using three specific benchmark patterns (Figure 1):
- Self-defeating Attack (S): Tenability correctly accepts arguments attacked only by self-defeating sets, unlike strict admissibility.
- Floating Assignment (F): Tenability correctly rejects arguments where every consistent singleton attack is unanswerable, even if the set of all attackers is inconsistent.
- Disjunctive Reinstatement (U): Tenability accepts arguments where no single uniform defense exists, but a specific defense exists for each consistent line of attack (e.g., $c_1$ defends against $b_1$ , $c_2$ defends against $b_2$ , but $c_1$ and $c_2$ are incompatible).
Hierarchy and Properties: The paper establishes a strict hierarchy: Strong Tenability $\implies$ Tenability $\implies$ Static Tenability.
- Tenability notions are shown to be downward closed (if $A$ is tenable, any subset $X \subseteq A$ is tenable), a property distinct from many extension-based semantics.
- They are compatible with the grounded extension (if $A$ is tenable, $A \cup G$ is tenable).
Complexity Analysis:
- Deciding Static Tenability is $\Pi^P_2$ -complete (comparable to skeptical acceptance in preferred semantics).
- Deciding Tenability and Strong Tenability is PSPACE-complete (comparable to weak admissibility).

Results

Separation from Existing Semantics: The paper proves that tenability notions are distinct from and generally weaker than Cogency and Cyclic Cogency semantics. While Cogency requires a fixed singular line of defense, tenability allows the defense to change based on the attack.
Inclusion Relations: The authors map the landscape of weak semantics (Figure 6), showing that:
- Cogent extensions are strongly tenable.
- Strongly tenable sets are tenable.
- Tenable sets are statically tenable.
- Tenable sets are contained within Weakly Complete extensions (though not necessarily equal).
- Weakly Admissible sets are contained within Weakly Complete extensions.
Infinite Frameworks: The definitions are extended to infinite frameworks. The authors prove that the existence of winning strategies for Pro or Opp is absolute and does not depend on the model of set theory used (unlike some general infinite games). They also demonstrate that for infinite sets, static tenability of a set does not imply the static tenability of its finite subsets, and vice versa, highlighting the necessity of considering infinite commitments.

Significance
The paper claims that tenability adds a new axis to the weak-semantics landscape by making strategic non-uniformity explicit at the abstract level. It preserves the defense-based intuition of Dung's work while relaxing the requirement for a single, uniform witness.

The authors position tenability not as a standalone model for practical reasoning in rich domains, but as a dialectical evaluation layer. It is particularly suited for:

Legal and Evidential Reasoning: Where debates involve shifting burdens of proof and where a party may need to tailor rebuttals to specific lines of attack rather than providing a single all-encompassing defense against mutually incompatible accusations.
Interactive Explanation: Systems can justify maintaining a position by exhibiting a defense strategy tailored to a user's specific, reasonable objections, without committing to a single extension that anticipates all possible (and potentially incompatible) challenges.

The work suggests that tenability is most useful when combined with established modeling layers for structure, priorities, and proof standards, rather than replacing them. The authors identify future work in extending tenability to Bipolar Argumentation Frameworks (BAFs) and structured formalisms like ASPIC+, where the distinction between attack and support would require rethinking the commitment protocols.