Graph Models for Rational Social Interaction

Abstract

A fundamental issue in multi-agent systems is to extract a consensus from a group of agents with different perspectives. Even if the bilateral relationships (reflecting the outcomes of disputes, product comparisons, or evaluation of political candidates) are rational, the collective output may be irrational (e.g., intransitivity of group preferences). This motivates AI’s research for devising social outcomes compatible with individual positions. Frequently, such situations are modeled as graphs. While the preponderance of formal theoretical studies of such graph based-models has addressed semantic concerns for defining a desirable output in order to formalize some high-level intuition, results relating to algorithmic and computational complexity are also of great significance from the computational point of view. The first Part of this thesis is devoted to combinatorial aspects of Argumentation Frameworks related to computational issues. These abstract frameworks, introduced by Dung in 1995, are directed graphs with nodes interpreted as arguments and the directed edges as attacks between the arguments. By designing a conflict-resolution formalism to make distinction among acceptable and unacceptable arguments, Dung initiated an important area of research in Artificial Intelligence. I prove that any argumentation framework 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 argumentation frameworks, which is a polytope with the property that its integral points are exactly the incidence vectors of specific types of Dung’s outcome. Also, a new notion of acceptability of arguments is considered – deliberative acceptability – and I provide it’s time computational complexity analysis. This part extends and improves some of the results from the my Master thesis. 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 Dung’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, a new characterization of path independence choice functions is given. Finally, in the third Part, we extend Dung’s Argumentation Frameworks to Opposition Frameworks, reducing the gap between Structured and Abstract Argumentation. A guarded attack calculus is developed, giving proper generalizations of Dung’s extensions.

Ein grundlegendes Problem von Multiagentensystemen ist, eine Gruppe von Agenten mit unterschiedlichen Perspektiven zum Konsens zu bringen.W¨ahrend die bilaterale Ergebnisse von Rechtsstreitigkeiten, Produktvergleichen sowie die Bewertung von politischen Kandidaten wiederspiegelnden Beziehungen rational sein sollten, k¨onnte der kollektive Ausgang irrational sein z.B. durch die Intransitivit¨at von Pr¨aferenzen der Gruppe. Das motiviert die KI-Forschung zur Entwicklung von sozialen Ergebnissen, welche mit individuellen Einstellungen kompatibel sind. H¨aufig werden solche Situationen als Graphen modelliert. W¨ahrend die meisten formalen theoretischen Studien von Graphmodellen sich mit semantischen Aspekten f¨ur die Definition eines w¨unschenswerten Ausgangs zur Formalisierung auf hohem Intuitionsniveau besch¨aftigen, ist es ebenfalls von großer Bedeutung, die Komplexit¨at von Algorithmen und Berechnungen zu verstehen. Der erste Teil der vorliegenden Arbeit widmet sich den kombinatorischen Aspekten von Argumentation Frameworks im Zusammenhang mit rechnerischen Fragen. Diese von Dung in 1995 eingef ¨uhrten abstrakten Frameworks sind gerichtete Graphen mit als Argumenten zu interpretierenden Knoten, wobei die gerichteten Kanten Angriffe zwischen den Argumenten sind. Somit hat Dung mit seiner Gestaltung eines Konfliktl¨osungsformalismus zur Unterscheidung zwischen akzeptablen und inakzeptablen Argumenten f¨ur einen wichtigen Bereich von Forschung in KI den Grundstein gelegt. Die Verfasserin hat bewiesen, dass jedes Argumentation Framework sich in einer die semantischen Eigenschaften der originalen Argumente bewahrenden normalen Form syntaktisch erweitern l¨asst, indem man eine mit kubischer Laufzeit umwandelnde Technik verwendet. Neu eingef¨urt werden hier Polyhedrische Etiketten f¨ur Argumentation Frameworks. Dabei handelt es sich um einen Polytop, wessen ganze Punkte genau die Inzidenzvektoren von bestimmten Arten von Dungs Ausgabe sind. Weiterhin wird ein neuer Begriff der Akzeptanz von Argumenten gepr¨agt, n¨amlich - deliberative Akzeptanz - und dessen Komplexit¨at analysiert. Dieser Teil erweitert und verfeinert einige ihrer Ergebnisse aus der Masterarbeit. Im zweiten Teil wurde ein neuartiges graphenbasiertes Modell f¨ur die Aggregation von Pr¨aferenzen erarbeitet. Hier werden axiomatische Charakterisierungen von Aggregatoren neu eingef¨uhrt, und zwar durch die Verwendung von Graphoperationen zur Beschreibung der Eigenschaften von Aggregatoren. Sie entsprechen dem ¨ublichen Mehrheitsprinzip bzw. der Genehmigungs- & Ablehnungsregel. Einen neuartigen, qualitativen Ansatz im Vergleich zu der klassischen Sozialwahltheorie bietet die Integration der Semantik von Dung in dem neuen Modell, und zwar argumentative Aggregation individueller Pr¨aferenzen. Desweiteren wird ein funktionales many to many zweiseitige M¨arkte abstrahierendes Framework untersucht, indem statt die Existenz einer Stabilen Wahl Matching in einem Bipartite Wahlsystem zu studieren, wird die Existenz von Stable Common Fixed Points auf zwei Wahlfunktionen erforscht. Im n¨achsten Schritt wird eine neue Verallgemeinerung des Gale-Shapley Algorithmus entworfen und eine neue Charakterisierung der Wegunabh¨angigkeitsfunktion gegeben, die einen Korrektheitsbeweis f¨ur den Algorithmus erm¨oglicht. Im dritten Teil werden schließlich Dungs Argumentation Frameworks auf Opposition Frameworks erweitert und dadurch die in der gegenw¨artigen Forschung bestehende L¨ucke zwischen strukturierter und abstrakter Argumentation verringert. Daf¨ur wird ein bewachter Angriffskalk¨ul entwickelt, welches strikten Verallgemeinerungen von Dungs echten Erweiterungen f¨uhrt.