Graph Aggregation
Ulle Endriss, Umberto Grandi

Abstract:
Suppose a number of agents each provide us with a directed graph over
a common set of vertices. Graph aggregation is the problem of
computing a single graph that best represents the information inherent
in this profile of individual graphs. We introduce a simple formal
framework for graph aggregation and then focus on the notion of
collective rationality, which asks whether a given property of graphs,
such as transitivity, can be guaranteed to hold for the collective
graph whenever it is satisfied by all individual graphs. We refine the
ultrafilter method for proving impossibility theorems in social choice
theory to arrive at a clear picture relating axiomatic properties of
aggregation procedures, properties of graphs with respect to which we
want to ensure collective rationality, and properties of ultrafilters.