Beyond Pairwise Comparisons in Social Choice: A Setwise Kemeny Aggregation Problem

Rank aggregation aims at producing a single ranking from a co llection of rankings of a fixed set of alternatives. In social choice theory (e.g., Moulin 1991), where the alternatives are candidates to an election and each ranking represents the preferences o f a voter, aggregation rules are called Social Welfare Functions (SWFs). Apart from social choice, rank aggregation has prov ed useful in many applications, including preference learning (Cheng a nd H ullermeier, 2009; Cl emen con et al., 2018), collaborative filtering (Wang et al., 2014), genetic map creation (Jackson et al., 2008), similarity search in databases systems (Fagin et al., 2003) and design of web search engines (Altman and Tennenholtz, 2008; Dwork et al., 2001). In the fo llowing, we use interchangeably the terms "input rankings" and "preferences", "output rank ing" and "consensus ranking", as well as "alternatives" and "'candidates". The well-known Arrow's impossibility theorem states that t here exists no aggregation rule satisfying a small set of desirable properties (Arrow, 1950). In the absense of an "ideal" rule, various aggregation rules have been proposed and studied. F ollowing Fishburn's classification (1977), we can distinguish between the SWFs for which the out put ranking can be computed from the majority graph alone, those for which the output ranking can be computed fro m the 1 Table 1: Results of setwise contests in Example 1. set c