Pareto Optimality in Abstract Argumentation

Iyad Rahwan, Kate LarsonAAAI 2008

Introduction

Abstract argumentation, a cornerstone of modern Artificial Intelligence research pioneered by Phan Minh Dung, provides a formal way to model reasoning by treating arguments as nodes in a directed graph. In these graphs, edges represent "attacks" or defeats between arguments. Traditionally, the goal has been to identify "extensions"—sets of arguments that can be collectively accepted based on logical criteria like consistency and self-defense. However, as argumentation is increasingly used in multi-agent systems involving self-interested participants (e.g., legal disputes or multi-stakeholder negotiations), purely logical criteria often fall short. This paper bridges the gap between formal logic and welfare economics by evaluating these frameworks through the lens of Pareto optimality.

The Challenge of Multiple Perspectives

A central issue in abstract argumentation is that a single graph can often support multiple valid logical interpretations, known as semantics. When agents have conflicting preferences over which arguments should "win," choosing between these interpretations becomes a social choice problem.

Figure 3: Comparison of different argument labelings (Grounded $L^G$, $L_1$, and $L_2$) and the legend for argument statuses.

As shown in Figure 3, different semantics lead to different labelings of arguments as "in" (accepted), "out" (rejected), or "undec" (undecided). While logic might permit all three outcomes ($L^G, L_1, L_2$), they have vastly different implications for the agents involved. Pareto optimality provides a criterion for selection: an outcome is Pareto optimal if no agent can be made better off without making at least one other agent worse off.

Modeling Agent Preferences

To apply economic principles, the authors define five distinct preference profiles for agents:

  1. Acceptability Maximizing: Agents seek to maximize the number of their own arguments labeled "in."
  2. Rejection Minimizing: Agents prioritize avoiding the "out" label for their arguments.
  3. Decisive: Agents dislike uncertainty and prefer labelings with the fewest "undecided" arguments.
  4. All-or-Nothing: Agents only derive utility if their entire set of arguments is accepted.
  5. Aggressive: Agents derive utility from seeing the arguments of others rejected.

Mapping Logic to Social Welfare

The core contribution of the paper is the mathematical proof linking these agent preferences to classical argumentation semantics.

Figure 5: A specific labeling $L_1$ for a five-argument graph, where arguments $\alpha_1, \alpha_3, \alpha_5$ are accepted.

For instance, the Grounded Extension ($L^G$ in Figure 3) is often seen as overly skeptical because it leaves many arguments undecided. However, the authors prove it is exactly the Pareto optimal outcome for populations of "rejection-minimizing" agents. Conversely, for "acceptability-maximizers," every Pareto optimal outcome is a Preferred Extension, but the reverse is not true: some preferred extensions may be Pareto dominated by others.

Population Type Pareto Optimality Result
Acceptability Maximizers Pareto optimal outcomes $\subseteq$ Preferred Extensions
Rejection Minimizers Pareto optimal outcome = Grounded Extension
Decisive Agents Pareto optimal outcomes $\subseteq$ Semi-stable Extensions
Aggressive Agents Pareto optimal outcomes $\subseteq$ Preferred Extensions

Conclusion and Future Directions

By introducing "welfare semantics," this research provides a principled way to break ties between competing logical conclusions. It suggests that the "best" logic depends on the social goals of the agent population. Future work remains to address the incentive problem—ensuring agents do not strategically hide or invent arguments to manipulate the outcome—and the computational complexity of finding these optimal sets in large-scale systems.

Summary updated

BibTeX
@inproceedings{rahwan2008pareto,
  author = {Iyad Rahwan and Kate Larson},
  title = {{Pareto Optimality in Abstract Argumentation}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2008},
}
Figure