Zusammenfassung
Graph aggregation is the process of computing a single output graph that
constitutes a good compromise between several input graphs, each provided by a
different source. One needs to perform graph aggregation in a wide variety of
situations, e.g., when applying a voting rule (graphs as preference orders),
when consolidating conflicting views regarding the relationships between
arguments in a debate (graphs as abstract argumentation frameworks), or when
computing a consensus between several alternative clusterings of a given
dataset (graphs as equivalence relations). In this paper, we introduce a formal
framework for graph aggregation grounded in social choice theory. Our focus is
on understanding which properties shared by the individual input graphs will
transfer to the output graph returned by a given aggregation rule. We consider
both common properties of graphs, such as transitivity and reflexivity, and
arbitrary properties expressible in certain fragments of modal logic. Our
results establish several connections between the types of properties preserved
under aggregation and the choice-theoretic axioms satisfied by the rules used.
The most important of these results is a powerful impossibility theorem that
generalises Arrow's seminal result for the aggregation of preference orders to
a large collection of different types of graphs.
Nutzer