In its most traditional setting, the main concern of optimization theory is the search for optimal solutions for instances of a given computational problem. A recent trend of research in artificial intelligence, called solution diversity, has focused on the development of notions of optimality that may be more appropriate in settings where subjectivity is essential. The idea is that instead of aiming at the development of algorithms that output a single optimal solution, the goal is to investigate algorithms that output a small set of sufficiently good solutions that are sufficiently diverse from one another. In this way, the user has the opportunity to choose the solution that is most appropriate to the context at hand. It also displays the richness of the solution space. When combined with techniques from parameterized complexity theory, the paradigm of diversity of solutions offers a powerful algorithmic framework to address problems of practical relevance. In this work, we investigate the impact of this combination in the field of Kemeny Rank Aggregation, a well-studied class of problems lying in the intersection of order theory and social choice theory and also in the field of order theory itself. In particular, we show that the Kemeny Rank Aggregation problem is fixed-parameter tractable with respect to natural parameters providing natural formalizations of the notions of diversity and of the notion of a sufficiently good solution. Our main results work both when considering the traditional setting of aggregation over linearly ordered votes, and in the more general setting where votes are partially ordered.
翻译:在最传统的环境下,最优化理论的主要关切是寻找对特定计算问题的各种情况的最佳解决办法。最近人工智能研究的趋势,即所谓的解决方案多样性,侧重于发展在主观性至关重要的情况下可能更适合的最佳性概念。想法是,与其旨在开发产生单一最佳解决办法的算法,而是要调查产生一小套足够多样的足够好的解决办法的算法。这样,用户就有机会选择最适合当前情况的解决方案。它也展示了解决方案空间的丰富性。如果结合参数化复杂理论的技术,解决方案多样性的范式提供了一个强有力的算法框架,以解决实际相关性问题。在这项工作中,我们调查这种组合在Kemeny Rank Agregication领域的影响,这是在秩序理论和社会选择理论以及秩序理论本身的交集中,人们深思熟虑的一类问题。我们特别表明,Kemenynical Agregation是传统化空间的丰富性空间。当我们传统的复杂理论理论中,在考虑自然多样性和直线性投票的固定性结果时,我们通常的表决是固定的固定的。