Graph Models for Rational Social Interaction - PhD Verteidigung

The first Part of this thesis is devoted to combinatorial aspects of Dung‘s Argumentation Frameworks (AFs) related to computational issues. I prove that any AF can be syntactically augmented into a normal form preserving the semantic properties of the original arguments, by using a cubic time rewriting technique. I introduce polyhedral labellings for an AF, which is a polytope with the property that its integral points are exactly the incidence vectors of specific types of extensions. Also, a new notion of acceptability of arguments is considered – deliberative acceptability – and I provide its time computational complexity analysis.
In the second Part, I introduce a novel graph-based model for aggregating preferences. By using graph operations to describe properties of the aggregators, axiomatic characterizations of aggregators corresponding to usual majority or approval & disapproval rule are given. Integrating AF‘s semantics into our model provides a novel qualitative approach to classical social choice: argumentative aggregation of individual preferences. Also, a functional framework abstracting many-to-many two-sided markets is considered: the study of the existence of a Stable Choice Matching in a Bipartite Choice System is reduced to the study of the existence of Stable Common Fixed Points of two choice functions. A generalization of the Gale-Shapley algorithm is designed and, in order to prove its correctness, new characterization of path independence choice functions is given.
Finally, in the third Part, we extend Dung’s AFs to Opposition Frameworks, reducing the gap between Structured and Abstract Argumentation. A guarded attack calculus is developed, giving proper generalizations of Dung’s extensions.